【转贴】面经之GOOGLE

Google笔经

笔试题目：9道单选+3道问答
时间：100分钟
我做的是B卷。
单选题：
1，求两个二进制数的异或值，基本上学过一点计算机的东西的人都能对的题目。。
2，不记得了。。也是不需要思考的题目。。
3，大概是如下的函数：
int someFunc(int x){
  if (x == 0)
    return 0;
  else
    return x + someFunc(x - 1);
}
问这个计算的是什么。。。
4，不记得了。。不需要思考吧。。
5，不记得了。。不需要思考吧。。
6，参见2，4，5。。
7，似乎需要思考一下。。
8，问链表结构和数组相比的优势不包括哪项，
包括：
插入的时间
删除的时间
存储空间
剩下两个不记得了。。
9，如下函数：
T(x) = 1 (x <= 1)
T(n) = 25 T(n/5) + n^2
问T(n)随n的增长。
选项大概是这样的：
O(n^2)，O(n^2logn)等等的。。

问答：
1，写两个N*N的矩阵的乘法，给出了C的格式，你可以选择你喜欢的语言去写。。
int* multi(int* a1, int* a2, int N){
}
2，寻找一个单向链表的中项，如果存在两个则返回前一个。给出了C的格式，同样你可
以选择。。。。
struct {
  Node* next;
  int value;
} Node;
Node* someFunc(Node* head){
}
3，给一个长度为n的整数数组，只允许用乘法不允许用除法，计算任意(n-1)个数的组合
乘积中最大的一组。。。写出算法的时空复杂度。
ps：怀疑这道题目出错啦。。虽然我也做错了。。。。。。


一些补充：
1，问答的第一题是google上学期 intern的大题原题；
2，google很喜欢考链表，无论intern的面试以及两次的笔试都有这样的题目；
3，google一般大题第三道都是写算法的时空复杂度；
4，选择题基本上偏简单，但是要做得准确率高似乎并不那么容易；
5，根据传言，小道消息，人云亦云以及以讹传讹，google的高速审卷政策来源于审卷时
以选择题为主，如果你全对啦，那么恭喜你pass啦；如果你错了好几道，那么下次努力
吧，如果还有下次。。。大题基本是做参考的。。。
6，选择题很多记不清了，因为一遍做下来的，回去随便扫了两眼。。。加上过了这几个
小时，记不得了。希望大家补充修正以及修改。。。
7，google会在11号开始3天内发面试通知，据小道消息等等，有四轮面试。bless大家~~

--
※ 来源:•饮水思源 bbs.sjtu.edu.cn

Google电面


今天早上十点一刻准时电话响起，还是前天打电话来的那个姐姐Jane Huang，很温柔的声音
。十五分钟，英语。我先寒暄了一下上次的nice talking，就进入正题了。
首先会问你有没有投过其他的什么公司。我如实答了，投了一些。接着就问你目前有没有收
到offer，没有，也是如实答的――估计收到了也要答没有吧… 然后是你什么时候毕业，什
么时候能够进行工作。之后是你的major，GPA。我老老实实说，GPA＝3.76，先汗一个…她
问“out of 4?” “…out of 5…”好寒！所以告诉低年级的ddmm们，一定要好好学习！我就巨后悔无比。
这些问完之后就进入正题了，因为当时有点紧张，现在凭印象记下来的大概就是这么四个问题。
你为什么应聘Adwords / customer service?
你为什么适合这个职位？
你对Adwords的理解？
如果你要向一个客户解释什么是Adwords，以及有哪些特点，你会怎么说？
15分钟很快就过去了，她也问完了，就告诉我过一段时间会跟我联系接下来的事情，如果前面的测试能够通过的话。叫我有什么问题就发邮件给她，很nice。
我面的不太好，全当做梯子了。
明天要面的同学不要紧张，就是这些问题，大概也逃不了多远，认真准备一些就好了。之前看一下google adwords的介绍，多了解一下它的文化，差不多就够了。
就是这些了，新鲜出炉的，还带着体温呢。希望给大家有些帮助
PS：电话是从California总部那边打过来的，我上网查了一下时差是16个小时，也就是说，给我打电话的时候，那边是下午6点多钟，

Google面试题

今年10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa
》、《今日物理》等几本专业杂志上刊登了一份“Google实验室能力倾向测试”的
试卷，开头蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观
，并成为我们其中一员”。有兴趣的人可以做完了邮寄给Google公司，也许会得到
一个工作机会呢。
　　1、解答下面的隐藏等式，其中的M和E的值可以互换，但不允许第一位是0：

　　WWWDOT - GOOGLE = DOTCOM
　　2、用一个俳句(一种日本短诗，每句有一个与季节有关的词)来建立模型，借
此预测网络搜索流量的季节性变化；
　　3、
　　1
　　1 1
　　2 1
　　1 2 1 1
　　1 1 1 2 2 1
　　下一行是什么？
　　4、你正处于一个全部由崎岖小路构成的迷宫里，手里有一个满是灰尘的笔记
本，可以无线上网，但是信号很弱。与此同时，一些阴森可怕、毫无生气的妖怪在
你身边游荡。你会怎么做呢？
　　(1)毫无目的的四处游荡，到处碰壁，直到被迷宫里的妖怪吃掉。
　　(2)用笔记本作为挖掘工具，打穿地面直接进入下一关。
　　(3)玩网络游戏《魔法骑兵》，直至电池耗尽，你也心灰意冷。
　　(4)使用笔记本画出迷宫的节点地图，找到出路。
　　(5)发送简历给Google，告诉主管妖怪你选择退出，随后你就回到现实世界。

　　5、Unix有何缺陷？你准备如何补救？
　　6、在Google工作的第一天，你发现身边的同事竟然是研究生一年级课本的作
者，你会：
　　(1)主动示好并索取签名。
　　(2)不改变坐姿，但放轻打字声音，避免影响她的工作和思考。
　　(3)把你每天的麦片和咖啡都留给她享用。
　　(4)在她所写的书中找到你最喜欢的内容，并告诉她这些内容已经成为你的座
右铭。
　　7、下列哪句话最贴切的表达了Google的企业文化？
　　(1)我感到很幸运。
　　(2)不要干坏事。
　　(3)哦，我已经解决了那个问题。
　　(4)你身边50英寸之内，必定能找到食物。
　　(5)以上皆是。
　　8、用3种颜色为20面体上色，每个面一种颜色，有多少种组合？你会选择哪些
颜色？
　　9、下面是故意留出的空白，请将其填满，使之看起来不那么空。
　　10、用1欧姆的电阻组成无限大的两维矩阵，“象棋跳马步”(“日”字对角点
)两点之间的电阻是多少？
　　11、现在是星期日下午2点，你正在旧金山著名的湾区。你可以选择去国家公
园的红杉林里徒步旅行，或者参观城市里的文化景观。你会怎么做？
　　12、你认为最美的数学等式是什么？
　　13、下列哪个团体没有在Google员工中形成？
　　(1)女子篮球
　　(2)淡黄色爱好者
　　(3)Cricketeers
　　(4)诺贝尔奖获得者
　　(5)葡萄酒俱乐部
　　14、搜索技术的下一个革命性突破是什么？
　　15、一个项目组由多少人构成才能达到最优规模？也就是说，一旦超过这一数
字，每增加一个成员项目组的平均生产力就会相应下降。
　　(1)1个
　　(2)3个
　　(3)5个
　　(4)11个
　　(5)24个
　　16、给你一个三角形ABC，请用圆规和尺找出点P，保证三角形ABP、ACP和BCP
周长相等。
　　17、有这样一个函数，对于任意整数n，都能返回写出0到n之间出现“1”的个
数。例如，f（13）=6。请注意f（1）=1，那么下一个能实现f（n）=n的最大数字
是什么？
　　18、你编写的最酷的黑客程序是什么？
　　19、在下面的数列中，下一个数字是多少：10, 9, 60, 90, 70, 66,?
　　(1)96
　　(2)10的100次方
　　(3)以上皆是
　　(4)以上皆不是
　　20、用少于29个词，描述你能带给Google实验室带来的贡献。

另一个Google电面经历

发信站: 饮水思源 (2005年11月12日01:29:33 星期六)
09月底或者10月初投的resume，都快忘了这码事了，突然11月02日接到一个电话，就是前面贴子提到的那个回电说空号的那个号码，一个估计是hr的mm通知说11月04日上午09时有个电话interview，之前也没自报家门，难怪前面那位老兄会当成骚扰电话挂掉，
cmft...11月04日上午09时10分接到电话，来电显示是+1951101，面试官是身在Mountain View的华人，在Google做Software Engineer，中文面试。开头先是寒暄几句，问了问做 过的最得意的项目和最大的项目分别是什么，然后进入正题，第一个题目问一个二叉树，把它所有节点打印出来，我一开始以为是要在终端印出一个树型的样子，所以就说广度优先，然后他讲只要把所有节点打印出来即可，就是一个普通的遍历，他要我写出代码，然后一个字符一个字符读给他听，我写了几行，懒得写了，就直接讲给他听，说先定义一个struct tree_t，里面三个成员，叫value，left和right，然后定义一个函数叫process，里面三行代码叫print value，process(left)和process(right)，就ok了，给果让他抓了把柄，说这是个infinite的递归，很ft很弱智的疏忽，偶说偶对电面不太适应，难以集中精神思考，事实上的确如此，改了if NULL的问题，他又问给出两个节点，要求它们在这 个binary tree里面的最深层的公共节点，我思考了大约几秒钟，很快回答说只要在 process返回一个值，如果left和right又一个等于给出的节点，就返回true，否则返回 false，当检测到process(left)和process(right)都是true，那个结点就是所就结点，结果又让他抓了把柄，问value怎么办，只好认输，更正说检测left和right的同时再检测一下value。他又问如果给出N个节点，求它们的公共结点又如何，这次我几乎马上就说只要不返回boolean型，而是返回一个整数就ok了，他最后问道这种先打印value的递归怎么称呼，我回答前序遍历，他把这个词用英文对我重复了一遍，换第二个问题。他先问对网络协议是否熟悉，如果不熟悉可以换题，我说我对HTTP协议比较熟，于是他问TCP连接建立 时，客户端和服务器端是如何交互的，我以前做过sniffer，所以对TCP还比较了解，于是答三次握手，客户端先请求服务器，服务器返回，客户端再请求，他问这三个请求的具体细节，他一边问我一边就打开了http://en.wikipedia.org/wiki/TCP，凭借快速在网上搜索信息的技巧，找到了SYN/ACK的具体细节讲给他听，他又问TCP header都会有什么数据 成员，我一时手忙脚乱，竟一时没从那网页里找到相关的内容，就凭感觉说一定会有端口，而且是两个，source和destination，又说应该没有ip，ip应该在ip层里面，他又问还 会有什么，我凭以前sniffer的印象，说应该还有序列号和checksum，他问序列号英文叫 什么，我一时想不出，就快速搜索wikipedia上面的文字，看sequence number比较像他问的，就说给他听，然后他问seq num有什么用，我以前搞过p2p protocol，所以比较容易猜到seq num在网络协议里面的一般用途，说是确认ACK时该ACK哪个seq num的packet，他听了似乎比较满意，说你了解的东西还蛮广泛的。第三道题目他先是说这东西可能没用，说stack和queue哪个更基本一些，我马上说stack，并告诉他我知道是stack，但不知道为什么是stack，他又具体举了个例子，说1和-1哪个更基本，我几乎没思考就说是1，他说 是-1，因为-1*-1可以得到1，而1怎么也得不到-1，我辩解说这要看你怎么定义“基本” 这个词，于是他回到了stack和queue，说其中一个可以模拟另一个，而反之不行，我重复了他的问题，说等同于系统只提供了stack这个数据结构，没有提供queue，要我用stack 模拟queue，但是最后我绕了一大圈，把问题搞得很复杂，甚至往hanoi方向上想，也没想出如何解决这个问题，当然挂了电话以后很快就知道怎么弄了，一只手拿着电话听筒确实没法思考...

最后他问有一个random number generator，是生成真实的随机数，而不是伪随机数，这个东西会生成几千亿个32位整数，要我打印数出现次数前100的整数，我马上 就说我的方法空间效率很差，但是这是唯一我能很快想到的办法，就是建一个4294967296个元素的数组，读generator，然后说如果你要前100，我会循环100次逐一找出，如果你 要前10000或者更多，我会先做一下排序，因为排序是O(nlogn)，可能对于top N，N比较 大时会更好些，但N多大采用快排要实验决定，他说他只是想到了快排，并对我提出N比较小时逐一找出表示赞同，他又问还有没有更好的办法，我这时不知道想到哪了，胡说一通哪也不挨哪的方法，说完发现把他之前问题的原意搞混了，于是说恐怕没有好很多的办法，但可以细节上进行优化。他问如果我不要精确解，而是要近似解又该如何，我说可以随机从生成器抽取样本，不必把所有数据都进行处理，这样可以大大提高排序的效率。一共就是这四个问题，答得还算马马虎虎，事先说要45分钟的interview整整花了1小时53分1 秒，偶的电话是全球通，耗资45.60元，不过最后pass了，大概就是这个样子...

Google 面试归来


今天下午去 google 面试了。不出意外的话，这应该是我近期最后一次面试了，所以来
写写感受。
原本以为是需要去北京的，还指着他们报销飞机票呢，没想到 google 居然在上海世纪
商贸广场租了一层楼当办公室专门负责面试。可惜啊，没有花到他们的钱，也没有能够
去北京看看有没有熔岩灯。
嗯嗯，总的来说 Google 的面试题确实水平不错，感觉比微软的强一些，不过面试人员
方面就要差些 —— 倒不是说他们水平不足，而是其中大部分人应该是比较纯粹的工程
师，不善于把握面试的节奏和主动权，一般学生还好，遇到我这种职场上混过两年的油
条，话题就很容易被我牵到我的强项上去。其中只有一位女士，应该三十出头了，明显
在这方面很有经验，节奏把握得很好，有一种缓缓给我压力的感觉，技术方面也很棒，
应该是项目经理这样的角色，给我留下了深刻印象。
过程方面，一共是五轮面试，每轮大约四十五分钟到一个小时，五轮结束之后再有 HR
人员过来和你“总结陈词”。让我比较不满的一点是居然不象微软那样当场能够知道结
果，而且我询问薪资福利水平的时候，全部推到美国总部那边去，说是要让他们来决定
…… 看来 google 中国这里是自主权比较小的。不过好进入这个流程之后 google 工作
效率不错，当初电面完了之后第三天就给我发了面试通知，这次 HR 也保证两周之内可
以给我答复。
回过头来说内容方面。前面说了，google 的面试题水准不错，考察比较全面而且有一定
深度。其中有几道题目还是比较开放的，可以说没有标准答案，面试人员技术水准也值
得信任，这里可以跟着你的解法下去，和你讨论这里面的优劣，给我的感觉很好。不过
google 的面试题几乎全部是算法题和趣味数学题，我遇到的唯一一道和具体语言相关的
题目也是问我两个标准容器在数据结构上的优劣。当然啦，编程功底还是很重要的，有
两轮面试都要求我当场给出实现（说真的，实在是不习惯在纸上写程序）。只有那位给
我留下了深刻印象的女士，她主持的那一轮，在问过我的工作经历之后，针对我的一个
项目，从架构设计这个角度问了我一些问题，关于组合和继承，关于设计模式。不过她
见我掰活得很顺（和 ajoo 吵架练出来的），也就点到为止，然后给我出了一道很难的
趣味数学题蹂躏了我一番 …… 这是唯一一道我要靠提示才能走上正确方向的面试题。
具体面试题恕我不能透露了：google 很重视这个，专门让我签了一份 NDA 承诺不透露
这方面信息 ……
嗯嗯，总的来说面试是很愉快的，工程师之间总是很好打交道，那位“疑似经理”女士
给我的感觉也很好。特别舒服的一条是我可以用中文，哇啦咧，这实在是太爽了。本人
属于英文废柴，一到英语环境就需要分出心神来“编码解码”，这次碰到中文面试可以
全力投入思考感觉真是太好了 —— 这次 google 面试题要比微软的难，而且因为照顾
小猫也没时间睡个午觉养精蓄锐，但是我做面试题时候的表现却要好得多。另外从我面
试时探听的口风来看，google 中国独立性很低，或者这么说吧，google 现在还是把全
球所有的分部当作一个整体来管，另外一点比较让我失望的是，貌似近期没有在上海开
分部的打算。可惜的是，没有有关薪酬的任何信息 —— 哪位如果已经被录用了，出来
说说？
大致就是如此吧，两周之后如果有更多的消息，再说。

google的21道面试问题


10月底，Google在美国《麻省技术评论》、《LinuxJournal》、《Mensa》、《今日物理》
等几本专业杂志上，刊登了一份“Google实验室能力倾向测试”。
　　试卷开头，蛊惑地写着“试试看！把答案寄回Google，你有希望去Google总部参观，
并成为我们其中一员”。
  这些题目，虽然古怪，但是也不算有困难，有兴趣的人可以做完了邮寄给google公司
，也许会得到一个工作机会呢。

1. Solve this cryptic equation, realizing of
course that values for M and E could be
interchanged. No leading zeros are allowed.
WWWDOT - GOOGLE = DOTCOM
2. Write a haiku describing possible methods
for predicting search traffic seasonality.
3.
1
1 1
2 1
1 2 1 1
1 1 1 2 2 1
What is the next line?
4. You are in a maze of twisty little passages,
all alike. There is a dusty laptop here with a
weak wireless connection. There are dull,
lifeless gnomes strolling about. What dost
thou do?
A) Wander aimlessly, bumping into
obstacles until you are eaten by a grue.
Use the laptop as a digging device to
tunnel to the next level.
C) Play MPoRPG until the battery dies
along with your hopes.
D) Use the computer to map the nodes
of the maze and discover an exit path.
E) Email your resume to Google, tell the
lead gnome you quit and find yourself
in whole different world.
5. What''s broken with Unix?
How would you fix it?
6. On your first day at Google, you discover
that your cubicle mate wrote the textbook
you used as a primary resource in your first
year of graduate school. Do you:
A) Fawn obsequiously and ask if you
can have an autograph.
Sit perfectly still and use only soft
keystrokes to avoid disturbing her
concentration.
C) Leave her daily offerings of granola
and English toffee from the food bins.
D) Quote your favorite formula from the
textbook and explain how it''s now
your mantra.
E) Show her how example 17b could
have been solved with 34 fewer lines
of code.
7. Which of the following expresses Google□
over-arching philosophy?
A) "I''m feeling lucky"
"Don''t be evil"
C) "Oh, I already fixed that"
D) "You should never be more than
50 feet from food"
E) All of the above
8. How many different ways can you color an
icosahedron with one of three colors on
each face?
What colors would you choose?
9. This space left intentionally blank. Please fill it
with something that improves upon emptiness.
10.On an infinite, two-dimensional, rectangular
lattice of 1-ohm resistors, what is the
resistance between two nodes that are a
knight''s move away?
11.It''s 2 PM on a sunny Sunday afternoon in the
Bay Area. You''re minutes from the Pacific
Ocean, redwood forest hiking trails and world
class cultural attractions. What do you do?
12.In your opinion, what is the most beautiful
math equation ever derived?
13. Which of the following is NOT an actual
interest group formed by Google employees?
A. Women''s basketball
B. Buffy fans
C. Cricketeers
D. Nobel winners
E. Wine club
14.What will be the next great improvement in
search technology?
15.What is the optimal size of a project team,
above which additional members do not
contribute productivity equivalent to the
percentage increase in the staff size?
A) 1
3
C) 5
D) 11
E) 24
16.Given a triangle ABC, how would you use only
a compass and straight edge to find a point P
such that triangles ABP, ACP and BCP have
equal perimeters? (Assume that ABC is
constructed so that a solution does exist.)
17.Consider a function which, for a given whole
number n, returns the number of ones required
when writing out all numbers between 0 and n.
For example, f(13)=6. Notice that f(1)=1. What
is the next largest n such that f(n)=n?
18.What''s the coolest hack you''ve ever written?
19.''Tis known in refined company, that choosing
K things out of N can be done in ways as
many as choosing N minus K from N: I pick K,
you the remaining.
Find though a cooler bijection, where you show
a knack uncanny, of making your choices contain
all K of mine. Oh, for pedantry: let K be no more
than half N.
20.What number comes next in the sequence:
10, 9, 60, 90, 70, 66,?
A)96
1000000000000000000000000000000000
0000000000000000000000000000000000
000000000000000000000000000000000
C) Either of the above
D) None of the above
21.In 29 words or fewer, describe what you
would strive to accomplish if you worked
at Google Labs.

google的待遇


一个朋友入职了

背景 一流大学CS硕士毕业 跨国软件公司实习半年
应征职位 software engineer
面试笔试一堆（包括从美国打来的越洋长途提问），最后是面见李开富 加工作餐一顿（他说大约是收50个关门弟子，但个人认为李替google炒作的味道太重）
月薪 16k左右
其它福利：google的股票40股 （现在市值超过400$ 每股）， 美国培训机会，李开复帮助职业规划（又是炒作的味道浓）

总的来说google的福利还是很不错的，现在钱多得用不完。 李开复回来筹备google中国研究院大约半年后应该可以开始运行了，想投身google的可以去试试，现在正是他们大把招聘的时候。