google面试

早上错过了班车，迟到了半个小时。妈蛋，果然跟google没缘分。

到了之后逛了一圈，不错，啥都有：coffee shop, laundry, kitchen at every floor, breakfast, launch, dinner, game room, music room, library. 应该来个Google Hilton.就齐活了。

一面问了个找字符串查重的问题。然后问了一下如何实现iterator的peek。挺有意思！

二面是一个哥们问如何对一个用户进行好友推荐，这个推荐的人应该和用户有最多的共同好友。是图问题。

三面是写一个meeting schedule, 求最少的房间。

四面问一个word grid.给一个词，返回有多少个path可以组成所给定的词。

面完了滚出，给了一个瓶子，还有五块钱的google store卡。。。

午饭挺好吃的。下次有机会去，一定得好好吃一顿

齐活...楼主哪里人？我以前经常用"齐活"这个词，哈哈

多谢楼主分享~~去一次onsite这辈子job hunting就值了~

1. class Grid(object):
   
2. 
   
3.     def __init__(self, grid):
   
4.         self._grid = grid
   
5.         self._m = len(grid)
   
6.         self._n = len(grid[0])
   
7. 
   
8.     def _get_children(self, i, j):
   
9.         res = {}
   
10.         for p in [-1, 0, 1]:
    
11.             for q in [-1, 0, 1]:
    
12.                 if p == q == 0:
    
13.                     continue
    
14.                 ii = i + p
    
15.                 jj = j + q
    
16.                 if 0 <= ii < self._m and 0 <= jj < self._n:
    
17.                     res[(ii, jj)] = self._grid[ii][jj]
    
18.         return res
    
19. 
    
20.     def find_path(self, word):
    
21.         self._visited = set()
    
22.         res = []
    
23.         for i in range(self._m):
    
24.             for j in range(self._n):
    
25.                 self._results = []
    
26.                 self._find_path_aux(0, word, [], i, j)
    
27.                 res.extend(self._results[:])
    
28.         return res
    
29. 
    
30.     def _find_path_aux(self, idx, word, one_result, i, j):
    
31.         if idx == len(word) - 1:
    
32.             target = word[idx]
    
33.             if target == self._grid[i][j] and ((i, j) not in self._visited):
    
34.                 self._results.append(one_result + [(i, j)])
    
35.         else:
    
36.             # 0 <= idx < len(word) - 1
    
37.             target = word[idx]
    
38.             if target == self._grid[i][j] and ((i, j) not in self._visited):
    
39.                 self._visited.add((i, j))
    
40.                 children = self._get_children(i, j)
    
41.                 for key in children:
    
42.                     ii = key[0]
    
43.                     jj = key[1]
    
44.                     self._find_path_aux(idx + 1, word, one_result + [(i, j)],
    
45.                                         ii, jj)
    
46.                 self._visited.remove((i, j))
    
47.             else:
    
48.                 return
    

复制代码

1. # -*- coding: utf-8 -*-
   
2. import unittest
   
3. from solution import Grid
   
4. 
   
5. 
   
6. class Test(unittest.TestCase):
   
7. 
   
8.     def test1(self):
   
9.         word = 'dog'
   
10.         grid = ['dogo', 'oodo', 'gogo', 'oooo']
    
11.         grid = ['dogo', 'xxxx', 'xxxx', 'xxxx']
    
12.         grid = [[y for y in x] for x in grid]
    
13.         s = Grid(grid)
    
14.         res = s.find_path(word)
    
15.         print res
    
16. 
    
17.     def test2(self):
    
18.         word = 'dog'
    
19.         grid = ['dogo', 'oodo', 'gogo', 'oooo']
    
20.         grid = [[y for y in x] for x in grid]
    
21.         s = Grid(grid)
    
22.         res = s.find_path(word)
    
23.         print res
    
24. if __name__ == '__main__':
    
25.     unittest.main(verbosity=2)
    

复制代码

1. class Grid(object):
   
2. 
   
3.     def __init__(self, grid):
   
4.         self._grid = grid
   
5.         self._m = len(grid)
   
6.         self._n = len(grid[0])
   
7. 
   
8.     def _get_children(self, i, j):
   
9.         res = {}
   
10.         for p in [-1, 0, 1]:
    
11.             for q in [-1, 0, 1]:
    
12.                 if p == q == 0:
    
13.                     continue
    
14.                 ii = i + p
    
15.                 jj = j + q
    
16.                 if 0 <= ii < self._m and 0 <= jj < self._n:
    
17.                     res[(ii, jj)] = self._grid[ii][jj]
    
18.         return res
    
19. 
    
20.     def find_path(self, word):
    
21.         self._visited = set()
    
22.         res = []
    
23.         for i in range(self._m):
    
24.             for j in range(self._n):
    
25.                 self._results = []
    
26.                 self._find_path_aux(0, word, [], i, j)
    
27.                 res.extend(self._results[:])
    
28.         return res
    
29. 
    
30.     def _find_path_aux(self, idx, word, one_result, i, j):
    
31.         if idx == len(word) - 1:
    
32.             target = word[idx]
    
33.             if target == self._grid[i][j] and ((i, j) not in self._visited):
    
34.                 self._results.append(one_result + [(i, j)])
    
35.         else:
    
36.             # 0 <= idx < len(word) - 1
    
37.             target = word[idx]
    
38.             if target == self._grid[i][j] and ((i, j) not in self._visited):
    
39.                 self._visited.add((i, j))
    
40.                 children = self._get_children(i, j)
    
41.                 for key in children:
    
42.                     ii = key[0]
    
43.                     jj = key[1]
    
44.                     self._find_path_aux(idx + 1, word, one_result + [(i, j)],
    
45.                                         ii, jj)
    
46.                 self._visited.remove((i, j))
    
47.             else:
    
48.                 return
    

复制代码

1. # -*- coding: utf-8 -*-
   
2. import unittest
   
3. from solution import Grid
   
4. 
   
5. 
   
6. class Test(unittest.TestCase):
   
7. 
   
8.     def test1(self):
   
9.         word = 'dog'
   
10.         grid = ['dogo', 'oodo', 'gogo', 'oooo']
    
11.         grid = ['dogo', 'xxxx', 'xxxx', 'xxxx']
    
12.         grid = [[y for y in x] for x in grid]
    
13.         s = Grid(grid)
    
14.         res = s.find_path(word)
    
15.         print res
    
16. 
    
17.     def test2(self):
    
18.         word = 'dog'
    
19.         grid = ['dogo', 'oodo', 'gogo', 'oooo']
    
20.         grid = [[y for y in x] for x in grid]
    
21.         s = Grid(grid)
    
22.         res = s.find_path(word)
    
23.         print res
    
24. if __name__ == '__main__':
    
25.     unittest.main(verbosity=2)
    

复制代码

找字符串查重的问题
什么意思？