在Quora上看到一个有趣的问题。”What are the best programming interview questions you’ve ever asked or been asked?” （在编程面试中，你问过或者被问过的最好的问题是什么）里面有几道题目很有意思，在这里分享给大家。

第一道题：有一个长度为N+1的数组，里面的元素都是1~N的整数，但有些数字可能重复多次。例如1,1,3 ,3或者 1,3,2,2。现在要求打印出重复的数字（有多个数字重复时，可打印任意一个）。

解答：

1. O(N^2)的方法是每次检查一个元素，看是不是重复。

2. 相比之下，更容易想到的是O(N logN)的算法，先排序，重复数字会在邻接位置。

3. 还有花费空间来换时间的方法。建一个位图，对每一个数字，检查对应位置是否已经置位。该算法是O(N)时间复杂度和O(N)空间复杂度。

4. 还有一种O(N)时间复杂度和O(1)空间复杂度的算法。我们将原数组a先变换成：如果元素i出现一次，它就在位置i处；如果元素j出现多次，它除了在位置j处之外，还占据某些其他未出现的元素的位置。然后从头遍历数组，如果出现a[i] != i的情况，则a[i]是重复出现的数字。变换过程可参考 缺失的数字分析 和 数组统计分析的另一种方法。

5. 题目增加限制，如果不允许修改原数组，应该怎样做。直接上答案：统计1N/2的个数，如果个数大于N/2，则说明1N/2中有重复数字（鸽巢原理）。否则说明N/2+1~N中有重复数字。递归有重复数字的那一半。算法复杂度是O(N*logN)。

按照答主的描述，走到第5时，通常都需要一些提示。如果能答出5的答案，面试官应该就比较满意了。

第二道题：去掉大小王的52张扑克牌，你和你的朋友事先约定一种策略，使得：我任意给你5张扑克牌，你选择一张留下，剩余的4张给你的朋友，你的朋友能够根据事先约定的策略，知道你留下的牌是什么。

我觉得这道题难在如何进行编码。题目中没有任何能够进行编码的暗示，这时候要抛开限制，自己构造出编码的基础。

答主给的答案如下。

首先要传递花色这个信息。5张牌4种花色，一定有两张或以上的拍具有同样的花色，可以留一张该花色的牌。用同花色的牌传递花色信息。可用的牌剩下3张。3张牌大小顺序可以作为一种编码方式。3!=6中排列可以产生6中信号。但还不够覆盖13张牌。这时，注意到同花色的牌只用到了花色，其数字没有用到。定义牌之间的距离。将距1,2,3…J,Q,K视为首尾相连的环，其距离定义为两个数字相距不超过6的那个距离（13张牌一定有不超过6的距离，否则x和y两个方向都超过6，则至少需要14张牌）。如dist(J, 4) = 6, dist(J, 5) = dist(5, J) = 6。这样，我们在同花色的两张牌中，保留较小的那张，你的朋友从排列中得到16的某个数字，再加上同花色的牌面值，模除13即可。所以，你和你的朋友需要事先约定第一张牌作为同花色牌，什么排列顺序表示16的哪个数字。

评论中有人提到，可以加上正反信息，你把牌交给你朋友时，面朝上的牌和面朝下的牌代表0和1，也能编码出所需要的信息。不再赘述。

第三道题：原文是这样的。

Write a function that takes a function and two ints and applies it to the two ints. E.g.

$ arith sum 1 2

3

$ arith divide 6 3

2

我没弄清楚这道题想考察什么东西。例子给的是shell方式的使用接口。

看评论后，有人说是传递函数指针。难怪答主说：Good luck with that if your CS degree was taught in Java :P。哈哈，Java达到传递函数指针的效果是比C语言麻烦的多。

第四道题：从连续不断的数字流中随机选取一个数字（数字流只能过一遍），要求保证任意时刻，已经过去的数字流中任意一个数字被选中的概率相等。

这道题我在面试网易游戏的时候遇到过，解答参见 找工作备忘。

第五道题：这位答主说，他在面试Fb时，曾经被要求实现一个线索二分查找树（我只记得大概的概念了）。还有要求实现饼排序。参见：煎饼堆问题（转载）。

第六道题：给定整数N，计算从1到N的数字的二进制表示中所有1的个数。

这个题目挺有趣的。但是答主没给解答，而且0评论。

比较容易想到的就是统计每一个数字中1的个数。注意到 n & (n-1)可以消除n的最后一个1。

如果要直接统计1到N中1的个数，可能需要仔细想一想，我们先看看0~23的二进制表示（0不影响结果）。针对每一列，都有规律，例如，第一列是 01循环出现，第二列是0011循环出现，第三列是00001111循环出现……

按列统计，

第一列出现1的个数为：(N+1)/2

第二列出现1的个数为：(N+1)/4 * 2 + ( (N+1)%4>2 ? (N+1)%4 - 2 : 0 )

第三列出现1的个数为：(N+1)/8 * 4 + ( (N+1)%8>4 ? (N+1)%8 - 4 : 0 )

第K列出现1的个数为：(N+1)/(2^K) * (2^(K-1)) + ( (N+1)%(2^K)>2^(K-1) ? (N+1)%(2^K)-2^(K-1):0 )

所以只需要按列计算就可以达到O(Column)的复杂度。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12

int count(int n){

         int k = 1, c = 0;

         while( (1<< k ) < n ){
                   c = c + (n+1)/(1<<k)*(1<<(k-1));
                   if((n+1)%(1<<k) > (1<<(k-1)))
                            c = c + (n+1)%(1<<k)-(1<<(k-1));
                   k++;
         }
         return c;
}

有的回答认为面试考这些题意义不大，Google面试已经减少了此类问题。不过我觉得能活跃一下大脑总是不错的。

当然，还有来歪楼的回答：

When can you start?

Always puts a smile on my face.