刀大匙 新鲜电面

10分钟前的新鲜面经， 一个湾湾小哥面的，在doordash待了三年半了已经。

题目比较有意思，感觉是小哥自己出的题， 有点类似简易版的word ladder II

题目大概就是说， doordash 送餐有几条路线， 让你求出从a 到b的最短路径

给你一个list of tuples
Roa

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

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

要自己import library 和写test case。 尽量多和面试官沟通 把test case过一遍就没问题。

顺便再po一下我的代码哈

1. 
   
2. import java.util.*;
   
3. 
   
4. class Solution {
   
5.      
   
6.      public static void main(String[] args) {
   
7.          Solution shortestPath = new Solution();
   
8.          Map<Integer, List<Integer>> map = new HashMap<>();
   
9.          map.put(0, Arrays.asList(1, 2, 1));
   
10.          map.put(1, Arrays.asList(2, 3, 1));
    
11.          map.put(2, Arrays.asList(3, 4, 1));
    
12.          map.put(3, Arrays.asList(4, 5, 1));
    
13.          map.put(4, Arrays.asList(5, 1, 3));
    
14.          map.put(5, Arrays.asList(1, 3, 2));
    
15.          map.put(6, Arrays.asList(5, 3, 1));
    
16.          
    
17.          List<Integer> cities = Arrays.asList(1, 2, 3, 4, 5);
    
18.          
    
19.          boolean[] res = shortestPath.shortestPath(map, cities);
    
20.          
    
21.          for (boolean used : res) {
    
22.             System.out.println(used + ", ");
    
23.          }
    
24.      }
    
25.      
    
26.     // given a map of bidrectional routes
    
27.     // find a shortest path
    
28.     public boolean[] shortestPath(Map<Integer, List<Integer>> map, List<Integer> cities) {
    
29.         // 1 (1, 2, 1)
    
30.         // 1 -> [2, 1, 1]
    
31.         Map<Integer, List<int[]>> graph = new HashMap<>();
    
32.         
    
33.         for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
    
34.             int road = entry.getKey();
    
35.             List<Integer> value = entry.getValue();
    
36.             int from = value.get(0);
    
37.             int to = value.get(1);
    
38.             int weight = value.get(2);
    
39.             
    
40.             graph.computeIfAbsent(from, k -> new ArrayList<>()).add(new int[]{to, weight, road});
    
41.             graph.computeIfAbsent(to, k -> new ArrayList<>()).add(new int[]{from, weight, road});
    
42.         }
    
43.         
    
44.         // [city_id, sumOfWeight]
    
45.         PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    
46.         Set<Integer> visited = new HashSet<>();
    
47.         pq.offer(new int[]{cities.get(0), 0});
    
48.         int targetCity = cities.get(cities.size() - 1);
    
49.         int lowestWeight = 0;
    
50.         
    
51.         while (!pq.isEmpty()) {
    
52.             int[] entry = pq.poll();
    
53.             
    
54.             if (entry[0] == targetCity) {
    
55.                 lowestWeight = entry[1];
    
56.                 break;
    
57.             }
    
58.             
    
59.             visited.add(entry[0]);
    
60.             
    
61.             for (int[] neis : graph.get(entry[0])) {
    
62.                 if (!visited.contains(neis[0])) {
    
63.                     pq.offer(new int[]{neis[0], entry[1] + neis[1]});
    
64.                 }
    
65.             }
    
66.         }
    
67.         
    
68.         boolean[] res = new boolean[map.size()];
    
69.         
    
70.         dfs(cities.get(0), targetCity, graph, lowestWeight, res, new HashSet<>());
    
71.         return res;
    
72.     }
    
73.    
    
74.     private void dfs(int from, int target, Map<Integer, List<int[]>> graph, int weight, boolean[] res, Set<Integer> roads) {
    
75.         if (weight < 0) {
    
76.             return;      
    
77.         }
    
78.         
    
79.         if (from == target) {
    
80.             for (int road : roads) {
    
81.                 res[road] = true;
    
82.             }
    
83.         }
    
84.         
    
85.         for (int[] neis : graph.get(from)) {
    
86.             // add the road
    
87.             if (!roads.contains(neis[2])) {
    
88.                 roads.add(neis[2]);
    
89.                 dfs(neis[0], target, graph, weight - neis[1], res, roads);
    
90.                 roads.remove(neis[2]);
    
91.             }
    
92.         }
    
93.     }
    
94. }

复制代码

好奇楼主 为什么结果有 1 → 5，1 → 2 → 3 → 5, and 1 → 3 → 5
就第一个来说from -> to 里面没有从1直接到5的，难道这个是无向图吗？还是楼主不小心写错了呀

Super simple solution using python (please add rice if you like it!!!)

1. def min_path(self, start, end, edges, n):
   
2.         
   
3.         from collections import defaultdict
   
4.         
   
5.         edge_map = defaultdict(list)
   
6.         
   
7.         for edge in edges:
   
8.             parent, child, weight = edge
   
9.             edge_map[parent].append((child, weight))
   
10.             
    
11.         visited = [0] * n
    
12.             
    
13.         def recur(node):
    
14.             if node == end:
    
15.                 return 0
    
16.             if node not in edge_map:
    
17.                 return -1
    
18.             childs = edge_map[node]
    
19.             
    
20.             layer = []
    
21.             for child, weight in childs:
    
22.                 if visited[child-1]:
    
23.                     continue
    
24.                 visited[child-1] = 1
    
25.                 tmp = recur(child)
    
26.                 if tmp >= 0:
    
27.                     layer.append(tmp + weight)
    
28.             
    
29.             if not layer:
    
30.                 return -1
    
31.             else:
    
32.                 return min(layer)
    
33.             
    
34.         return recur(start)

复制代码

niubuzhi 发表于 2021-10-28 07:26
Super simple solution using python (please add rice if you like it!!!)

The previous version has some minor bug. I modified the code as follows:

1. def min_path(self, start, end, edges, n):
   
2.         
   
3.         from collections import defaultdict
   
4.         
   
5.         edge_map = defaultdict(list)
   
6.         
   
7.         for edge in edges:
   
8.             parent, child, weight = edge
   
9.             edge_map[parent].append((child, weight))
   
10.             
    
11.         values = [0] * (n+1)
    
12.             
    
13.         def recur(node):
    
14.             if node == end:
    
15.                 values[node] = 0
    
16.             if node not in edge_map:
    
17.                 values[node] = -1
    
18.             if values[node]:
    
19.                 return values[node]
    
20. 
    
21.             layer = []
    
22.             for child, weight in edge_map[node]:
    
23.                 tmp = recur(child)
    
24.                 if tmp >= 0:
    
25.                     layer.append(tmp + weight)
    
26.             
    
27.             if not layer:
    
28.                 values[node] = -1
    
29.             else:
    
30.                 values[node] = min(layer)
    
31. 
    
32.             return values[node]
    
33.             
    
34.         return recur(start)

复制代码

请问楼主DoorDash的电面是AUDIO ONLY吗？ 我收到的电面邀请是这个，不知道做题还是就瞎聊？

l0ganic 发表于 2021-07-17 11:41:58
请问楼主DoorDash的电面是AUDIO ONLY吗？ 我收到的电面邀请是这个，不知道做题还是就瞎聊？

说是audio only 但我后来忘关camera了. 我的话差不多自我介绍两三分钟 四十分钟做题 然后剩下时间就是open-ended questions

道理上的确不难，不过面试写这么多dijkstra + dfs backtracking 还是让人失心疯，尤其写Java的。。555

这题按LeetCode难度应该是hard级别吧....

同意啊，这题好难啊

今天面了同样的题。。太丧心病狂了。可能和楼主是一个面试官。

想问一下为什么不用bfs然后create一个专门的node class来存path

vivan_66 发表于 2021-9-14 13:47
想问一下为什么不用bfs然后create一个专门的node class来存path

空间占用太大，面试官估计会不满意

vivan_66 发表于 2021-9-14 10:47
想问一下为什么不用bfs然后create一个专门的node class来存path

问的好，
我米又限 什么也看不见，为什么不是一个start 和一个end 城市，怎么会是一个城市list？