DoorDash 2023 SDE NG OA 10.4

10.4 新鲜OA 求米！！！！！
如地理所说，

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

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

我还准备了常见A->C->B的代码但没用上，而且不一定保证对，放在下面要是有人需要自取，求米！！！！！！！！

1. [hide=188<img src="https://www.1point3acres.com/bbs/forum.php?mod=image&aid=477382&size=300x300&key=ddaecc605bdc30ad&nocache=yes&type=fixnone" border="0" aid="attachimg_477382" alt=""><img src="https://www.1point3acres.com/bbs/forum.php?mod=image&aid=477383&size=300x300&key=e9522bef61b98f12&nocache=yes&type=fixnone" border="0" aid="attachimg_477383" alt=""><img src="https://www.1point3acres.com/bbs/forum.php?mod=image&aid=477384&size=300x300&key=e1c7e1631d7def91&nocache=yes&type=fixnone" border="0" aid="attachimg_477384" alt="">]import java.util.*;
   
2. 
   
3. public class DoorDash {
   
4. 
   
5.     public static long getShortestRoute(int roadsNotes, List<Integer> roadsFrom, List<Integer> roadsTo, List<Integer> roadsWeight, int a, int b, int c) {
   
6.         int[][] adjMatrix = new int[roadsNotes][roadsNotes];
   
7.         for(int i = 0; i < roadsFrom.size(); i++) {
   
8.             adjMatrix[roadsFrom.get(i)][roadsTo.get(i)] = roadsWeight.get(i);
   
9.             adjMatrix[roadsTo.get(i)][roadsFrom.get(i)] = roadsWeight.get(i);
   
10.         }
    
11.         HashSet<Integer> set = new HashSet<>();
    
12.         long l1 = dijkstra(adjMatrix,set, a, c);
    
13.         System.out.println(set);
    
14.         long l2 = Long.MAX_VALUE;
    
15.         for(int node : set) {
    
16.             l2 = Math.min(l2, dijkstra(adjMatrix, node, b));
    
17.         }
    
18.         System.out.println(l1);
    
19.         System.out.println(l2);
    
20.         if(l1 == Long.MAX_VALUE || l2 == Long.MAX_VALUE) {
    
21.             return -1;
    
22.         }
    
23.         return l1 + l2;
    
24.     }
    
25. 
    
26.     public static long dijkstra(int[][] matrix, int from, int to) {
    
27.         long[] d = new long[matrix.length];
    
28.         for(int i = 0; i < d.length; i++) {
    
29.             d[i] = Long.MAX_VALUE;
    
30.         }
    
31.         d[from] = 0;
    
32.         PriorityQueue<long[]> pq = new PriorityQueue<>((a,b) -> (int) (a[1] - b[1]));
    
33.         pq.offer(new long[]{from, d[from]});
    
34.         while(!pq.isEmpty()) {
    
35.             long[] currNode = pq.poll();
    
36.             int node = (int)currNode[0];
    
37.             long distance = currNode[1];
    
38.             if(node == to) {
    
39.                 return distance;
    
40.             }
    
41.             for(int i = 0; i < matrix.length; i++) {
    
42.                 if(matrix[node][i] > 0) {
    
43.                     long dU = distance;
    
44.                     long dV = d[i];
    
45.                     int wUV = matrix[node][i];
    
46.                     if(dU + (long)wUV < dV) {
    
47.                         d[i] = dU + (long)wUV;
    
48.                         pq.offer(new long[]{i, d[i]});
    
49.                     }
    
50.                 }
    
51.             }
    
52.         }
    
53.         return d[to];
    
54.     }
    
55. 
    
56.     public static long dijkstra(int[][] matrix,HashSet<Integer> set, int from, int to) {
    
57.         long[] d = new long[matrix.length];
    
58.         for(int i = 0; i < d.length; i++) {
    
59.             d[i] = Long.MAX_VALUE;
    
60.         }
    
61.         d[from] = 0;
    
62.         PriorityQueue<long[]> pq = new PriorityQueue<>((a,b) -> (int) (a[1] - b[1]));
    
63.         pq.offer(new long[]{from, d[from]});
    
64.         set.add(from);
    
65.         while(!pq.isEmpty()) {
    
66.             long[] currNode = pq.poll();
    
67.             int node = (int)currNode[0];
    
68.             long distance = currNode[1];
    
69.             set.add(node);
    
70.             if(node == to) {
    
71.                 return distance;
    
72.             }
    
73.             for(int i = 0; i < matrix.length; i++) {
    
74.                 if(matrix[node][i] > 0) {
    
75.                     long dU = distance;
    
76.                     long dV = d[i];
    
77.                     int wUV = matrix[node][i];
    
78.                     if(dU + (long)wUV < dV) {
    
79.                         d[i] = dU + (long)wUV;
    
80.                         pq.offer(new long[]{i, d[i]});
    
81.                     }
    
82.                 }
    
83.             }
    
84.         }
    
85.         return d[to];
    
86.     }
    
87. 
    
88.     public static void main(String[] args) {
    
89.         List<Integer> from = new ArrayList<>();
    
90.         from.add(0);
    
91.         from.add(0);
    
92.         from.add(0);
    
93.         List<Integer> to = new ArrayList<>();
    
94.         to.add(2);
    
95.         to.add(1);
    
96.         to.add(3);
    
97.         List<Integer> weight = new ArrayList<>();
    
98.         weight.add(1);
    
99.         weight.add(2);
    
100.         weight.add(3);
     
101.         long d = getShortestRoute(4, from, to, weight, 1, 3, 2);
     
102.         System.out.println(d);
     
103.     }
     
104. }[/hide]
     

复制代码

第一题楼主用的是2分搜索吗

微信用户_d4e941f 发表于 2022-10-5 16:10
第一题楼主用的是2分搜索吗

没 我用的二维DP 但没做完 时间就到了 一共就过了三个基础例子。。。 我感觉思路是可行的 二分搜索的话你可以试试，听起来也蛮可行的
求米求米

第一题，要是strB本身就是strA的subsequence（没有需要remove的）结果应该是0还是1呢？

匿名用户 发表于 2022-10-6 16:53
第一题，要是strB本身就是strA的subsequence（没有需要remove的）结果应该是0还是1呢？

0 紫薯求米

匿名用户 发表于 2022-10-7 12:54
0 紫薯求米

谢谢，已加米

已加米，请问第二题是两个实习生分配任务那个吗？

风纪委员 发表于 2022-10-8 20:02
已加米，请问第二题是两个实习生分配任务那个吗？

是的 紫薯紫薯

请问第二题是1029？

匿名用户 发表于 2022-10-11 16:14
请问第二题是1029？

是的 但是北京内容不一样，贪心的思想一样的