解析Google的面试题.doc

某猎头收集了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 Manager8. Why do you want to join Google? 9. What do you know about Googles product and technology? 10. If you are Product Manager for Googles Adwords, how do you plan to market this? 11. What would you say during an AdWords or AdSense product seminar? 12. Who are Googles competitors, and how does Google compete with them? 13. Have you ever used Googles products? Gmail? 14. Whats a creative way of marketing Googles brand name and product? 15. If you are the product marketing manager for Googles 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 youve read about recently. Now tell me your own creative execution for an ad for that product. 18. 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? 19. 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 Manager21. How would you boost the GMail subscription base? 22. What is the most efficient way to sort a million integers? （陈皓：merge sort） 23. How would you re-position Googles 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 seconds. 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 machines stack grows up or down in memory? 28. Explain a database in three sentences to your eight-year-old nephew. （陈皓：用三句话向8岁的侄子解释什么是数据库，考你的表达能力了） 29. How many times a day does a clocks hands overlap?（陈皓：经典的时钟问题） 30. You have to get from point A to point B. You dont know if you can get there. What would you do? 31. Imagine you have a closet full of shirts. Its 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 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)? 答案：这题的关键在于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 seventeen minutes. The bridge is too dangerous to cross without a flashlight, and its 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 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? 答案：不算闰年的话，别人跟你生日相同的概率是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 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.) 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 search engine? 44. Design an evacuation plan for San Francisco. 45. Theres a latency problem in South Africa. Diagnose 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 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? 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 vacuums are made per year in USA? Software Engineer50. Why are manhole covers round? （陈皓：为什么下水井盖是圆的？这是有N种答案的，上Wiki看看吧） 51. What is the difference between a mutex and a semaphore? Which one would you use 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看看吧，经典的问题） /questions/137783/expand-a-random-range-from-1-5-to-1-7解法零：int r;for(int i = 0; i 21); /孟永辉：(i 14)应该也可以吧？/ i is now uniformly random between 1 and 21return i % 7 + 1; / result is now uniformly random between 1 and 7This 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 Rosenfields 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 rand7()| int vals55 = 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 = valsi-1j-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, its a statistically random value between 1 and 7, since there are an equal number of non-zero values to choose from. If you hit a zero, just keep throwing the dart until you hit a non-zero. Thats what this code is doing: the i and j indexes randomly select a location on the dart board, and if we dont get a good result, we keep throwing darts.Like Adam said, this can run forever in the worst case, but statistically the worst case never happens. :)55. Describe the algorithm for a depth-first graph traversal. 56. Design a class library for writing card games. （陈皓：用一系列的类来设计一个扑克游戏，设计题）57. 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，它们是一样的吗？”）孟永辉：“Bob，请收到纸条后，给我打个电话。”58. How are cookies passed in the HTTP protocol?孟永辉：发送请求时，附加cookies。浏览器根据服务器的要求记录cookies。59. Design the SQL database tables for a car rental database. 60. Write a regular expression which matches a email address. （陈皓：上StackOverflow查相当的问题吧。）61. 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(n2)和一个O(n)的算法复杂度） 孟永辉：按255长度的数组做b的Hash，在遍历a，同时查b。62. 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? （陈皓：和随机数有关系？或是时间？）孟永辉：和野指针、外存、网络、输入、时间等有关系63. Explain how congestion control works in the TCP protocol.孟永辉：ToS、发送和接收窗口、拥塞避免(拥塞窗口)、慢启动、快速重传、快速恢复、选择性应答(SACK)、Naggle算法等，还有一些套接字选项，例如三次握手时延迟第三个ACK包，以和数据一块发送的选项：TCP_QUICKACK或TCP_DEFER_ACCEPT等64. In Java, what is the difference between final, finally, and finalize? 孟永辉：Final修饰符（关键字）如果一个类被声明为final，意味着它不能再派生出新的子类，不能作为父类被继承。因此一个类不能既被声明为 abstract的，又被声明为final的。将变量或方法声明为final，可以保证它们在使用中不被改变。被声明为final的变量必须在声明时给定初值，而在以后的引用中只能读取，不可修改。被声明为final的方法也同样只能使用，不能重载。 Finally再异常处理时提供 finally 块来执行任何清除操作。如果抛出一个异常，那么相匹配的 catch 子句就会执行，然后控制就会进入 finally 块（如果有的话）。finalize方法名。Java 技术允许使用 finalize() 方法在垃圾收集器将对象从内存中清除出去之前做必要的清理工作。这个方法是由垃圾收集器在确定这个对象没有被引用时对这个对象调用的。它是在 Object 类中定义的，因此所有的类都继承了它。子类覆盖 finalize() 方法以整理系统资源或者执行其他清理工作。finalize() 方法是在垃圾收集器删除对象之前对这个对象调用的。65. What is multithreaded programming? What is a deadlock? 66. Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,DAA,AB,AC, AAA.) and returns a corresponding integer value (A=1,B=2, AA=26.). 孟永辉：AA=27?按26进制转化成10进制67. 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. 孟永辉：1. 评估算法是什么？如果是根据单个查询就能确定，则使用1000个元素的最大堆；如果是根据出现频率，则需要先Hash，VAL指向最大堆2. 亦可使用采样的方法，例如保持最新的1000,000条随机记录。每次的1000个结果可从这1000,1000条记录中选取。68. 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. 69. 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 dont know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. （陈皓：循环排序数组的二分查找问题） 孟永辉：1. 题目要求的是链表，而不是数组。如果是单链表，好像只能是顺序遍历了？。顺序遍历时找到第一个大于前面元素的值，因为是循环链表，所以必有此值。2. 如果是双向循环链表，则可以从正反两个方向同时遍历，直到碰头时，还没有找到元素，则查找失败。答案：我们最喜欢的答案来自读者”dude”：建立临时指针并从根上开始。（循环链表大多数情况下都有向前或向后指针。）判断是向前更大还是向后更大。如果向前更大则知道已达到链表最后，又重新位于链表开始位置。如果向前更大，那你可以向后搜寻并进行数字比较。如果既没有根也没有指针指向链表，那么你的数据就丢失在内存中了。70. Describe the data structure that is used to manage memory. (stack) 71. Whats the difference between local and global variables? 孟永辉：生存期和作用域（根源在于存储区域不同）72. If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)孟永辉：百万级不算大，直接内排即可（快速排序）；如果数的范围较小，可用计数排序73. In Java, what is the difference between static, final, and const. (if you dont know Java they will ask something similar for C or C+). 孟永辉：Java中没有conststatic关键字可以用来修饰类的变量，方法和内部类。static是静态的意思，也是全局的意思它定义的东西，属于全局与类相关，不与具体实例 相关。就是说它调用的时候，只是ClassName.method(),而不是new ClassName().method()。new ClassName()不就是一个对象了吗？static的变量和方法不可以这样调用的。它不与具体的实例有关。子类不能重写父类的静态方法哦，也不能把父类不是静态的重写成静态的方法。想隐藏父类的静态方法的话，在子类中声明和父类相同的方法就行了final关键字有三个东西可以修饰的。修饰类，方法，变量在类的声明中使用final 使用了final的类不能再派生子类，就是说不可以被继承了。有些java的面试题里面，问String可不可以被继承。答案是不可以，因为 java.lang.String是一个final类。这可以保证String对象方法的调用确实运行的是String类的方法，而不是经其子类重写后的方法。 在方法声明中使用final 被定义为final的方法不能被重写了，如果定义类为final的话，是所有的方法都不能重写。而我们只需要类中的某几个方法，不可以被重写，就在方法前加final了。而且定义为final的方法执行效率要高的啊。 在变量声明中使用final 这样的变量就是常量了，在程序中这样的变量不可以被修改的。修改的话编译器会报错的。而且执行效率也是比普通的变量要高。final的变量如果没有赋予初值的话，其他方法就必需给他赋值，但只能赋值一次。74. Talk about your class projects or work projects (pick something easy) then describe how you could make them more efficient (in terms of algorithms). 75. 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.（陈皓：以前见过一维数组的这个问题，现在是二维的。感觉应该是把二维的第一行的最大和的区间算出来，然后再在这个基础之上进行二维的分析。思路应该是这个，不过具体的算法还需要想一想） 孟永辉：一维的使用贪心来做。二维的可转化成一维的，把各小段看做首尾连接可以76. Write some code to reverse a string.孟永辉：首尾指针指向的元素互换，首指针+, 尾指针-77. Implement division (without using the divide operator, obviously).（陈皓：想一想手算除法的过程。） 孟永辉：使用二进制处理，能够简化试商过程78. Write some code to find all permutations of the letters in a particular string.孟永辉：递归79. What method would you use to look up a word in a dictionary? （陈皓：使用排序，哈希，树等算法和数据结构）孟永辉：字典树（字母键树或trie树）80. Imagine you have a closet full of shirts. Its very hard to find a shirt. So what can you do to organize your shirts for easy retrieval? 答案：此题没有固定答案。考验的是被面试者在解决问题方面的想象力和创造性。我们觉得读者”Dude”的这个答案可能会给Google留下深刻印象：把它们按布料的种类进行哈希（HASH）组合。然后每类再按2-3-4树或红黑树（都是计算机算法）排序。81. 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? 82. What is the C-language command for opening a connection with a foreign host over the internet? 孟永辉：是connect？好像有点简单83. Design and describe a system/application that will mos