【zz】140个Google的面试题

现在的位置: 首页 > 综合 > 正文

【zz】140个Google的面试题

2012年11月15日 ⁄ 综合 ⁄ 共 20956字 ⁄ 字号小中大 ⁄ 评论关闭

来源：http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html（墙）

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. （陈皓：Binary Search，二分查）
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.
Implement division (without using the divide operator, obviously).（陈皓：想一想手算除法的过程。）
Write some code to find all permutations of the letters in a particular string.
What method would you use to look up a word in a dictionary? （陈皓：使用排序，哈希，树等算法和数据结构）
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?
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 fine the ball that is
heavier by using a balance and only two weighings?
What is the C-language command for opening a connection with a foreign host over the internet?
Design and describe a system/application that will most efficiently
produce a report of the top 1 million Google search requests. These are
the particulars: 1) You are given 12 servers to work with. They are all
dual-processor machines with 4Gb of RAM, 4x400GB hard drives and
networked together.(Basically, nothing more than high-end PC’s) 2) The
log data has already been cleaned for you. It consists of 100 Billion
log lines, broken down into 12 320 GB files of 40-byte search terms per
line. 3) You can use only custom written applications or available free
open-source software.
There is an array A[N] of N numbers. You have to compose an array
Output[N] such that Output[i] will be equal to multiplication of all the
elements of A[N] except A[i]. For example Output[0] will be
multiplication of A[1] to A[N-1] and Output[1] will be multiplication of
A[0] and from A[2] to A[N-1]. Solve it without division operator and in
O(n).（陈皓：注意其不能使用除法。算法思路是这样的，把output[i]=a[i]左边的乘积 x
a[i]右边的乘积，所以，我们可以分两个循环，第一次先把A[i]左边的乘积放在Output[i]中，第二次把A[i]右边的乘积算出来。我们先看第
一次的循环，使用迭代累积的方式，代码如下：for(r=1; i=0; i<n-1; i++){ Output[i]=r; r*=a[i];
}，看明白了吧。第二次的循环我就不说了，方法一样的。）
There is a linked list of numbers of length N. N is very large and
you don’t know N. You have to write a function that will return k random
numbers from the list. Numbers should be completely random. Hint: 1.
Use random function rand() (returns a number between 0 and 1) and
irand() (return either 0 or 1) 2. It should be done in
O(n).（陈皓：本题其实不难。在遍历链表的同时一边生成随机数，一边记录最大的K个随机数和其链接地址。）
Find or determine non existence of a number in a sorted list of N
numbers where the numbers range over M, M>> N and N large enough
to span multiple disks. Algorithm to beat O(log n) bonus points for
constant time algorithm.（陈皓：使用bitmap，如果一个长整形有64位，那么我们可以使用M/64个bitmap）
You are given a game of Tic Tac Toe. You have to write a function in
which you pass the whole game and name of a player. The function will
return whether the player has won the game or not. First you to decide
which data structure you will use for the game. You need to tell the
algorithm first and then need to write the code. Note: Some position may
be blank in the game। So your data structure should consider this
condition also.
You are given an array [a1 To an] and we have to construct another
array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only
constant space and the time complexity is O(n). No divisions are
allowed.（陈皓：前面说过了）
How do you put a Binary Search Tree in an array in a efficient
manner. Hint :: If the node is stored at the ith position and its
children are at 2i and 2i+1(I mean level order wise)Its not the most
efficient way.（陈皓：按顺序遍历树）
How do you find out the fifth maximum element in an Binary Search
Tree in efficient manner. Note: You should not use use any extra space.
i.e sorting Binary Search Tree and storing the results in an array and
listing out the fifth element.
Given a Data Structure having first n integers and next n chars. A =
i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange
the elements of the array ass A = i1 c1 i2 c2 … in
cn（陈皓：这个算法其实就是从中间开始交换元素，代码：for(i=n-1; i>1; i++) { for(j=i;
j<2*n-i; j+=2) { swap(a[j], a[j+1]); } }，不好意思写在同一行上了。）
Given two sequences of items, find the items whose absolute number
increases or decreases the most when comparing one sequence with the
other by reading the sequence only once.
Given That One of the strings is very very long , and the other one
could be of various sizes. Windowing will result in O(N+M) solution but
could it be better? May be NlogM or even better?
How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
Let’s say you have to construct Google maps from scratch and guide a
person standing on Gateway of India (Mumbai) to India Gate(Delhi). How
do you do the same?
Given that you have one string of length N and M small strings of
length L. How do you efficiently find the occurrence of each small
string in the larger one?
Given a binary tree, programmatically you need to prove it is a binary search tree.
You are given a small sorted list of numbers, and a very very long
sorted list of numbers – so long that it had to be put on a disk in
different blocks. How would you find those short list numbers in the
bigger one?
Suppose you have given N companies, and we want to eventually merge
them into one big company. How many ways are theres to merge?
Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? （陈皓：我能想到的是拆分成若干个小数组，排序，然后一点点归并起来）
Write a program for displaying the ten most frequent words in a file
such that your program should be efficient in all complexity
measures.（陈皓：你可能需要看看这篇文章Finding Frequent Items in Data Streams）
Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.（陈皓：你应该查看一下这篇文章：Coin Change Problem）
Given an array, i) find the longest continuous increasing
subsequence. ii) find the longest increasing
subsequence.（陈皓：这个题不难，O(n)算法是边遍历边记录当前最大的连续的长度。）
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
Write a function to find the middle node of a single link list. （陈皓：我能想到的算法是——设置两个指针p1和p2，每一次，p1走两步，p2走一步，这样，当p1走到最后时，p2就在中间）
Given two binary trees, write a compare function to check if they
are equal or not. Being equal means that they have the same value and
same structure.（陈皓：这个很简单，使用递归算法。）
Implement put/get methods of a fixed size cache with LRU replacement algorithm.
You are given with three sorted arrays ( in ascending order), you
are required to find a triplet ( one element from each array) such that
distance is minimum. Distance is defined like this : If a[i], b[j] and
c[k] are three elements then
distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a
solution in O(n) time complexity（陈皓：三个指针，a, b,
c分别指向三个数组头，假设：a[0]<b[0]<c[0]，推进a直到a[i]>b[0]，计算 abs(a[i-1] –
c[0])，把结果保存在min中。现在情况变成找 a[i],
b[0],c[0]，重复上述过程，如果有一个新的值比min要小，那就取代现有的min。）
How does C++ deal with constructors and deconstructors of a class and its child class?
Write a function that flips the bits inside a byte (either in C++ or
Java). Write an algorithm that take a list of n words, and an integer
m, and retrieves the mth most frequent word in that list.
What’s 2 to the power of 64?
Given that you have one string of length N and M small strings of
length L. How do you efficiently find the occurrence of each small
string in the larger one?
（陈皓：我能想到的是——把那M个小字串排个序，然后遍历大字串，并在那M个字串中以二分取中的方式查找。）
How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
There is linked list of millions of node and you do not know the
length of it. Write a function which will return a random number from
the list.
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?
How long it would take to sort 1 trillion numbers? Come up with a good estimate.
Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
There are some data represented by(x,y,z). Now we want to find the
Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1,
z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now
we can not get it by calculating value(x,y,z) or through other indirect
calculations as lg(value(x,y,z)). How to solve it?
How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?
Given an array whose elements are sorted, return the index of a the
first occurrence of a specific integer. Do this in sub-linear time. I.e.
do not just go through each element searching for that element.
Given two linked lists, return the intersection of the two lists:
i.e. return a list containing only the elements that occur in both of
the input lists. （陈皓：把第一个链表存入hash表，然后遍历第二个链表。不知道还没有更好的方法。）
What’s the difference between a hashtable and a hashmap?
If a person dials a sequence of numbers on the telephone, what
possible words/strings can be formed from the letters associated with
those numbers?（陈皓：这个问题和美国的电话有关系，大家可以试着想一下我们发短信的手机，按数字键出字母，一个组合的数学问题。）
How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
Create a fast cached storage mechanism that, given a limitation on
the amount of cache memory, will ensure that only the least recently
used items are discarded when the cache memory is reached when inserting
a new item. It supports 2 functions: String get(T t) and void
put(String k, T t).
Create a cost model that allows Google to make purchasing decisions
on to compare the cost of purchasing more RAM memory for their servers
vs. buying more disk space.
Design an algorithm to play a game of Frogger and then code the
solution. The object of the game is to direct a frog to avoid cars while
crossing a busy road. You may represent a road lane via an array.
Generalize the solution for an N-lane road.
What sort would you use if you had a large data set on disk and a small amount of ram to work with?
What sort would you use if you required tight max time bounds and wanted highly regular performance.
How would you store 1 million phone numbers?（陈皓：试想电话是有区段的，可以把区段统一保存，Flyweight设计模式）
Design a 2D dungeon crawling game. It must allow for various items
in the maze – walls, objects, and computer-controlled characters. (The
focus was on the class structures, and how to optimize the experience
for the user as s/he travels through the dungeon.)
What is the size of the C structure below on a 32-bit system? On a 64-bit? （陈皓：注意编译器的对齐）

struct foo {

char a;

char* b;

};

Software Engineer in Test

Efficiently implement 3 stacks in a single array.
Given an array of integers which is circularly sorted, how do you find a given integer.
Write a program to find depth of binary search tree without using recursion.
Find the maximum rectangle (in terms of area) under a histogram in linear time.
Most phones now have full keyboards. Before there there three
letters mapped to a number button. Describe how you would go about
implementing spelling and word suggestions as people type.
Describe recursive mergesort and its runtime. Write an iterative version in C++/Java/Python.
How would you determine if someone has won a game of tic-tac-toe on a board of any size?
Given an array of numbers, replace each number with the product of
all the numbers in the array except the number itself *without* using
division.
Create a cache with fast look up that only stores the N most recently accessed items.
How to design a search engine? If each document contains a set of
keywords, and is associated with a numeric attribute, how to build
indices?
Given two files that has list of words (one per line), write a program to show the intersection.
What kind of data structure would you use to index annagrams of
words? e.g. if there exists the word “top” in the database, the query
for “pot” should list that.

Quantitative Compensation Analyst

What is the yearly standard deviation of a stock given the monthly standard deviation?
How many resumes does Google receive each year for software engineering?
Anywhere in the world, where would you open up a new Google office
and how would you figure out compensation for all the employees at this
new office?
What is the probability of breaking a stick into 3 pieces and forming a triangle?

Engineering Manager

You’re the captain of a pirate ship, and your crew gets to vote on
how the gold is divided up. If fewer than half of the pirates agree with
you, you die. How do you recommend apportioning the gold in such a way
that you get a good share of the booty, but still survive?

AdWords Associate

How would you work with an advertiser who was not seeing the benefits of the AdWords relationship due to poor conversions?
How would you deal with an angry or frustrated advertisers on the phone?

Sources

http://news.ycombinator.com/item?id=266663

http://tihomir.org/crazy-questions-at-google-job-interview/

http://www.drizzle.com/~jpaint/google.html

http://www.gamedev.net/community/forums/topic.asp?topic_id=299692

http://careers.cse.sc.edu/googleinterview

http://job-interview.blogspot.com/2005/02/google-interview-product-marketing.html

http://www.theregister.co.uk/2007/01/05/google_interview_tales/

http://money.cnn.com/2007/08/29/technology/brain_teasers.biz2/index.htm

http://blogs.lessthandot.com/index.php/ITProfessionals/EthicsIT/google-interview-questions

http://placementsindia.blogspot.com/2007/09/google-top-interview-puzzles.html

http://linkmingle.com/user/interview_questions/google_interview_questions