2024年4月22日发(作者：时悦宜)

硅谷流行迷题面试

近年来，越来越多的硅谷科技公司开始在面试中提出类似的问题。这些公司感兴趣的并不是

正确答案，而是应聘者解决问题的方式和能力。当今的商业世界瞬息万变，企业更需要有独立思

考能力的人才，而不仅仅是高智商、高学历的工程师。早在上世纪80年代末，微软就在面试中

引入了一些开放式的逻辑问题，例如“波音747有多重？”。微软招聘经理华伦·阿什顿(Warren

Ashton)表示：“我们希望通过这一方式考察应聘者的创造力。”

“为什么下水道的盖子是圆的？”，这是阿什顿在面试中最经常问到的一个问题。阿什顿表示，

最常见的答案是，“在任何角度下，圆的下水道盖子都不 会掉落到下水道中，而方的则不然。”

但是，一些人也提供了其它答案，例如“圆的下水道盖子容易从一个地点搬运到另一个”，或者“圆

的下水道盖子加工成本较 低”。他说：“我们希望应聘者充分发挥自己的思维和想象力，给出更

多答案。”

在硅谷高科技公司的面试中，经常会出现这类问题。谷歌前员工马克·简(Mark Jen)表示：

“雇主希望了解你在一定数量级之内能否做出准确的预计。”一般来说，优秀的应聘者会做出有根

据的推测，而不是计算准确的数字。事实上，面试 人员也正是通过考察应聘者估算的方式，来

确定最合适的人选。例如，亚马逊就经常在面试中提出这样的问题，“美国有多少个加油站？”，

或者“擦遍西雅图所有 窗户能挣多少钱？”。

当然，现在的面试远不止估算这么简单。作家、设计顾问布鲁克·埃克尔(Bruce Eckel)经

常会让应聘者用程序语言来描述一只小鸡；eBay面试人员经常会提出一个著名的逻辑问题

——“强盗分金币”：5名强盗 (A、B、C、D、E) 分100个金币。他们决定从A开始提出分配

方案，如果不能获得半数以上的支持，A将被处死，然后由B提出分配方案，依此类推。如果

每一名强盗都足够聪明， 那么A提出什么样的方案才能保证自己获得最多的金币，而且不会被

处死？

谷歌走得最远

尽管很多公司都采用了迷题面试，但没有哪家公司像谷歌这样彻底。三年前，谷歌在美国

101公路硅谷地段树立了一个醒目的广告牌，上面只有一个复杂的数学问题。如果过往行人提

交的答案正确，谷歌就会邀请他访问一个秘密网站，而这个网站上有一道更难的问题。如果答案

再次正确，谷歌将邀请他提交个人简历，并到谷歌总部参加面试。

当然，这距离应聘者正式加入谷歌还有很远的距离，至少他还要在面试中回答很多刁钻古怪

的问题。其中最常见的一个问题是：假设你的身高缩小至一枚硬币那么大，当然是按比例缩小，

密度不变。你被扔进了一个空的玻璃搅拌机里，刀片将于60秒后开始工作，你会怎么办？

并非只有应聘者需要适应这种全新的招聘方式，雇主也同样如此，他们必须面对很多从未遇

到过的问题。今年早些时候，LinkedIn创始人雷德· 霍夫曼(Reid Hoffman)开始为自己的公

司寻找一位CEO。在这一过程中，他采用了一种全新的方式来查看简历。他并没有将目光锁定

在某一个特定的候选者，而是使用 LinkedIn网络查找最合适的人选。(摩尔)

google面试题（一）

有一个random number generator，是生成真实的随机数，而不是伪随机数，这个东西会生

成几千亿个32位整数，打印出现次数前100的整数。

方法一：由于数的范围已经确定，采用计数排序的方法计算出0-2^31-1间数的出现次数，如

下代码所示:

int[] array=new int[2^31-1]；

for i=0 to n-1 do {

array[a[i]]++；

}

时间复杂度0(n),空间复杂度0(n)

接着问题就变成寻找数组array中前100大的数，可以采用类似快速排序的方式，先找第100

大的数e的位置l，然后使用快速排序的partion方法重构数组，使得l前面的数都小于e，l

后面的数都大于e，如下：

int radomize_select(int[] array, p, r, int i) { // 找第i大的数的位置

if(p==r){ // 递归出口

return array[p];

}

q=radomize_partion(A,p,r);

k<-q-p+1;

if(i<=k){

return radomize_select(array,p,q,i);

}

else{

return radomize_select(array,p,q,i-k);

}

}

时间复杂度0(n),空间复杂度0(1)

void getResult(){

int l=radomize_select(array, 0, n-1, 100);

q=partion(l); //快速排序的partion

for i=q to n-1 {

输出 array[i];

}

}

时间复杂度0(n),空间复杂度0(1)

综上，时间复杂度0(n),空间复杂度0(n)

方法二：采用哈希表, key is i, value is the count of i

Hashtable table=new Hashtable();

for i=0 to 2^31-1 do {

int count=0;

if((i)==null){

count++;

}

else{

count=++((i));

}

(i,count);

}

剩下的方法和上面一样，略

时间复杂度0(n),空间复杂度>0(n)

对比以上2种方法，时间复杂度一样，但方法一的孔间复杂度稍微小于方法二，哈希表的空间

一般情况下比普通的数组的空间要大

google面试题（二）

平面上N个点，求一条直线，穿过的点数最多

思路：2点确定一条线，N个点共有n(n-1)/2条线，穿过的点数最多的直线，斜率相同的最多，

因此只要找出相同斜率最多的点对集合，并且有公共点的即可

方法一：用上三角矩阵，矩阵里的值为任意两点的斜率，上三角矩阵用数组(n-1)/2]表

示。问题就转化为求数组中相同数最多的并且有公共点的数，方法参照“[微软面试题]请把一个

整形数组中重复的数字去掉”。

时间复杂度0(n^2)

方法二：平面上N个点以及这N个点构成的无向图，边数n(n-1)/2，对图遍历（深度或广度），

遍历到某个点node的时候，计算该点与它的前一个点的斜率r，用pr存储前一个点与它的前

结点的斜率，如果pr！=r，则返回到node，继续遍历node的下一条边，如果斜率相等，则

count++。如果找不到，则从一下结点开始遍历未访问过的节点。

时间复杂度0(n^2)

google面试题（三）

算法题一：Given 1 GB memory, input a file which contians 4 billion integers,

output one integer that is not in the file. What if you have only 10 MB

memory?

算法题二：There are 100 hundred sorted arrays, and each of them contains 100

numbers. Give an algorithm to merge them into a single sorted array, using

only one temporary array in the middle steps.

编程题：Input an integer array of size n and an integer k (k<=n), output all subsets

of size k.

思路：

(一) 整型变量的值的范围是-（2的15次方）至（2的15次方）-1，因此为数组开辟2^16

的空间，也就是64K的大小，设置一定大小的缓冲(几十K左右)，把文件读入，依次统计缓冲

区的整数出现的次数，次数为0的即位结果

(二) 使用胜者树或败者树，K=100路归并，用one temporary array来构造以及重构树。或

者

1. 取100个数组中各自的第一个数，组成一个最小堆。

2. 输出堆中的最小值，并且把这个最小值对应的数组的第二个数加入堆，并且调整。

3. 重复步骤2直到所有数组中的值都被输出。

显然前者效率较高。

空间需要为一个长度为10000的临时数组。

(三) for i=0 to n-k-1 do {

for j=i to i+k-1 do{

out(a[j]+" ");

}

out("n");

}

循环次数nk-k^2, 时间复杂度0(n)

Google面试题（四）

26个英文字母从新排序（未知的顺序alphabet），然后用这个位置的顺序给一组数据(array list)

排序现在给你这组array list，问能不能计算出来那个alphabet未知的顺序。

思路：拓扑排序就行

0. 初始排序图[G]为单个点[0]，[0]小于任何字母（添加[0]为了保证图的连通性，编

程简单），[G]为有向图。

1. 对于输入array [A]，取每个串第一个字母，去重复，得到一个有序序列[T]。将这

个串merge到排序图中，merge的方法：

a.对[T]每个字母[a_i]，如果在[G]中没有存在，则添加到[G]中。若[a_i]为[T]中

第一个字母，则添加边[a_i]->[0]，否则添加边[a_i]->[a_i-1]。

b. 如果[a_i]在[G]中已经存在，若边[a_i]->[a_i-1]（对于[a_0]为[a_0]->[0]）

不存在，添加此边。

2. 对于首字母相同的[A]中的串，去掉首字母后组成新的array [A]', 如果有空串，在

空串处splitarray。 递归调用步骤1.

结果生成：

1. 如果[G]中存在回路，输入有矛盾，无解

2. 如果[G]中的字母节点小于26个，或者存在环（除1情况外），产生不唯一的解。

3. 如果[G]是一条含有26个节点的无环路径，产生唯一解。

Google面试题（五）

几星期前，一个朋友接受了Google公司的面试，他透露了面试中的一些问题。顺便，我把从其

他几个曾经面试过的人那里听来的内容也整理在一起。最大的互联网公司Google的一份面试题

集，看看你是否能够回答出来。其中很多问题都是开放式的，正确的解答有许多种，所以在这里

就不提供答案了。

1. 一辆学校班车里面能装多少个高尔夫球？

2. 你被缩小到只有硬币厚度那么点高（不是压扁，是按比例缩小），然后被扔到一个空的

玻璃搅拌器中，搅拌刀片一分钟后就开始转动。你怎么办？

3. 要是让你清洗整个西雅图的所有窗子，你会收取多少费用？

4. 怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出？

5. 你要向你8岁的侄子解释什么是数据库，请用三句话完成。

6. 时钟的指针一天内会重合几次？

7. 你需要从A地去B地，但你不知道能不能到，这时该怎么办？

8. 好比你有一个衣橱，里面塞满了各种衬衫，你会怎么整理这些衬衫，好让你以后找衬衫

的时候容易些？

9. 有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎

言，但是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子

一旦证明丈夫不忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，

镇上的女王宣布，至少有一个丈夫是不忠的。这是怎么发生的呢？

10. 在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一

个，直到生下的是男孩为止。这样的国家，男女比例会是多少？

11. 如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆

车开过的几率是多少 （假设为常概率条件下）

12. 如果你看到钟的时间是3:15，那一刻时针和分针的夹角是多少？（肯定不是0度！）

13. 4个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分

钟的手电筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四

个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5

分钟，最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥？

14. 你和朋友参加聚会，包括你们两人在内一共有10个人在场。你朋友想跟你打赌，说这

里每有一个人生日和你相同，你就给他1元，每有一个人生日和你不同，他给你2元。

你会接受么？

15. 全世界有多少个钢琴调音师？

16. 你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅

称两次将那个重一些的球找出来。

17. 有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。

但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让

自己拿到尽可能多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）

你觉得自己有把握去Google工作了么？

附：一些问题的候选答案

1、一辆学校巴士中可以放多少个高尔夫球？

一辆学校巴士可以塞进多少个高尔夫球？

大约50万，假设巴士有50个高尔夫球高，50个高尔夫球宽，200个高尔夫球长。

2、假如你被扔进了一个空的玻璃搅拌机里，刀片将于60秒后开始工作，你会怎么办？

如何从搅拌器中逃生？

(1)顺着度量刻度往上爬；

(2)把搅拌器的玻璃罩拧下来；

(3)利用旋转的气流“飞”出来。

3、擦遍西雅图所有窗户能挣多少钱？

假如西雅图有1万栋建筑物，每栋建筑物有600个窗户，擦一个窗户需要5分钟，收费标

准为每小时20美元，那么一共可以挣1000万美元。

Google面试题（六）

题目：对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，

时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是

O(1)。

分析：要使pop,push,min都是O(1)，所以肯定要牺牲点空间

思路：1：在stack的数据结构中加两个个字段，如

typedef struct {

int data[MAX];

int top;

int min;

int second;

}stack;

pop,push的时候都去栈顶元素，所以是O(1)

min的时候取stack的min字段，所以也是O(1)

每次push的时候进行比较，如果当前push的元素比stack->min小，则用当前元素

替换stack->min，用原来的min替换second。如果当前push的元素比stack->min大，

但比second小，则用当前元素替换stack->second。于是达到了取min的效果，程序如下

int push(stack * s,int x){

ASSERT(s!=NULL);

if(s->top>=MAX)

{

printf("Stack overload!");

return -1;

}

s->data[s->top++]=x;

if(xmin)

s->min=x;

return 0;

}

每次pop的时候进行比较，如果pop的元素为min，则用second替换min。于是达到

了取min的效果，程序如下

int pop(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty!");

return -1;

}

(*x)=s->data[s->top--];

if(x==s->min) s->min=s->second;

return 0;

}

int min( stack *s,int *x )

{

ASSERT(s!=NULL);

(*x)=s->min;

return 0;

}

思路2：设置辅助栈ass,记录每个状态下的最小值，每次插入时，得到辅助栈当前值，和插入

的值比较

如果小则插入到最小值栈的就是它，否则就是原来的最小值，通过这种方式，pop，push，min

三个都是

O(1)算法的。

typedef struct {

int data[MAX];

int top;

}stack;

STATIC int push_stack(stack *s,int x)

{

ASSERT((s!=NULL));

if(s->top>=MAX)

{

printf("Stack overload");

return -1;

}

s->data[s->top++]=x;

return 0;

}

STATIC int pop_stack(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty");

return -1;

}

(*x)=s->data[s->top--];

return 0;

}

int push(stack *main,stack *ass,int x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

push_stack(main,x);

if(x

{

push_stack(ass,temp);

push_stack(ass,x);

}

else

{

push_stack(ass,temp);

push_stack(ass,temp);

}

return 0;

}

int pop(stack *main,stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

pop_stack(main,x);

return 0;

}

int min(stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

pop_stack(ass,x);

push_stack(ass,(*x));

return 0;

}

Google面试题（七）

很多Google考生出来，也随之不少Google考试问答题目给释放出来，Google的面试题曾经

一度在网络上被粉丝和网民炒得很火热，这些题目被曝光也不止一次了。说实话，如果Google

还有点脑子的话，肯定会更换题目了。所以本次研究不是为了那些面试者而开设。只是出于粉丝

们来了解Google的一个组成部分，今天我去网上好好的搜罗了一下，如果你搜索题目，想找到

答案似乎是很难的事情：发现大部分都是转载Google考试题目的博客。内容被大量转载，导致

原来因该出现的“答案”被沉入搜索引擎的海底了。找了半天，我打算在这边建立一则文章，专门

用来收集Google考试题目和相关参考答案，方便大家研究和学习。值得一提的是，Google考

题分为几大类：日常知识型、思考型。还有一些我们甚至不知道用意是什么，凭什么拿来做面试

题… 也许在我们一起研究的同时，可以得出一些结论，如果你知道某个题目的答案或者有自己

的看法、见解直接在下面留言，我将总结到文章中去：

一辆学校班车里面能装多少个高尔夫球？

答：应该也是用常理推断过程

你被缩小到只有硬币厚度那么点高（不是压扁，是按比例缩小），然后被扔到一个空的玻璃搅拌

器中，搅拌刀片一分钟后就开始转动。你怎么办？

答：搅拌器应该是有空隙的，所以躲到边上应该不会被打到。但是玻璃搅拌器四周可能无法抓住

附着，所以旋转带来的风可能把你吹起来。所以尽量走到搅拌器转轴中间，试图爬上去或者抓住。

要是让你清洗整个西雅图的所有窗子，你会收取多少费用？

答：类似调音师的推理过程

怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出？

答：只能向上溢出

你要向你8岁的侄子解释什么是数据库，请用三句话完成。

答1：数据库就如存钱罐…

答2：就是你的书包，里面有你喜欢的：圣斗士金卡，小玩具；也有你不喜欢的：考卷啊，要家

长签名的东西啊。。。。反正里面各种各样的东西都有，但绝大多数可能都不是你放进去的，但

你却要注意收拾。

时钟的指针一天内会重合几次？

答：如果是没有秒针且分针不是按1分钟递进的那种钟表，那么可以重合多次（22次吧），如

果是按分钟递进的或者有秒针的，那就重合两次。另外，还要考虑齿轮的齿距和制表匠的水平。

因此从微观上讲，那两根或三根针针的很难重合。。。。。。。

你需要从A地去B地，但你不知道能不能到，这时该怎么办？

答：以目前科学水平，只要A地B地都叫得出名字并且都在地球表面的陆地上，都可以到。

好比你有一个衣橱，里面塞满了各种衬衫，你会怎么整理这些衬衫，好让你以后找衬衫的时候容

易些？

答1：优先颜色，其次款式，再次新旧程度

答2： 按季节、场合、性别分

有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎言，但

是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子一旦证明丈夫不

忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，镇上的女王宣布，至少

有一个丈夫是不忠的。这是怎么发生的呢？

答1：全部男人都被杀死

答2：国王被杀死了 (可能女王也被杀死，这样才能确保秘密不会泄露)

在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到

生下的是男孩为止。这样的国家，男女比例会是多少？

答：1 : 1 / 50%

如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过

的几率是多少 （假设为常概率条件下）

答1：1-(1-x)(1-x)(1-x)=0.95，解出x就可以了，嘿嘿

答2：0.95

答3：12度*0.25=3度

如果你看到钟的时间是3:15，那一刻时针和分针的夹角是多少？（肯定不是0度！）

答：7.5

4 个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电

筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度

都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5分钟，最慢的那个要10分

钟。他们怎样才能在17分钟内全部走过索桥？

答1：1+2先过，1（或2）返回，5+10过，2（或1）返回，1+2过

答2：最慢的10分钟在桥头打手电筒,1分钟和2分钟先过,在1分钟过完时，5分钟立刻上桥。

在2分钟过完时，10分钟拿着手电筒上桥，总共只花了12分钟就能全部过去

答3：

先1分钟和2分钟的过去，2分钟呆在那边，1分钟的回来，用了2+1=3分钟了；

5分钟和10分钟一起过去，2分钟的回来，用来3+10+2=15分钟了；

1和2分钟最后一起过去，用了15+2=17分钟了。

你和朋友参加聚会，包括你们两人在内一共有10个人在场。你朋友想跟你打赌，说这里每有一

个人生日和你相同，你就给他1元，每有一个人生日和你不同，他给你2元。你会接受么？

答1：这个题目好像有陷阱，首先自己肯定和自己生日相同，所以开始你就要给对方1元。然后

剩下9个人里面，你需要有4个人和你生日不同，你才能赚回来。而9个人里面同时有5个人

生日和你相同的概率我觉得是比较小了，所以换做我，我会接受的！

答2： 不接受

全世界有多少个钢琴调音师？

答1：2个，一个男的一个女的

答2：对客户来讲就一个，因为所作的工作一样，所以统统可以外包掉

你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次

将那个重一些的球找出来。

答1：先取6个,天平上一边3个,同重则称剩余2个即可;不同重,则取重的3个中的2个来称.

答2：将8个球按个数2，3，3任意分为三组：A、B、C。

将B、C 两组分别置于天平两端，若两端持平，即质量相等，则只需将A

组的两个球分别置于天平两端，向下倾斜的一端所盛的球即是比较重的；若两端倾斜，则将向下

倾斜的一端所盛的3个球取出，再从这3个球中任意取出两个球分别置于天平两端。如果两端

持平，那么未被抽取的那个球就比较重的；如果两端倾斜，那么向下倾斜的一端所盛的球即是比

较重的；

答3：3-3-2分称

有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他

人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能

多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）

答1： 98，0，1，0，1

答2：如果是我。。。我会提出让等级比我低的人继续按这个方法协商如何分，这样可以陷入逻

辑悖论。只要完全按这个规则，那我就死不掉。。。。。

Google面试题（八）

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随

机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它

们是完全随机的（出现概率均等）。

2. 给你一个数组]，请你在O(n)的时间里构造一个新的数组]，使得

B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

Solution:

1. 由于不知道N多大，因此不能使用[0, n]之间的等概率随机整数。遍历链表，给每个元素赋

一个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]。

Google面试题（九）

25匹马赛跑，5个跑道，怎么以最少的比赛次数来决出最快的3匹，马跑的时间未知，只知道

马的先后顺序.

思想：

（1）25匹马分为5组，进行5次赛跑；

（2）由5组第一再跑一次，这样可以选出所有马最快的那匹；

（3）由最快的那匹的分组中的第二匹、第三匹和步骤（2）中的第一匹，第二匹，以及步骤（2）

中的第三快，共五批马再跑一次

总共比赛7次

2024年4月22日发(作者：时悦宜)

硅谷流行迷题面试

近年来，越来越多的硅谷科技公司开始在面试中提出类似的问题。这些公司感兴趣的并不是

正确答案，而是应聘者解决问题的方式和能力。当今的商业世界瞬息万变，企业更需要有独立思

考能力的人才，而不仅仅是高智商、高学历的工程师。早在上世纪80年代末，微软就在面试中

引入了一些开放式的逻辑问题，例如“波音747有多重？”。微软招聘经理华伦·阿什顿(Warren

Ashton)表示：“我们希望通过这一方式考察应聘者的创造力。”

“为什么下水道的盖子是圆的？”，这是阿什顿在面试中最经常问到的一个问题。阿什顿表示，

最常见的答案是，“在任何角度下，圆的下水道盖子都不 会掉落到下水道中，而方的则不然。”

但是，一些人也提供了其它答案，例如“圆的下水道盖子容易从一个地点搬运到另一个”，或者“圆

的下水道盖子加工成本较 低”。他说：“我们希望应聘者充分发挥自己的思维和想象力，给出更

多答案。”

在硅谷高科技公司的面试中，经常会出现这类问题。谷歌前员工马克·简(Mark Jen)表示：

“雇主希望了解你在一定数量级之内能否做出准确的预计。”一般来说，优秀的应聘者会做出有根

据的推测，而不是计算准确的数字。事实上，面试 人员也正是通过考察应聘者估算的方式，来

确定最合适的人选。例如，亚马逊就经常在面试中提出这样的问题，“美国有多少个加油站？”，

或者“擦遍西雅图所有 窗户能挣多少钱？”。

当然，现在的面试远不止估算这么简单。作家、设计顾问布鲁克·埃克尔(Bruce Eckel)经

常会让应聘者用程序语言来描述一只小鸡；eBay面试人员经常会提出一个著名的逻辑问题

——“强盗分金币”：5名强盗 (A、B、C、D、E) 分100个金币。他们决定从A开始提出分配

方案，如果不能获得半数以上的支持，A将被处死，然后由B提出分配方案，依此类推。如果

每一名强盗都足够聪明， 那么A提出什么样的方案才能保证自己获得最多的金币，而且不会被

处死？

谷歌走得最远

尽管很多公司都采用了迷题面试，但没有哪家公司像谷歌这样彻底。三年前，谷歌在美国

101公路硅谷地段树立了一个醒目的广告牌，上面只有一个复杂的数学问题。如果过往行人提

交的答案正确，谷歌就会邀请他访问一个秘密网站，而这个网站上有一道更难的问题。如果答案

再次正确，谷歌将邀请他提交个人简历，并到谷歌总部参加面试。

当然，这距离应聘者正式加入谷歌还有很远的距离，至少他还要在面试中回答很多刁钻古怪

的问题。其中最常见的一个问题是：假设你的身高缩小至一枚硬币那么大，当然是按比例缩小，

密度不变。你被扔进了一个空的玻璃搅拌机里，刀片将于60秒后开始工作，你会怎么办？

并非只有应聘者需要适应这种全新的招聘方式，雇主也同样如此，他们必须面对很多从未遇

到过的问题。今年早些时候，LinkedIn创始人雷德· 霍夫曼(Reid Hoffman)开始为自己的公

司寻找一位CEO。在这一过程中，他采用了一种全新的方式来查看简历。他并没有将目光锁定

在某一个特定的候选者，而是使用 LinkedIn网络查找最合适的人选。(摩尔)

google面试题（一）

有一个random number generator，是生成真实的随机数，而不是伪随机数，这个东西会生

成几千亿个32位整数，打印出现次数前100的整数。

方法一：由于数的范围已经确定，采用计数排序的方法计算出0-2^31-1间数的出现次数，如

下代码所示:

int[] array=new int[2^31-1]；

for i=0 to n-1 do {

array[a[i]]++；

}

时间复杂度0(n),空间复杂度0(n)

接着问题就变成寻找数组array中前100大的数，可以采用类似快速排序的方式，先找第100

大的数e的位置l，然后使用快速排序的partion方法重构数组，使得l前面的数都小于e，l

后面的数都大于e，如下：

int radomize_select(int[] array, p, r, int i) { // 找第i大的数的位置

if(p==r){ // 递归出口

return array[p];

}

q=radomize_partion(A,p,r);

k<-q-p+1;

if(i<=k){

return radomize_select(array,p,q,i);

}

else{

return radomize_select(array,p,q,i-k);

}

}

时间复杂度0(n),空间复杂度0(1)

void getResult(){

int l=radomize_select(array, 0, n-1, 100);

q=partion(l); //快速排序的partion

for i=q to n-1 {

输出 array[i];

}

}

时间复杂度0(n),空间复杂度0(1)

综上，时间复杂度0(n),空间复杂度0(n)

方法二：采用哈希表, key is i, value is the count of i

Hashtable table=new Hashtable();

for i=0 to 2^31-1 do {

int count=0;

if((i)==null){

count++;

}

else{

count=++((i));

}

(i,count);

}

剩下的方法和上面一样，略

时间复杂度0(n),空间复杂度>0(n)

对比以上2种方法，时间复杂度一样，但方法一的孔间复杂度稍微小于方法二，哈希表的空间

一般情况下比普通的数组的空间要大

google面试题（二）

平面上N个点，求一条直线，穿过的点数最多

思路：2点确定一条线，N个点共有n(n-1)/2条线，穿过的点数最多的直线，斜率相同的最多，

因此只要找出相同斜率最多的点对集合，并且有公共点的即可

方法一：用上三角矩阵，矩阵里的值为任意两点的斜率，上三角矩阵用数组(n-1)/2]表

示。问题就转化为求数组中相同数最多的并且有公共点的数，方法参照“[微软面试题]请把一个

整形数组中重复的数字去掉”。

时间复杂度0(n^2)

方法二：平面上N个点以及这N个点构成的无向图，边数n(n-1)/2，对图遍历（深度或广度），

遍历到某个点node的时候，计算该点与它的前一个点的斜率r，用pr存储前一个点与它的前

结点的斜率，如果pr！=r，则返回到node，继续遍历node的下一条边，如果斜率相等，则

count++。如果找不到，则从一下结点开始遍历未访问过的节点。

时间复杂度0(n^2)

google面试题（三）

算法题一：Given 1 GB memory, input a file which contians 4 billion integers,

output one integer that is not in the file. What if you have only 10 MB

memory?

算法题二：There are 100 hundred sorted arrays, and each of them contains 100

numbers. Give an algorithm to merge them into a single sorted array, using

only one temporary array in the middle steps.

编程题：Input an integer array of size n and an integer k (k<=n), output all subsets

of size k.

思路：

(一) 整型变量的值的范围是-（2的15次方）至（2的15次方）-1，因此为数组开辟2^16

的空间，也就是64K的大小，设置一定大小的缓冲(几十K左右)，把文件读入，依次统计缓冲

区的整数出现的次数，次数为0的即位结果

(二) 使用胜者树或败者树，K=100路归并，用one temporary array来构造以及重构树。或

者

1. 取100个数组中各自的第一个数，组成一个最小堆。

2. 输出堆中的最小值，并且把这个最小值对应的数组的第二个数加入堆，并且调整。

3. 重复步骤2直到所有数组中的值都被输出。

显然前者效率较高。

空间需要为一个长度为10000的临时数组。

(三) for i=0 to n-k-1 do {

for j=i to i+k-1 do{

out(a[j]+" ");

}

out("n");

}

循环次数nk-k^2, 时间复杂度0(n)

Google面试题（四）

26个英文字母从新排序（未知的顺序alphabet），然后用这个位置的顺序给一组数据(array list)

排序现在给你这组array list，问能不能计算出来那个alphabet未知的顺序。

思路：拓扑排序就行

0. 初始排序图[G]为单个点[0]，[0]小于任何字母（添加[0]为了保证图的连通性，编

程简单），[G]为有向图。

1. 对于输入array [A]，取每个串第一个字母，去重复，得到一个有序序列[T]。将这

个串merge到排序图中，merge的方法：

a.对[T]每个字母[a_i]，如果在[G]中没有存在，则添加到[G]中。若[a_i]为[T]中

第一个字母，则添加边[a_i]->[0]，否则添加边[a_i]->[a_i-1]。

b. 如果[a_i]在[G]中已经存在，若边[a_i]->[a_i-1]（对于[a_0]为[a_0]->[0]）

不存在，添加此边。

2. 对于首字母相同的[A]中的串，去掉首字母后组成新的array [A]', 如果有空串，在

空串处splitarray。 递归调用步骤1.

结果生成：

1. 如果[G]中存在回路，输入有矛盾，无解

2. 如果[G]中的字母节点小于26个，或者存在环（除1情况外），产生不唯一的解。

3. 如果[G]是一条含有26个节点的无环路径，产生唯一解。

Google面试题（五）

几星期前，一个朋友接受了Google公司的面试，他透露了面试中的一些问题。顺便，我把从其

他几个曾经面试过的人那里听来的内容也整理在一起。最大的互联网公司Google的一份面试题

集，看看你是否能够回答出来。其中很多问题都是开放式的，正确的解答有许多种，所以在这里

就不提供答案了。

1. 一辆学校班车里面能装多少个高尔夫球？

2. 你被缩小到只有硬币厚度那么点高（不是压扁，是按比例缩小），然后被扔到一个空的

玻璃搅拌器中，搅拌刀片一分钟后就开始转动。你怎么办？

3. 要是让你清洗整个西雅图的所有窗子，你会收取多少费用？

4. 怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出？

5. 你要向你8岁的侄子解释什么是数据库，请用三句话完成。

6. 时钟的指针一天内会重合几次？

7. 你需要从A地去B地，但你不知道能不能到，这时该怎么办？

8. 好比你有一个衣橱，里面塞满了各种衬衫，你会怎么整理这些衬衫，好让你以后找衬衫

的时候容易些？

9. 有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎

言，但是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子

一旦证明丈夫不忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，

镇上的女王宣布，至少有一个丈夫是不忠的。这是怎么发生的呢？

10. 在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一

个，直到生下的是男孩为止。这样的国家，男女比例会是多少？

11. 如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆

车开过的几率是多少 （假设为常概率条件下）

12. 如果你看到钟的时间是3:15，那一刻时针和分针的夹角是多少？（肯定不是0度！）

13. 4个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分

钟的手电筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四

个人过索桥的速度都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5

分钟，最慢的那个要10分钟。他们怎样才能在17分钟内全部走过索桥？

14. 你和朋友参加聚会，包括你们两人在内一共有10个人在场。你朋友想跟你打赌，说这

里每有一个人生日和你相同，你就给他1元，每有一个人生日和你不同，他给你2元。

你会接受么？

15. 全世界有多少个钢琴调音师？

16. 你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅

称两次将那个重一些的球找出来。

17. 有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。

但其他人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让

自己拿到尽可能多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）

你觉得自己有把握去Google工作了么？

附：一些问题的候选答案

1、一辆学校巴士中可以放多少个高尔夫球？

一辆学校巴士可以塞进多少个高尔夫球？

大约50万，假设巴士有50个高尔夫球高，50个高尔夫球宽，200个高尔夫球长。

2、假如你被扔进了一个空的玻璃搅拌机里，刀片将于60秒后开始工作，你会怎么办？

如何从搅拌器中逃生？

(1)顺着度量刻度往上爬；

(2)把搅拌器的玻璃罩拧下来；

(3)利用旋转的气流“飞”出来。

3、擦遍西雅图所有窗户能挣多少钱？

假如西雅图有1万栋建筑物，每栋建筑物有600个窗户，擦一个窗户需要5分钟，收费标

准为每小时20美元，那么一共可以挣1000万美元。

Google面试题（六）

题目：对现在的Stack（栈）数据结构进行改进，加一个min()功能，使之能在常数，即O(1)，

时间内给出栈中的最小值。可对push()和pop()函数进行修改，但要求其时间复杂度都只能是

O(1)。

分析：要使pop,push,min都是O(1)，所以肯定要牺牲点空间

思路：1：在stack的数据结构中加两个个字段，如

typedef struct {

int data[MAX];

int top;

int min;

int second;

}stack;

pop,push的时候都去栈顶元素，所以是O(1)

min的时候取stack的min字段，所以也是O(1)

每次push的时候进行比较，如果当前push的元素比stack->min小，则用当前元素

替换stack->min，用原来的min替换second。如果当前push的元素比stack->min大，

但比second小，则用当前元素替换stack->second。于是达到了取min的效果，程序如下

int push(stack * s,int x){

ASSERT(s!=NULL);

if(s->top>=MAX)

{

printf("Stack overload!");

return -1;

}

s->data[s->top++]=x;

if(xmin)

s->min=x;

return 0;

}

每次pop的时候进行比较，如果pop的元素为min，则用second替换min。于是达到

了取min的效果，程序如下

int pop(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty!");

return -1;

}

(*x)=s->data[s->top--];

if(x==s->min) s->min=s->second;

return 0;

}

int min( stack *s,int *x )

{

ASSERT(s!=NULL);

(*x)=s->min;

return 0;

}

思路2：设置辅助栈ass,记录每个状态下的最小值，每次插入时，得到辅助栈当前值，和插入

的值比较

如果小则插入到最小值栈的就是它，否则就是原来的最小值，通过这种方式，pop，push，min

三个都是

O(1)算法的。

typedef struct {

int data[MAX];

int top;

}stack;

STATIC int push_stack(stack *s,int x)

{

ASSERT((s!=NULL));

if(s->top>=MAX)

{

printf("Stack overload");

return -1;

}

s->data[s->top++]=x;

return 0;

}

STATIC int pop_stack(stack *s,int *x)

{

ASSERT(s!=NULL);

if(s->top<=0)

{

printf("Stack Empty");

return -1;

}

(*x)=s->data[s->top--];

return 0;

}

int push(stack *main,stack *ass,int x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

push_stack(main,x);

if(x

{

push_stack(ass,temp);

push_stack(ass,x);

}

else

{

push_stack(ass,temp);

push_stack(ass,temp);

}

return 0;

}

int pop(stack *main,stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

int temp;

pop_stack(ass,&temp);

pop_stack(main,x);

return 0;

}

int min(stack *ass,int *x)

{

ASSERT((main!=NULL)&&(ass!=NULL));

pop_stack(ass,x);

push_stack(ass,(*x));

return 0;

}

Google面试题（七）

很多Google考生出来，也随之不少Google考试问答题目给释放出来，Google的面试题曾经

一度在网络上被粉丝和网民炒得很火热，这些题目被曝光也不止一次了。说实话，如果Google

还有点脑子的话，肯定会更换题目了。所以本次研究不是为了那些面试者而开设。只是出于粉丝

们来了解Google的一个组成部分，今天我去网上好好的搜罗了一下，如果你搜索题目，想找到

答案似乎是很难的事情：发现大部分都是转载Google考试题目的博客。内容被大量转载，导致

原来因该出现的“答案”被沉入搜索引擎的海底了。找了半天，我打算在这边建立一则文章，专门

用来收集Google考试题目和相关参考答案，方便大家研究和学习。值得一提的是，Google考

题分为几大类：日常知识型、思考型。还有一些我们甚至不知道用意是什么，凭什么拿来做面试

题… 也许在我们一起研究的同时，可以得出一些结论，如果你知道某个题目的答案或者有自己

的看法、见解直接在下面留言，我将总结到文章中去：

一辆学校班车里面能装多少个高尔夫球？

答：应该也是用常理推断过程

你被缩小到只有硬币厚度那么点高（不是压扁，是按比例缩小），然后被扔到一个空的玻璃搅拌

器中，搅拌刀片一分钟后就开始转动。你怎么办？

答：搅拌器应该是有空隙的，所以躲到边上应该不会被打到。但是玻璃搅拌器四周可能无法抓住

附着，所以旋转带来的风可能把你吹起来。所以尽量走到搅拌器转轴中间，试图爬上去或者抓住。

要是让你清洗整个西雅图的所有窗子，你会收取多少费用？

答：类似调音师的推理过程

怎么才能识别出电脑的内存堆栈是向上溢出还是向下溢出？

答：只能向上溢出

你要向你8岁的侄子解释什么是数据库，请用三句话完成。

答1：数据库就如存钱罐…

答2：就是你的书包，里面有你喜欢的：圣斗士金卡，小玩具；也有你不喜欢的：考卷啊，要家

长签名的东西啊。。。。反正里面各种各样的东西都有，但绝大多数可能都不是你放进去的，但

你却要注意收拾。

时钟的指针一天内会重合几次？

答：如果是没有秒针且分针不是按1分钟递进的那种钟表，那么可以重合多次（22次吧），如

果是按分钟递进的或者有秒针的，那就重合两次。另外，还要考虑齿轮的齿距和制表匠的水平。

因此从微观上讲，那两根或三根针针的很难重合。。。。。。。

你需要从A地去B地，但你不知道能不能到，这时该怎么办？

答：以目前科学水平，只要A地B地都叫得出名字并且都在地球表面的陆地上，都可以到。

好比你有一个衣橱，里面塞满了各种衬衫，你会怎么整理这些衬衫，好让你以后找衬衫的时候容

易些？

答1：优先颜色，其次款式，再次新旧程度

答2： 按季节、场合、性别分

有个小镇有100对夫妇，每个丈夫都在欺骗他的妻子。妻子们都无法识破自己丈夫的谎言，但

是她们却能知道其他任何一个男人是否在撒谎。镇上的法律规定不准通奸，妻子一旦证明丈夫不

忠就应该立刻杀死他，镇上所有妇女都必须严格遵守这项法律。有一天，镇上的女王宣布，至少

有一个丈夫是不忠的。这是怎么发生的呢？

答1：全部男人都被杀死

答2：国王被杀死了 (可能女王也被杀死，这样才能确保秘密不会泄露)

在一个重男轻女的国家里，每个家庭都想生男孩，如果他们生的孩子是女孩，就再生一个，直到

生下的是男孩为止。这样的国家，男女比例会是多少？

答：1 : 1 / 50%

如果在高速公路上30分钟内到一辆车开过的几率是0.95，那么在10分钟内看到一辆车开过

的几率是多少 （假设为常概率条件下）

答1：1-(1-x)(1-x)(1-x)=0.95，解出x就可以了，嘿嘿

答2：0.95

答3：12度*0.25=3度

如果你看到钟的时间是3:15，那一刻时针和分针的夹角是多少？（肯定不是0度！）

答：7.5

4 个人晚上要穿过一座索桥回到他们的营地。可惜他们手上只有一支只能再坚持17分钟的手电

筒。通过索桥必须要拿着手电，而且索桥每次只能撑得起两个人的份量。这四个人过索桥的速度

都不一样，第一个走过索桥需要1分钟，第二个2分钟，第三个5分钟，最慢的那个要10分

钟。他们怎样才能在17分钟内全部走过索桥？

答1：1+2先过，1（或2）返回，5+10过，2（或1）返回，1+2过

答2：最慢的10分钟在桥头打手电筒,1分钟和2分钟先过,在1分钟过完时，5分钟立刻上桥。

在2分钟过完时，10分钟拿着手电筒上桥，总共只花了12分钟就能全部过去

答3：

先1分钟和2分钟的过去，2分钟呆在那边，1分钟的回来，用了2+1=3分钟了；

5分钟和10分钟一起过去，2分钟的回来，用来3+10+2=15分钟了；

1和2分钟最后一起过去，用了15+2=17分钟了。

你和朋友参加聚会，包括你们两人在内一共有10个人在场。你朋友想跟你打赌，说这里每有一

个人生日和你相同，你就给他1元，每有一个人生日和你不同，他给你2元。你会接受么？

答1：这个题目好像有陷阱，首先自己肯定和自己生日相同，所以开始你就要给对方1元。然后

剩下9个人里面，你需要有4个人和你生日不同，你才能赚回来。而9个人里面同时有5个人

生日和你相同的概率我觉得是比较小了，所以换做我，我会接受的！

答2： 不接受

全世界有多少个钢琴调音师？

答1：2个，一个男的一个女的

答2：对客户来讲就一个，因为所作的工作一样，所以统统可以外包掉

你有8个一样大小的球，其中7个的重量是一样的，另一个比较重。怎样能够用天平仅称两次

将那个重一些的球找出来。

答1：先取6个,天平上一边3个,同重则称剩余2个即可;不同重,则取重的3个中的2个来称.

答2：将8个球按个数2，3，3任意分为三组：A、B、C。

将B、C 两组分别置于天平两端，若两端持平，即质量相等，则只需将A

组的两个球分别置于天平两端，向下倾斜的一端所盛的球即是比较重的；若两端倾斜，则将向下

倾斜的一端所盛的3个球取出，再从这3个球中任意取出两个球分别置于天平两端。如果两端

持平，那么未被抽取的那个球就比较重的；如果两端倾斜，那么向下倾斜的一端所盛的球即是比

较重的；

答3：3-3-2分称

有5个海盗，按照等级从5到1排列。最大的海盗有权提议他们如何分享100枚金币。但其他

人要对此表决，如果多数反对，那他就会被杀死。他应该提出怎样的方案，既让自己拿到尽可能

多的金币又不会被杀死？（提示：有一个海盗能拿到98%的金币）

答1： 98，0，1，0，1

答2：如果是我。。。我会提出让等级比我低的人继续按这个方法协商如何分，这样可以陷入逻

辑悖论。只要完全按这个规则，那我就死不掉。。。。。

Google面试题（八）

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随

机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它

们是完全随机的（出现概率均等）。

2. 给你一个数组]，请你在O(n)的时间里构造一个新的数组]，使得

B[i]=A[1]*A[2]*...*A[n]/A[i]。你不能使用除法运算。

Solution:

1. 由于不知道N多大，因此不能使用[0, n]之间的等概率随机整数。遍历链表，给每个元素赋

一个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]。

Google面试题（九）

25匹马赛跑，5个跑道，怎么以最少的比赛次数来决出最快的3匹，马跑的时间未知，只知道

马的先后顺序.

思想：

（1）25匹马分为5组，进行5次赛跑；

（2）由5组第一再跑一次，这样可以选出所有马最快的那匹；

（3）由最快的那匹的分组中的第二匹、第三匹和步骤（2）中的第一匹，第二匹，以及步骤（2）

中的第三快，共五批马再跑一次

总共比赛7次