谷歌上门

[匿名1217]

Mountainview面的，level没定，可能是L4或L5

第一轮

• Variation of https://leetcode.com/problems/random-pick-with-weight/
  Given a list of countries along with the respective population. Design a random generator that would select one of the countries.

第二轮

• Given a list of planks where there is a parent child relationship between planks, Implement a function to print all the planks that are inside a given plank. (it was a breadth first search, the question is difficult to explain without a drawing)

第三轮 系统设计

• Firefox - design a system that will show the page “this site is blocked” on entering a blocked site.

第四轮: [Googleyness & Leadership]

第五轮

• Variation of https://leetcode.com/problems/k-closest-points-to-origin/
  Given a list of points with (x,y) co-ordinates. Implement a system that will return the K points nearest to a given point N.

[匿名1154]

我碰到的题

第一题: Given family tree such that Father and Mother are parents to children find if given two people are genetically related. for example siblings are genetically related but husband wife are not. Had freedom to define datastructure for nodes. I chose to represent node with List of parents pointer.

第二题: Given a function f(x,y) = N where x,y,N are natural numbers and function f(x,y) is strictly increasing. Find all posssible combinations of x,y.

第三题: Given itinerary like ABC->DEF->GHI->KLM where each of these are cities which might or might not be valid city and functions getNeighbour(City) and GetAllCities(). We can change any given city Name valid or invalid such that cost is sum of edit distance(number of characters changed) of original itinerary and new itinerary is minimum. Also adjacent cities in itinerary should be neighbouring cities.

[匿名1299]

1. 第一题是一个stream match。指定的string，用倒叙存储就可以了。
2. 第二题是一个tree，找最佳的位置来获得足够的node，followup是问如何挑选最好的起始点。就是计算所有的subtree的node
3. 第三轮第一问是iterator，第二问是一个iterator的iterator，中间可能会有null
4. 第四轮是对角线切割字符串，写完分析时间复杂度的时候出了点岔子。不过写的很快所以又问了两道dp，都答出来了
5. 第五轮是一个小哥自己编的题，很奇怪，但是他最后说我的结果work，然后又讨论了一下trade off，用了两种不同的数据结构。最后聊了15分钟来。