A-A+

几道面试趣题( 打印重复数字 编码扑克牌 煎饼堆排序 随机选取数字 统计1的个数 )

2014年03月21日 算法 暂无评论 阅读 2,491 次
摘要:

逛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。现在要求打印出重复的数字(有多个数字重复时,可打印任意一个)。
第二道题目:去掉大小王的52张扑克牌,你和你的朋友事先约定一种策略,使得:我任意给你5张扑克牌,你选择一张留下,剩余的4张给你的朋友,你的朋友能够根据事先约定的策略,知道你留下的牌是什么。
从连续不断的数字流中随机选取一个数字(数字流只能过一遍),要求保证任意时刻,已经过去的数字流中任意一个数字被选中的概率相等。
给定整数N,计算从1到N的数字的二进制表示中所有1的个数。

在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. 题目增加限制,如果不允许修改原数组,应该怎样做。直接上答案:统计1~N/2的个数,如果个数大于N/2,则说明1~N/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。这样,我们在同花色的两张牌中,保留较小的那张,你的朋友从排列中得到1~6的某个数字,再加上同花色的牌面值,模除13即可。所以,你和你的朋友需要事先约定第一张牌作为同花色牌,什么排列顺序表示1~6的哪个数字。

评论中有人提到,可以加上正反信息,你把牌交给你朋友时,面朝上的牌和面朝下的牌代表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循环出现……

ones 

按列统计,

第一列出现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)的复杂度。

代码如下:

 

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

当然,还有来歪楼的回答:

When can you start?

Always puts a smile on my face.

 

 

标签:

给我留言