Waymo

Waymo
1. Given 2 sets of synonymous words, return if 2 sentences are synonymousfollow up: what if synonymous can be multi-w

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

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

finding out how far does a car go given a series of operations...

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

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

对于第二题，其实是不是没有必要用heap, 因为bfs每个位置最多被访问4次，依然是线性时间，用heap理论复杂度反而增加了。

什么是waymo呀？

请教楼主第二题，with minimum turn, 应该再怎么做呀？
matrix上是带障碍物，只需要避开障碍物吗？
貌似DFS + memoization 就可以？

请问楼主是全职还是实习

求大米：

1. import numpy as np
   
2. 
   
3. import matplotlib.pyplot as plt
   
4. 
   
5. def min_turn(map, src, dst, current_direction = None):
   
6.     if src == dst:
   
7.         return 0, [src]
   
8.     m, n = map.shape
   
9.     ret = np.inf
   
10.     ret_path = []
    
11.     for direction in ((1,0), (0,1), (-1,0), (0,-1)):
    
12.         loc = (src[0]+direction[0], src[1]+direction[1])
    
13.         if loc[0] < 0 or loc[0] >= m or loc[1] < 0 or loc[1] >= n or map[loc[0],loc[1]] != 0:
    
14.             continue
    
15.         map[loc[0],loc[1]] = -1
    
16.         n_turns, path = min_turn(map, loc, dst, direction)
    
17.         map[loc[0],loc[1]] = 0
    
18.         if direction != current_direction:
    
19.             n_turns += 1
    
20.         if ret > n_turns:
    
21.             ret = n_turns
    
22.             ret_path = [src] + path
    
23.     return ret, ret_path
    
24. 
    
25. 
    
26. map = np.zeros((5,5))
    
27. map[1,1] = 1
    
28. map[2,2] = 1
    
29. map[3,3] = 1
    
30. map[3,0] = 1
    
31. map[4,1] = 1
    
32. 
    
33. n_turns, path = min_turn(map, (1,0), (4,2))
    
34. print(n_turns, path)
    
35. for p in path:
    
36.     map[p[0],p[1]] = -1
    
37. plt.figure()
    
38. plt.imshow(map)
    
39. plt.show()

复制代码

发两个解法
求大米

1. import heapq
   
2. import numpy as np
   
3. import matplotlib.pyplot as plt
   
4. 
   
5. def min_turn_bfs(map, src, dst):
   
6.     if src == dst:
   
7.         return 0, [src]
   
8.     m, n = map.shape
   
9.     q = [(0, (0,0), [src])]
   
10.     while len(q) > 0:
    
11.         n_turns, current_direction, path = heapq.heappop(q)
    
12.         print(q)
    
13.         for direction in ((1,0), (0,1), (-1,0), (0,-1)):
    
14.             loc = (path[-1][0]+direction[0], path[-1][1]+direction[1])
    
15.             if loc[0] < 0 or loc[0] >= m or loc[1] < 0 or loc[1] >= n or map[loc[0],loc[1]] != 0 or loc in path: # path can be optimized with set
    
16.                 continue
    
17.             n_turns_next = n_turns
    
18.             if direction != current_direction:
    
19.                 n_turns_next += 1
    
20.             path_next = path + [loc]
    
21.             if loc == dst:
    
22.                 return n_turns_next, path_next
    
23.             heapq.heappush(q, (n_turns_next, direction, path_next))
    
24.     return np.inf, []
    
25. 
    
26. 
    
27. 
    
28. 
    
29. def min_turn_dfs(map, src, dst, current_direction = None):
    
30.     if src == dst:
    
31.         return 0, [src]
    
32.     m, n = map.shape
    
33.     ret = np.inf
    
34.     ret_path = []
    
35.     for direction in ((1,0), (0,1), (-1,0), (0,-1)):
    
36.         loc = (src[0]+direction[0], src[1]+direction[1])
    
37.         if loc[0] < 0 or loc[0] >= m or loc[1] < 0 or loc[1] >= n or map[loc[0],loc[1]] != 0:
    
38.             continue
    
39.         map[loc[0],loc[1]] = -1
    
40.         n_turns, path = min_turn(map, loc, dst, direction)
    
41.         map[loc[0],loc[1]] = 0
    
42.         if direction != current_direction:
    
43.             n_turns += 1
    
44.         if ret > n_turns:
    
45.             ret = n_turns
    
46.             ret_path = [src] + path
    
47.     return ret, ret_path
    
48. 
    
49. 
    
50. map = np.zeros((5,5))
    
51. map[1,1] = 1
    
52. map[2,2] = 1
    
53. map[3,3] = 1
    
54. map[3,0] = 1
    
55. map[4,1] = 1
    
56. 
    
57. n_turns, path = min_turn_bfs(map, (1,0), (4,2))
    
58. print(n_turns, path)
    
59. for p in path:
    
60.     map[p[0],p[1]] = -1
    
61. plt.figure()
    
62. plt.imshow(map)
    
63. plt.show()
    

复制代码