一个迟到的消息：Google Treasure Hunt 2008已经开始了，这是Google Sydney为了挖掘出新的工程师而精心设置的一个活动。现在已经有两道题目了，在以后几周的时间里Google将陆陆续续地发布更多的题目。第一个答对所有问题的人将成为这次Treasure Hunt的获胜者。
    有兴趣的朋友赶快去试一试。

    Ben orenstein尝试在Goolge Code Search里输入脏话，在众多的开源软件中找到了一些非常牛B的代码：

gdb-6.4.50.20060515:
/* OK, now set up the filehdr...  */

/*   We will NOT put a fucking timestamp in the header here. Every time you
     put it back, I will come in and take it out again.  I’m sorry.  This
     field does not belong here.  We fill it with a 0 so it compares the
     same but is not a reasonable time. — gnu@cygnus.com  */

Siesta-0.66:
    # This job would be great if it wasn’t for the fucking customers.

CGI-FormBuilder-3.0202:
        # Get field from radio buttons or checkboxes
        # Must cycle through all again to see which is checked. yeesh.
        # However, this only works if there are MULTIPLE checkboxes!
        # The fucking JS DOM *changes* based on one or multiple boxes!?!?!
        # Damn damn damn I hate the JavaScript DOM so damn much!!!!!!

DJabberd-0.81:
    # Trillian, again, is fucking stupid and crashes on just
    # about anything its homemade XML parser doesn’t like.

gift-0.11.5:
void list_lock_insert_sorted (ListLock *lock, CompareFunc func, void *data)
{
    if (lock->locked)
    {
        /* TODO: this is obviously not right ... this whole fucking module
         * sucks anyway */
        list_lock_prepend (lock, data);
        return;
    }

    lock->list = list_insert_sorted (lock->list, func, data);
}

bh-asia-03-grugq:
    /* if we get here, there are massive fucking problems, for a start
     * our stack is fucked up, and we can’t return(). Just crash out. */

trunk:
    /* FIXME: please god, when will the hurting stop? Thus function is so
              fucking broken it’s not even funny. */

SQL-Abstract-1.20:
    # Note to self: I have no idea what this does anymore
    # It looks like a cool fucking segment of code though!
    # I just wish I remembered writing it… :-\

mendax_linux:
for(i = 0 ; i < pktcount; i++) {
    from.sin_port = htons(ntohs(from.sin_port) + 1);
    pktlen = gen_tcp_pak(&pak, &from, dst, ip_id++,
                     seq_num, 0L, 0, flags);
    seq_num += 64000;

    /* don't fire dem packets too fucking fast */
    usleep(1000);

    send_pak((char *) &pak, pktlen, ether);
    putchar('.');
}

SugarOS-for-Microsoft-Full-4.5.0h:
    /*   Outlook can’t fucking follow RFC if someone PAID them to do it…
        oh wait, someone paid them NOT to do it. */

AfterStep-2.2.5:
    /* No we fucking don’t! DB entries should be stored in the same order
       as they are in the file ! I can’t belive I was so fucking stupid !  */

gallery-2.0.4/modules/core/classes/GalleryStorage:
else if ($affectedRows > 1) {
   /* Holy shit, we just updated more than one row!  What do we do now? */
   return GalleryStatus::error(ERROR_STORAGE_FAILURE, __FILE__, __LINE__,
                        "$query (" . implode('|', $data) . ") $affectedRows");
}

linux-2.4.34.1/arch/sparc/lib/checksum.S:
        /* Sun, you just can’t beat me, you just can’t.  Stop trying,
         * give up.  I’m serious, I am going to kick the living shit
         * out of you, game over, lights out. */

linux-2.6.1/arch/mips/kernel/sysirix.c:
    /* 2,191 lines of complete and utter shit coming up… */

nfs-utils-1.1.0/utils/statd/misc.c:
    if (!(ptr = malloc (size)))
            /* SHIT!  SHIT!  SHIT! */
            die (”malloc failed”);

dada-2_10_12:
    # code below replaces code above - any problems?
    # yeah, it doesn’t fucking work.

    这个可能比较火星，很多人可能已经知道了这个彩蛋；但如果你事先不知道这个彩蛋而碰巧遇上了，你能找出触发这个彩蛋的条件吗？刚才打开iGoogle，发现一件神奇的事件：我的iGoogle主题的顶部图片上居然出现了一个圆周率π──天上的星星排列出来的形状。我立即想到这是iGoogle的一个彩蛋，但我却不知道是什么东西触发了这个彩蛋。仔细想了一下后，突然恍然大悟，这个触发条件确实符合Google的Geek精神。把当时的截屏放出来给大家看一看，如果你还不曾听说过这个彩蛋，你完全可以通过这个截屏找出这个彩蛋的触发条件。继续看下去前不妨先来找找看~~

    图上显示截屏的时间是11点15分。中国是东八区，比标准时间早8小时，因此国际标准时间是3点15分。考虑到本机时间准确性、截屏时间稍晚等原因，很容易想到iGoogle页面的实际生成时间是3点14分。也就是说，当国际标准时间恰为3:14时，iGoogle将会出现彩蛋。

图片地址：http://www.google.com/ig/images/skins/sweetdreams/3.14am/header_bg.jpg
了解更多：http://www.gseeker.com/50226711/googleaeaeeceee_66197.php

看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*...*A[i]，Q[i]=A[n]*A[n-1]*...*A[i]。于是，B[i]=P[i-1]*Q[i+1]。

突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。

今天看Google分析时发现了一件和上次相比更加不可思议的事情。

今天早上登陆Google分析，发现昨天的网站点击来源里居然有这么一项……
有没有人能解释一下这是为什么？

    订阅这个Blog的人可能不止OIer，或许有一些喜欢数学谜题或者智力游戏的人。Google US Puzzle Championship即将开始了，不知道是否有人感兴趣。
    四道测试题已经发布，我翻译一下放在这里。

================= 我是性感的分割线 =================

Puzzle #1 – Arrow Sudoku
    数独加强版：每个圆圈里的数必须要等于对应箭头标识的路径上的数之和。

      


Puzzle #2 – Card Trick (Cihan Altay)
    14张写有数字的卡片放在了3x3的格子里，每行每列的数字之和已经给出。拿起其中两张卡片，放回格子中的任意位置，使得六个总和相等。

      


Puzzle #3 – Point Pairs (Cihan Altay)
    用13条直线段将图中的点成对地连起来，使得这些线段的长度正好是1到13中的13个数。每个点只能用一次；线段与线段间可以交叉，但线段上不能有其它点。

      


Puzzle #4 – First Name Basis (Shawn Kennedy)

• ADA
  
• ALDOS
  
• ALEX
  
• ANN
  
• BYRON
  
• ELIJAH
  
• ELLA
  
• HANS
  
• HESS
  
• ISABEL
  
• JOYCE
  
• LANCE
  
• LEAH
  
• LENA
  
• REX
  
• SOL

     把上面的16个名字放在下面的格子中（每格放一个字母），使得每一行、每一列恰好出现一个名字（中间允许有空格出现）。
    


    下面的例子演示了有12个单词的情况，其中横向的单词为WOOD, INCH, LATE, PUN, TERSE, STEW，纵向的单词为WILT, NAPS, OCTET, OUR, DENSE, HEW。
    


================= 我是性感的分割线 =================

    这些题的答案都还很“正常”，第二题除外。第二题的答案打死你都想不到：把右边的1覆盖在下边的2上，把左上角的9当成6放回去，这样所有的和都是27。

    和大家一样，我也是一个G饭，将百度设为默认搜索引擎的唯一一个原因仅仅是上网看到了不认识的单词后，鼠标选中一拖（用了Drag de Go）就可以看到百度词典的链接。有时也会用一下搜狗，因为搜狗还有一个显示偏僻字读音的功能。今天没事干，打算写一个Greasemonkey脚本让Google显示搜索关键字的读音和释义（中英文都可以）。
    花了大概两个小时，具体方法是给Dict.cn发送XMLhttp请求，并把结果插入到Google页面中。我做人还算厚道，用了别人的东西是要链一下别人的，因此加了一个“View More”链接。不知道Google本身或者FireFox插件能不能实现这样的效果，反正我是没有找到。我想肯定有人需要这个，因此发布出来大家可以测试一下。

点击这里安装
注意：安装前请确认你正在使用FireFox并已经安装了Greasemonkey插件！
成功使用或有任何问题的同志在下面留个言

    目前我在FireFox 2.0和英文google环境下使用正常，大家发现Bug请帮忙报告一下。不过我好像每次叫大家报告Bug时都没人理我。
    目前已知问题：由于编码问题，中文关键字的“View More”链接无效。
    Matrix67原创，转贴请注明出处。