140个Google的面试题

某猎头收集了140多个Google的面试题，都张到他的Blog中了，主要是下面这些职位的，因为被墙，且无任何敏感信息，所以，我原文搬过来了。

? ? ? ? ? ? ?

Product Marketing Manager Product Manager Software Engineer Software Engineer in Test

Quantitative Compensation Analyst Engineering Manager AdWords Associate

这篇Blog例举了Google用来面试下面这几个职位的面试题。很多不是很容易回答，不过都比较经典与变态，是Google，Microsoft，Amazon之类的公司的风格。对于本文，我没有翻译，因为我相信，英文问题是最好的。不过对于有些问题，我做了一些注释，不一定对，但希望对你有帮助启发。对于一些问题，如果你百思不得其解，可以Google一下，StackOverflow或是Wikipedia上可能会给你非常全面的答案。

Product Marketing Manager

? ? ? ? ? ? ? ? ? ? ?

Why do you want to join Google?

What do you know about Google’s product and technology?

If you are Product Manager for Google’s Adwords, how do you plan to market this? What would you say during an AdWords or AdSense product seminar? Who are Google’s competitors, and how does Google compete with them? Have you ever used Google’s products? Gmail?

What’s a creative way of marketing Google’s brand name and product?

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?

How much money you think Google makes daily from Gmail ads?

Name a piece of technology you’ve read about recently. Now tell me your own

creative execution for an ad for that product.

Say an advertiser 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 advertiser to make $20?

? Estimate the number of students who are college seniors, attend four-year schools,

and graduate with a job in the United States every year. Product Manager

? ? ? ?

How would you boost the GMail subscription base?

What is the most efficient way to sort a million integers? （陈皓：merge sort） How would you re-position Google’s offerings to counteract competitive threats from

Microsoft?

How many golf balls can fit in a school bus? （陈皓：这种题一般来说是考你的解题思路的，

注意，你不能单纯地把高尔夫球当成一个小立方体，其是一个圆球，堆起来的时候应该是错开的——也就是三个相邻的球的圆心是个等边三角形）

? 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 seconds. What do you do?

? How much should you charge to wash all the windows in Seattle?

? ? ? ? ?

How would you find out if a machine’s stack grows up or down in memory? Explain a database in three sentences to your eight-year-old nephew. （陈皓：用三

句话向8岁的侄子解释什么是数据库，考你的表达能力了）

How many times a day does a clock’s hands overlap?（陈皓：经典的时钟问题） You have to get from point A to point B. You don’t know if you can get there. What

would you do?

Imagine you have a closet 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之类的数据结构）

? 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们的递归，这类的问题是经典的分布式通讯问题，上网搜 一搜吧。）

? 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%的概率是永远不变的。）

? ? ?

If the probability of observing a car in 30 minutes on a highway is 0.95, what is the

probability of observing a car in 10 minutes (assuming constant default probability)?

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!)

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 seventeen minutes. The bridge is too dangerous to cross without a flashlight, and it’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?（陈皓：经典的过桥问题）

? You are at a party with a friend and 10 people are present 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?

? ?

How many piano tuners are there in the entire world?

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?（陈皓：经典的称重问题。这样的问题花样很多，不过都不难回答）

? You have five pirates, ranked from 5 to 1 in descending order. The top pirate has the

right to propose 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.)

? 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）

? ? ? ?

Describe a technical problem you had and how you solved it. How would you design a simple search engine? Design an evacuation plan for San Francisco.

There’s a latency problem in South Africa. Diagnose it. （陈皓：这个问题完全是在考你

的解决问题的能力。没有明确的答案。不过，解决性能问题的第一步通常是找出瓶颈，找瓶颈有很多种方法，工具，二分查，时间记录等等。）

? ?

What are three long term challenges facing Google?

Name three non-Google websites that you visit often and like. What do you like about

the user interface and design? Choose one of the three sites and comment on what new feature or project you would work on. How would you design it?

? 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? （陈皓：经典的电梯设计问题，这种问题千变万化，主要是考你的设计能力和需求变化的适变能力，与此相似的是酒店订房系统。）

? ? ? ? ? ? ?

How many vacuum’s are made per year in USA?

Software Engineer

Why are manhole covers round? （陈皓：为什么下水井盖是圆的？这是有N种答案的，上

Wiki看看吧）

What is the difference between a mutex and a semaphore? Which one would you use

to protect access to an increment operation?

A man pushed his car to a hotel and lost his fortune. What happened? （陈皓：脑筋

急转弯？他在玩大富翁游戏？！！）

Explain the significance of ―dead beef‖.（陈皓：要是你看到的是16进制 DEAD BEEF，

你会觉得这是什么？IPv6的地址？）

Write a C program which measures the the speed of a context switch on a UNIX/Linux

system.

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看看吧，经典的问题）

? ? ?

Describe the algorithm for a depth-first graph traversal.

Design a class library for writing card games. （陈皓：用一系列的类来设计一个扑克游戏，

设计题）

You need to check that your friend, Bob, has your correct phone number, but you

cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your

phone number?（陈皓：协议+数字加密，我试想了一个，纸条上可以这样写，―Bob，请把我的手机号以MD5算法加密后的字符串，比对下面的字符串——XXXXXX，它们是一样的吗？‖）

? ? ? ?

How are cookies passed in the HTTP protocol?

Design the SQL database tables for a car rental database.

Write a regular expression which matches a email address. （陈皓：上StackOverflow

查相当的问题吧。）

Write a function f(a, b) which takes two character string arguments and returns a

string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.（陈皓：算法题，不难，不说了。一个O(n^2)和一个O(n)的算法复杂度）

? You are given a the source to a application which is crashing when run. After running

it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? （陈皓：和随机数有关系？或是时间？）

? ? ? ?

Explain how congestion control works in the TCP protocol. In Java, what is the difference between final, finally, and finalize? What is multithreaded programming? What is a deadlock?

Write a function (with helper functions if needed) called to Excel that takes an excel

column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).

? You have a stream of infinite queries (ie: real time Google search queries that people

are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.

? Tree search algorithms. Write BFS and DFS code, explain run time and space

requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.

? You are given a list of numbers. When you reach the end of the list you will come back

to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. （陈皓：循环排序数组的二分查找问题）

? ? ? ? ? ?

Describe the data structure that is used to manage memory. (stack) What’s the difference between local and global variables?

If you have 1 million integers, how would you sort them efficiently? (modify a specific

sorting algorithm to solve this)

In Java, what is the difference between static, final, and const. (if you don’t know

Java they will ask something similar for C or C++).

Talk about your class projects or work projects (pick something easy)… then describe

how you could make them more efficient (in terms of algorithms).

Suppose you have an NxN matrix of positive and negative integers. Write some code

that finds the sub-matrix with the maximum sum of its elements.（陈皓：以前见过一维数组的这个问题，现在是二维的。感觉应该是把二维的第一行的最大和的区间算出来，然后再在这个基础之上进行二维的分析。思路应该是这个，不过具体的算法还需要想一想）

? Write some code to reverse a string.