解析Google的⾯试题
某猎头收集了140多个Google的⾯试题，都张到他的Blog中了，主要是下⾯这些职位的，因为被墙，且⽆任何敏感信息，所以，我原⽂搬过来了。
1. Product Marketing Manager
2. Product Manager
3. Software Engineer
4. Software Engineer in Test
5. Quantitative Compensation Analyst
6. Engineering Manager
7. AdWords Associate
这篇Blog例举了Google⽤来⾯试下⾯这⼏个职位的⾯试题。很多不是很容易回答，不过都⽐较经典与变态，是
Google，Microsoft，Amazon之类的公司的风格。对于本⽂，我没有翻译，因为我相信，英⽂问题是最好的。不过对于有些问题，我做了⼀些注释，不⼀定对，但希望对你有帮助启发。对于⼀些问题，如果你百思不得其解，可以Google⼀
下，StackOverflow或是Wikipedia上可能会给你⾮常全⾯的答案。
Product Marketing Manager
8. Why do you want to join Google?
9. What d o you know about Google’s product and technology?
10. If you are Product Manager for Google’s Adwords, how do you plan to
market this?
11. What would you say during an AdWords or AdSen product minar?
12. Who are Google’s competitors, and how does Google compete with them?
13. Have you ever ud Google’s products? Gmail?
14. What’s a creative way of marketing Google’s brand name and product?
15. If you are the product marketing manager for Google’s Gmail product, how
do you plan to market it so as to achieve 100 million customers in 6
months?
16. How much money you think Google makes daily from Gmail ads?
17. Name a piece of technology you’ve read about recently. Now tell me your
own creative execution for an ad for that product.
18. Say an advertir makes $0.10 every time someone clicks on their ad.
Only 20% of people who visit the site click on their ad. How many people need to visit the site for the advertir to make $20?
19.
20. Estimate the number of students who are college niors, attend four-year
schools, and graduate with a job in the United States every year.
Product Manager
21. How would you boost the GMail subscription ba?
22. What is the most efficient way to sort a million integers? （陈皓：merge
sort）
23. How would you re-position Google’s offerings to counteract competitive
threats from Microsoft?
24. How many golf balls can fit in a school bus? （陈皓：这种题⼀般来说是考
你的解题思路的，注意，你不能单纯地把⾼尔夫球当成⼀个⼩⽴⽅体，其是⼀个圆球，堆起来的时候应该是错开的——也就是三个相邻的球的圆⼼是个等边三⾓形）
25. You are shrunk to the height of a nickel and your mass is proportionally
reduced so as to maintain your original density. You are then thrown into an empty glass blender. The blades will start moving in 60 conds. What do you do?
26. How much should you charge to wash all the windows in Seattle?
27. How would you find out if a machine’s stack grows up or down i n memory?
28. Explain a databa in three ntences to your eight-year-old nephew. （陈
皓：⽤三句话向8岁的侄⼦解释什么是数据库，考你的表达能⼒了）
29. How many times a day does a clock’s hands overlap?（陈皓：经典的时钟
问题）
30. You have to get from point A to point B. You don’t know if you can get
there. What would you do?
31. Imagine you have a clot full of shirts. It’s very hard to find a shirt. So
what can you do to organize your shirts for easy retrieval? （陈皓：很不错的⼀道题，不要以为分类查询很容易，想想图书馆图书的分类查询问题吧。
另外，你处想想如何在你在你的⾐柜⾥实现⼀个相当于Hash表或是⼀个Tree之类的数据结构）
32. Every man in a village of 100 married couples has cheated on his wife.
Every wife in the village instantly knows when a man other than her
husband has cheated, but does not know when her own husband has. The village has a law that does not allow for adultery. Any wife who can prove that her husband is unfaithful must kill him that very day. The women of the village would never disobey this law. One day, the queen of the village
visits and announces that at least one husband has been unfaithful. What happens? （陈皓：这个问题很有限制级，哈哈，⾮常搞的⼀个问题，注意wife们的递归，这类的问题是经典的分布式通讯问题，上⽹搜⼀搜吧。）答案：这是⼀个典型的递归问题。⼀旦所有的妻⼦都知道⾄少有⼀个男⼈出轨，我们就可以按递归⽅
式来看待这个流程。先让我们假设只有⼀个丈夫偷情。则他的妻⼦见不到任何偷情的男⼈，因此知道
这个⼈就是⾃⼰丈夫，她当天就会杀了他。假如有两个丈夫偷情，则他俩的妻⼦只知道不是⾃⼰丈夫
的那⼀个男⼈偷情。因此她会等上⼀天看那个⼈有没有被杀死。假如第⼀天没⼈被杀死，她就能确定
她⾃⼰的丈夫也偷了情。依此类推，假如有100个丈夫偷情，则他们能安全活上99天，直到100
天时，所有妻⼦把他们全都杀死。
33. In a country in which people only want boys, every family continues to
have children until they have a boy. If they have a girl, they have another child. If they have a boy, they stop. What is the proportion of boys to girls in
the country?（陈皓：第⼀反应是——这个国家是中国。⼀个概率问题，其实，⽆论你怎么⽣，50%的概率是永远不变的。）
34. If the probability of obrving a car in 30 minutes on a highway is 0.95,
what is the probability of obrving a car in 10 minutes (assuming constant default probability)?
答案：这题的关键在于0.95是见到⼀辆或多辆汽车的概率，⽽不是仅见到⼀辆汽车的概率。在30分钟内，见不到任何车辆的概率为0.05。因此在10分钟内见不到任何车辆的概率是这个值的⽴⽅根，⽽在10分钟内见到⼀辆车的概率则为1减去此⽴⽅根，也就是⼤约63%。
35. If you look at a clock and the time is 3:15, what is the angle between the
hour and the minute hands? (The answer to this is not zero!)
36. Four people need to cross a rickety rope bridge to get back to their camp
at night. Unfortunately, they only have one flashlight and it only has
enough light left for venteen minutes. The bridge is too dangerous to
cross without a flashlight, and i t’s only strong enough to support two
people at any given time. Each of the campers walks at a different speed.
One can cross the bridge in 1 minute, another in 2 minutes, the third in 5 minutes, and the slow poke takes 10 minutes to cross. How do the
campers make it across in 17 minutes?（陈皓：经典的过桥问题）
答案：1和2⼀起过（2分钟）；1返回（3分钟）；5和10⼀起过（13分钟）；2返回（15分钟）；
1和2⼀起过（17分钟）。全体安全过桥。
37. You are at a party with a friend and 10 people are prent including you
and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he
finds that does not have the same birthday as you, he gets $2. would you accept the wager?
答案：不算闰年的话，别⼈跟你⽣⽇相同的概率是1/365；跟你⽣⽇不同的概率是364/365。因此不要打这个赌。
38. How many piano tuners are there in the entire world?
39. You have eight balls all of the same size. 7 of them weigh the same, and
one of them weighs slightly more. How can you find the ball that is heavier by using a balance and only two weighings?（陈皓：经典的称重问题。这样的问题花样很多，不过都不难回答）
40. You have five pirates, ranked from 5 to 1 in descending order. The top
pirate has the right to propo how 100 gold coins should be divided
among them. But the others get to vote on his plan, and if fewer than half agree with him, he gets killed. How should he allocate the gold in order to maximize his share but live to enjoy it? (Hint: One pirate ends up with 98 percent of the gold.) 41. You are given 2 eggs. You have access to a 100-story building. Eggs can
be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100th floor. Both eggs are
identical. You need to figure out the highest floor of a 100-story building an egg can be dropped without breaking. The question is how many drops you need to make. You are allowed to break 2 eggs in the process. （陈皓：
从3的倍数的楼层开始扔，⽐如3，6，9，12…..，如果鸡蛋在3n层碎了，那到在3n-1层扔第⼆个鸡蛋，如果没碎，则最⾼不碎楼层为3n-1，否则为3n-2）
42. Describe a technical problem you had and how you solved it.
43. How would you design a simple arch engine?
44. Design an evacuation plan for San Francisco.
45. There’s a latency p roblem in South Africa. Diagno it. （陈皓：这个问题
完全是在考你的解决问题的能⼒。没有明确的答案。不过，解决性能问题的第⼀步通常是找出瓶颈，找瓶颈有很多种⽅法，⼯具，⼆分查，时间记录等等。）
46. What are three long term challenges facing Google?
47. Name three non-Google websites that you visit often and like. What do you
like about the ur interface and design? Choo one of the three sites
and comment on what new feature or project you would work on. How
would you design it?
48. If there is only one elevator in the building, how would you change the
design? How about if there are only two elevators in the building? （陈皓：经典的电梯设计问题，这种问题千变万化，主要是考你的设计能⼒和需求变化的适变能⼒，与此相似的是酒店订房系统。）
49. How many vacuum’s are made per year in USA?
Software Engineer
50. Why are manhole covers round? （陈皓：为什么下⽔井盖是圆的？这是有
N种答案的，上Wiki看看吧）
51. What is the difference between a mutex and a maphore? Which one
would you u to protect access to an increment operation?
52. A man pushed his car to a hotel and lost his fortune. What happened? （陈
皓：脑筋急转弯？他在玩⼤富翁游戏）
53. Explain the significance of ―dead beef‖.（陈皓：要是你看到的是16进制
DEAD BEEF，你会觉得这是什么？IPv6的地址？）
孟永辉：调试器对特定类型内存的填充或调试时的某种标识，为调试⽅便设计的。例如CD表⽰已分配内存，DD表⽰已释放内存等。
54. Write a C program which measures the the speed of a context switch on a
UNIX/Linux system.
孟永辉：循环调⽤sleep(0)。
Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.（陈皓：上StackOverflow看看吧，经典的问题）
/doc/d576889ab0717fd5360cdcc1.html /questions/137783/expand-a-random-range-from-1-5-to-1-7
解法零：
int r;
for(int i = 0; i < 7; i++){
r += rand5();
}
return r%7 + 1;
解法⼀：
int i;
do
{
i = 5 * (rand5() - 1) + rand5(); // i is now uniformly random between 1 and 25
} while(i > 21); //孟永辉：(i > 14)应该也可以吧？
// i is now uniformly random between 1 and 21
return i % 7 + 1; // result is now uniformly random between 1 and 7
This has an expected runtime of 25/21 = 1.19 iterations of the loop, but there is an infinitesimally small probability of looping forever.
解法⼆：
This is equivalent to Adam Ronfield's solution, but may be a bit more clear for some readers. It assumes rand5() is a function that returns a statistically random integer in the range 1 through 5 inclusive.
int rand7()
{
| int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};
int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
How does it work? Think of it like this: imagine printing out this double-dimension array on paper, tacking it up to a dart board and randomly throwing darts at it. If you hit a non-zero value, it's a statistically random value between 1 and 7, since there are an equal number of non-zero values to c
hoo from. If you hit a zero, just keep throwing the dart until you
hit a non-zero. That's what this code is doing: the i and j indexes randomly lect a location on the dart board, and if we don't get a good result, we keep throwing darts.
Like Adam said, this can run forever in the worst ca, but statistically the worst ca never happens. :)
55. Describe the algorithm for a depth-first graph traversal.
