Google onsite

原帖地址:一亩三分地

共5轮
第一轮
给一个matrix,一开始都是0。写一个method addRock(int i, int j),实现在i,j位置加入一个rock使其可以变成一个island或者island的一部分,然后这个method要返回这个matrix里有多少个island

第二轮
-google 1point3acres假设把人类的族谱形成一张图,每个人都是一个node,每个人会有父亲和母亲(也是node),写一个method isBloodRelated(Node n1, Node n2),实现假设n1和n2有共同的祖先,那么就意味着n1和n2是related的。限制是可能有很多代人,然后可以在node加额外的信息。

第三轮
问题1:
给两个实现的method, Collection getActors(String movie) 和 Collection getMovies(String actor)
写一个method int distance(String actor1, String actor2),实现计算actor1到actor2的最短距离。距离的定义是假设两个演员在同一部电影里出演,那么他们之间的distance就是1。follow up是假设数据集很大,有什么方法可以优化。
问题2:
给一个expression只有+, *, 和数字。然后给一个实现好的method Iterator tokenize(String exp),1问是如何model这个Token,方向是OOD。2问是写一个method int calculate(Iterator iter),实现计算表达式的值。

第四轮
问题1:
鏉ユ簮涓憨.涓夊垎鍦拌鍧 写一个method int longestStringWithAtMostTwoUniqueChars(String s),实现返回最长的substring最多有两个unique的char
问题2:
设计google map的back end的api

第五轮
感觉问得有点偏。他先问如何实现shuffle elements in an array,但是关键不是在实现,而是证明为什么概率是正确的。我没答上来,他引导我用数有多少种可能的permutation来证明。然后follow up是他给了一种错误的shuffle的方法,然后问怎么证明这个算法是错误的。我也没答上来,他就继续引导,我没能很快理解,不过最后在他耐心的解释下,我还是理解了。
由于没剩下很多时间,第2个问题就是问了下在网页上填了个什么东西,然后点击submit后会发生什么,越详细越好。