April 9 2014 Google onsite

Google onsite.

4 轮面试，3轮Software Engineer 一轮 Software Engineer in Test.

一轮。 给定一个binary search tree， 知道到第k大的数。

二轮。

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies

的那个单词。尽可能的优化。

本人代码全都用Python写的。Google很好，给我分配的面试官都是写Python的。

求过，攒人品。

lz就是个jb

第三轮第一题，什么叫共同好友最多的“那个人”？意思是说共同好友最多的“两个人”吗？这题是就直接遍历所有用户，复杂度O(EV)吗？
还有第三题怎么回答？

谢谢！

话说FLAG主要用什么语言？

Did you use yield() in round 2?

楼主亲自作答。

一轮。 给定一个binary search tree， 知道到第k大的数。

1. class TreeNode(object):
   
2. 
   
3.     def __init__(self, val):
   
4.         self.val = val
   
5.         self.left = None
   
6.         self.right = None
   
7. 
   
8. 
   
9. class Solution(object):
   
10. 
    
11.     def __init__(self):
    
12.         self._idx = 0
    
13.         pass
    
14. 
    
15.     def find_kth(self, root, k):
    
16.         self._idx = 0
    
17.         res = self._inorder(root, k)
    
18.         return res
    
19. 
    
20.     def _inorder(self, node, k):
    
21.         if not node:
    
22.             return
    
23.         left = self._inorder(node.left, k)
    
24.         self._idx += 1
    
25.         if self._idx == k:
    
26.             return node
    
27.         if left:
    
28.             return left
    
29.         right = self._inorder(node.right, k)
    
30.         if right:
    
31.             return right

复制代码

题目三：假设google在火星上弄了个data center， 如何无人值守给他升级内核。如何判断机器挂掉了，挂掉了怎么办。

求答案...

楼主亲自作答。

二轮。
题目一：扩展的斐波那契数列。Sn = Sn-j + Sn-k (0<j<k). 写一个generator类。有实现next()方法。

1. class Fibonacci(object):
   
2. 
   
3.     def __init__(self, j, k, slist):
   
4.         self._j = j
   
5.         self._k = k
   
6.         self._slist = slist
   
7.         self._n = len(slist)
   
8. 
   
9.     def next(self):
   
10.         res = self._slist[self._n - self._j] +\
    
11.             self._slist[self._n - self._k]
    
12.         self._slist.append(res)
    
13.         self._n += 1
    
14.         return res
    

复制代码

1. from solution import Fibonacci
   
2. import unittest
   
3. 
   
4. 
   
5. class Test(unittest.TestCase):
   
6. 
   
7.     def test1(self):
   
8.         slist = [1, 1]
   
9.         f = Fibonacci(1, 2, slist)
   
10.         res1 = f.next()
    
11.         res2 = f.next()
    
12.         res3 = f.next()
    
13.         res4 = f.next()
    
14.         # print res1, res2, res3, res4
    
15.         self.assertEqual(2, res1)
    
16.         self.assertEqual(3, res2)
    
17.         self.assertEqual(5, res3)
    
18.         self.assertEqual(8, res4)
    
19. 
    
20.     def test2(self):
    
21.         slist = [1, 2, 3, 4, 5]
    
22.         f = Fibonacci(2, 5, slist)
    
23.         res1 = f.next()
    
24.         res2 = f.next()
    
25.         res3 = f.next()
    
26.         res4 = f.next()
    
27.         # print res1, res2, res3, res4
    
28.         self.assertEqual(5, res1)
    
29.         self.assertEqual(7, res2)
    
30.         self.assertEqual(8, res3)
    
31.         self.assertEqual(11, res4)
    
32. 
    
33. if __name__ == '__main__':
    
34.     unittest.main(verbosity=2)
    

复制代码

楼主亲自作答。


三轮。
题目一：社交网络中，如何实现好友推荐。抽象成图，然后找出共同好友最多的那个人。

1. class Node(object):
   
2. 
   
3.     def __init__(self, val):
   
4.         self.val = val
   
5.         self.friends = []
   
6. 
   
7. 
   
8. def recommend(node):
   
9.     exclude = node.friends + [node]
   
10.     freq = {}
    
11.     for item in node.friends:
    
12.         for sub_item in item.friends:
    
13.             if sub_item not in exclude:
    
14.                 freq[sub_item] = freq.get(sub_item, 0) + 1
    
15.     max_val = 0
    
16.     res = None
    
17.     for key in freq:
    
18.         val = freq[key]
    
19.         if val > max_val:
    
20.             max_val = val
    
21.             res = key
    
22.     return res
    

复制代码

楼主亲自作答。

四轮：
给一个text file， 里面是按行分割的各种单词，让找到频率第k大的那个单词。尽可能的优化。

1. def get_kth_freq(input_file_path, k):
   
2.     mydict = {}
   
3.     with open(input_file_path) as input_file:
   
4.         for line in input_file:
   
5.             mydict[line] = mydict.get(line, 0) + 1
   
6. 
   
7.     i = 0
   
8.     while i < k:
   
9.         max_key = None
   
10.         max_val = 0
    
11.         for key in mydict:
    
12.             val = mydict[key]
    
13.             if val > max_val:
    
14.                 max_val = val
    
15.                 max_key = key
    
16.         res = max_key
    
17.         del mydict[max_key]
    
18.         i += 1
    
19.     return res
    
20. 
    
21.     print mydict
    

复制代码

楼主亲自作答

三轮：
题目二：BigInt 相加。 如何表示一个BigInt， 用一个数组。跟leetcode一样

1. class BigInt(object):
   
2.     max_val = 10000
   
3. 
   
4.     def __init__(self):
   
5.         self.val = []
   
6. 
   
7.     def add(self, B):
   
8.         lenA = len(self.val)
   
9.         lenB = len(B.val)
   
10.         carry = 0
    
11.         i = 0
    
12.         res = BigInt()
    
13.         while i < lenA or i < lenB or carry != 0:
    
14.             tmp = carry
    
15.             if i < lenA:
    
16.                 tmp += self.val[i]
    
17.             if i < lenB:
    
18.                 tmp += B.val[i]
    
19. 
    
20.             if tmp >= BigInt.max_val:
    
21.                 carry = 1
    
22.                 tmp = tmp - BigInt.max_val
    
23.             else:
    
24.                 carry = 0
    
25.             res.val.append(tmp)
    
26.             i += 1
    
27.         return res
    
28. 
    

复制代码