Google onsite 面筋失败经验

totolin 发表于 2015-7-17 21:51
第一要考虑食物被隔开的情况，事先要讨论好怎么处理而不是事后被指出。题41最优是o(n).我遍了个o(n2)的

为什么食物找不到的情况卡住了？
BFS的时候queue里没东西了，然后你还没发现食物，这不就done了？

请问第2题是infinite的做法应该是什么？lz当时怎么回答的？

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

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

大概是这样

1. 
   
2. from collections import deque
   
3. 
   
4. 
   
5. 
   
6. def shortestPoint(A):
   
7.     m = len(A)
   
8.     n = len(A[0])
   
9.     psum = [[0]*n for k in range(m)]
   
10. 
    
11.     for i in range(m):
    
12.         for j in range(n):
    
13.             if A[i][j] == 2:
    
14.                 B = [[-1]*n for k in range(m)]
    
15.                 B[i][j] = 0
    
16.                 bfshelper(B, A, i, j, m, n)
    
17.                 psum = map(lambda pair: map(lambda x, y: x+y, pair[0] , pair[1]),  zip(B,psum))
    
18. 
    
19.     mini, minj, maxstep = -1, -1, 2147483647
    
20.     for i in range(m):
    
21.         for j in range(n):
    
22.             if 0 < psum[i][j] < maxstep:
    
23.                 mini, minj = i, j
    
24.                 maxstep = psum[i][j]
    
25.     return (mini, minj)
    
26. 
    
27. def bfshelper(B, A, i, j, m, n):
    
28.     Q = deque([(i,j)])
    
29. 
    
30.     while Q:
    
31.         (i, j) = Q.popleft()
    
32.         for x, y in [(i+1,j), (i-1, j), (i, j+1), (i, j-1)]:
    
33.             if 0<=x<m and 0<=y<n and B[x][y] == -1 and A[x][y] != 0:
    
34.                 B[x][y] = B[i][j] + 1
    
35.                 Q.append( (x, y) )
    
36. 
    
37.    
    
38. 
    
39. def Main():
    
40.     C = [[0, 2, 1, 1], [0, 1, 2, 0], [1, 1, 1, 1], [1, 0, 0, 2], [1, 2, 0, 0]]
    
41.     B = [[2,0,1, 0], [1,1,1, 2], [0,1,0, 0], [1, 1, 1, 2]]
    
42.     A = [[1]]
    
43.     D = [[2, 1, 0, 0], [1, 2, 0, 1], [1, 0, 2, 1], [0, 1, 2, 1]]
    
44. 
    
45.     test = C
    
46.     for row in test:
    
47.         print row
    
48. 
    
49.     print "---"
    
50.     print shortestPoint(test)
    
51. 
    
52. if __name__ == '__main__':
    
53.     Main()
    

复制代码

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

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

为什么第五题的字典是4G而不是16G的呢，2^32个数，每个都要占用4byte不是么

另外第一题的代码看不太懂，楼主可以加一点注释么

returning 发表于 2015-10-11 01:07
对于很大stream求median，我觉得应该有个范围估值，可以把一定很大的数抛弃，把一定很小的数抛弃，假设一定 ...

弱弱的问一下既然是求median(中位数) 为什么会有因为size 而漏掉的情况呢?还是讨论的是求mean(平均数)?

say543 发表于 2015-10-12 02:21
弱弱的问一下既然是求median(中位数) 为什么会有因为size 而漏掉的情况呢?还是讨论的是求mean(平均数)?

题目不是说万一数目很大怎么办？如果heap不能维护，那肯定就要估计了，对吧，一旦估计就可能漏掉一些，除非开始的估计很准确。

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

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

stellari 发表于 2015-7-19 01:26
感谢楼主分享，但是原题不是要求a和b的hamming distance么？如果按这种方法建字典，得到似乎是a和0的hamm ...

我也有同样的问题，请问你是怎么理解的？