1. 给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。
2. 给你n个数，其中有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。
1. 从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。
2. 从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。
题目来源：http://groups.google.com/group/pongba/browse_frm/thread/f4a080edbe3ce0e1
早晨7:40的闹铃。到36楼下面见到了我的两个队友后，随便吃了点东西就出发了。
计算中心门前特别热闹，N多人围在一张大桌子前，好像是在签到。我挤进去找了半天发现没我的名字，名单上全是信科的人。我抬头问，中文的在哪儿呢。一个美女姐姐用手指了远处的一个几乎没人的地方说“中文的在那边”，并说了一句“哇，中文的呀，太牛B了”。我顺着她手指的方向望过去，另一张小桌子前面贴了“中文”二字，桌子后面没有人，估计是交给了旁边负责数院和元培的人，让他们顺便管一下。从我目前所了解的情况来看，那张桌子应该是特别为我准备的，它在历史上很可能是第一次出现。
第四题是做得最顺利的一道题。我把所有题粗略看了一遍后，首先决定就想这道题。题目描述巨简单，就是问你沿对角线把一个正n边形剖分成三角形和四边形有多少种方法。上图显示了n=5时所有的10种方法。熟悉组合数学的人都知道，三角形剖分方案对应的是Catalan数列，其递推公式的推导相当经典。设C(n)表示凸n+2边形的剖分方案数，枚举底边和哪一个点相连（下图左），容易看出C(n) = C(0)*C(n-1) + C(1)*C(n-2) + … + C(n-1)*C(0)。
现在，如果剖分中允许有四边形的出现，又该怎么办呢？看看数据规模n≤5000，估计应该是叫我们寻找类似的递推公式。容易想到，我们可以枚举底边与哪一个点相连构成三角形，统计出底边属于某个三角形的剖分方案T(n)=ΣC(i)C(j), i+j=n-1；再枚举底边和哪两个点相连构成四边形，统计底边在一个四边形上的剖分数Q(n)=ΣC(i)C(j)C(k), i+j+k=n-2。但是，枚举四边形需要O(n^2)的时间，这样的话整个程序就是O(n^3)的了，n=5000绝对超时。那怎么办呢？两分钟后，我想到了一个具有决定意义的点子：计算Q(n)可以直接利用以前算过的T(i)。枚举四边形的两个顶点时，固定四边形的左边那个顶点，你会惊奇地发现右半部分的所有情况加起来正好就是一个T(i) （上图右）。因此，ΣC(i)T(n-i-1)就是我们所需要的Q(n)。
一个有趣的细节是，这道题要求选手输出结果除以2^64的余数，不知道会不会有人想不到这个该怎么处理；事实上只需要直接用64位无符号类型来运算就可以了，超界了后计算机储存的本来就已经是2^64的余数了。
12. 两个机器人，初始时位于数轴上的不同位置。给这两个机器人输入一段相同的程序，使得这两个机器人保证可以相遇。程序只能包含“左移n个单位”、“右移n个单位”，条件判断语句If，循环语句while，以及两个返回Boolean值的函数“在自己的起点处”和“在对方的起点处”。你不能使用其它的变量和计数器。
答案：两个机器人同时开始以单位速度右移，直到一个机器人走到另外一个机器人的起点处。然后，该机器人以双倍速度追赶对方。程序如下。
while(!at_other_robots_start) {
move_right 1
}
while(true) {
move_right 2
}
13. 如果叫你从下面两种游戏中选择一种，你选择哪一种？为什么？
a. 写下一句话。如果这句话为真，你将获得10美元；如果这句话为假，你获得的金钱将少于10美元或多于10美元（但不能恰好为10美元）。
b. 写下一句话。不管这句话的真假，你都会得到多于10美元的钱。
答案：选择第一种游戏，并写下“我既不会得到10美元，也不会得到10000000美元”。
偶然进了这个页面，看到几个原来没见过的面试智力题。顺带也翻译一些比较少见、可能有人没见过的题目写在这里。有几个题目在国内流传相当广，什么n个人怎么分饼最公平，屋里的三个灯泡分别由哪个开关控制，三架飞机环游世界，用火柴和两根绳子测量45分钟之类的题目，火星得已经可以考古了，这里就不再说了。个别题目本Blog原来有过详细的介绍，这里也不再提了。
1. 考虑一个双人游戏。游戏在一个圆桌上进行。每个游戏者都有足够多的硬币。他们需要在桌子上轮流放置硬币，每次必需且只能放置一枚硬币，要求硬币完全置于桌面内（不能有一部分悬在桌子外面），并且不能与原来放过的硬币重叠。谁没有地方放置新的硬币，谁就输了。游戏的先行者还是后行者有必胜策略？这种策略是什么？
答案：先行者在桌子中心放置一枚硬币，以后的硬币总是放在与后行者刚才放的地方相对称的位置。这样，只要后行者能放，先行者一定也有地方放。先行者必胜。
2. 用线性时间和常数附加空间将一篇文章的单词（不是字符）倒序。
答案：先将整篇文章的所有字符逆序（从两头起不断交换位置相对称的字符）；然后用同样的办法将每个单词内部的字符逆序。这样，整篇文章的单词顺序颠倒了，但单词本身又被转回来了。
3. 用线性时间和常数附加空间将一个长度为n的字符串向左循环移动m位（例如，”abcdefg”移动3位就变成了”defgabc”）。
答案：把字符串切成长为m和n-m的两半。将这两个部分分别逆序，再对整个字符串逆序。
4. 一个矩形蛋糕，蛋糕内部有一块矩形的空洞。只用一刀，如何将蛋糕切成大小相等的两块？
答案：注意到平分矩形面积的线都经过矩形的中心。过大矩形和空心矩形各自的中心画一条线，这条线显然把两个矩形都分成了一半，它们的差当然也是相等的。
5. 一块矩形的巧克力，初始时由N x M个小块组成。每一次你只能把一块巧克力掰成两个小矩形。最少需要几次才能把它们掰成N x M块1×1的小巧克力？
答案：N x M – 1次显然足够了。这个数目也是必需的，因为每掰一次后当前巧克力的块数只能增加一，把巧克力分成N x M块当然需要至少掰N x M – 1次。
Read more…
如果你经常使用“file5.txt”、“梁静茹23.mp3”、“AdultVideo153.avi”一类的文件名，你会发现在给文件名排序时，这种命名方式存在很大的弊端。很大一部分程序直接用字典序给文件名排序，因此file10.txt会排到file2.txt前面，尽管事实上10比2大。你是否想过，有没有什么办法能给数字编码，使得它们按字典序排序后仍然保持原有的大小顺序，并且编码的方法足够简单，编码之后原来的数字仍可以一目了然？一种简单的方法就是加前缀0，这样就保证了002在010前面，file005.txt也不会排到file100.txt的后面。它有一个缺点就是，你必须预先知道需要编码的数字最多有多少位，否则一旦新添进一个位数更多的数，前面所有的数必需要全部重新编码（加更多的前缀0）。另一个比较明显的缺点就是，这种编码方式过于冗长，添加进去的数字0最多可能与最大数的位数相当，多数情况下都远远超过了待编码的数自身的长度。我们更希望，编码时添加进去的“辅助码”不要超过这个数字本身的长度。由于数字n本身的长度是log(n)，因此我们需要保证冗余部分不超过log(n)。你能找到满足这些条件的一种编码方式吗？
注意到，当数字位数相同时，数值小的数按字典序排列时也排在前面。问题的关键就是，你需要找到一种编码方式，它可以标识出数字的位数，并且这种标识可以保证数字按位数从小到大排序。于是我们想到用“一进制编码”为每一个数加上一个“位数标识”。我们在每个数前面加上和这个数字本身的位数一样多的”1″，中间用一个”0″隔开。这样，所有三位数都是1110???的形式，所有四位数都是11110????的形式，这样按字典序排序时，三位数一定都排在四位数的前面。对应的解码方法也相当简单，只需要取第一个”0″后面的数字就行了。忽略常数的话，这种编码方式的冗余长度为log(n)，和数字本身的长度相当，基本上符合我们的要求。