狗家昂赛

1. 给一个由1和0组成的矩阵，返回每一个位置的数字与0的最短距离（上下左右四个方向走）。先写了一个对每个点用BFS的解法。follow up是如何优化，避免重复的BFS。

2.1 问了很多C++的问题，virtual function， friend function，不同数据结构的比较，等等。
2.2

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

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

3.

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

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

4. 有点像LC 150. Evaluate Reverse Polish Notation。follow up是nested表达式。

5. 给一段距离（比如100），

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

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

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

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

第一题follow up是不是所有的0一起做BFS？

1. 
   
2. from collections import deque
   
3. class Solution(object):
   
4.     # Do BFS for all one's
   
5.     def minDist(self, matrix):
   
6.         def bfs(i, j, matrix):
   
7.             directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
   
8.             queue = deque([(i, j, 0)])
   
9.             visited = set()
   
10.             while queue:
    
11.                 pi, pj, depth = queue.popleft()
    
12.                 for di, dj in directions:
    
13.                     ni, nj = pi + di, pj + dj
    
14.                     if 0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) and (ni, nj) not in visited:
    
15.                         visited |= {(ni, nj)}
    
16.                         if matrix[ni][nj] == 0:
    
17.                             matrix[i][j] = depth + 1
    
18.                             return
    
19.                         queue.append((ni, nj, depth + 1))
    
20. 
    
21.         for i in range(len(matrix)):
    
22.             for j in range(len(matrix[0])):
    
23.                 if matrix[i][j] == 1:
    
24.                     bfs(i, j, matrix)
    
25.         return matrix
    
26. 
    
27.     def minDistFollowUp(self, matrix):
    
28.         queue = deque([])
    
29.         directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
30.         for i in range(len(matrix)):
    
31.             for j in range(len(matrix[0])):
    
32.                 if matrix[i][j] == 1:
    
33.                     matrix[i][j] = -1
    
34. 
    
35.         for i in range(len(matrix)):
    
36.             for j in range(len(matrix[0])):
    
37.                 if matrix[i][j] == 0:
    
38.                     queue.append((i, j))
    
39. 
    
40.         while queue:
    
41.             i, j = queue.popleft()
    
42.             for di, dj in directions:
    
43.                 ni, nj = i + di, j + dj
    
44.                 if 0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) and matrix[ni][nj] == -1:
    
45.                     matrix[ni][nj] = matrix[i][j] + 1
    
46.                     queue.append((ni, nj))
    
47.         return matrix
    
48. 
    
49. solver = Solution()
    
50. m = [[0,1,0,0,1], [1,1,1,0,0], [1,1,0,0,1],[0,0,1,0,1]]
    
51. print m
    
52. print solver.minDist(m)
    
53. print solver.minDistFollowUp(m)
    

复制代码

在浙里 发表于 2017-1-10 13:05
感谢楼主分享，他家有冻结期吗？多久？

听说12个月？

请问第二题secret word和guess word的长度相同吗？

第五题是我电面一面考的题目，当时就有点蒙了。。。

xianzhuzi 发表于 2017-1-12 05:34
第五题是我电面一面考的题目，当时就有点蒙了。。。

这题是要自动生成random.nextDouble(100)然后模拟要多少雨滴么？ 可以用类似Merge interval嚒

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

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

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

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