刀带史VO挂经

分享一个刀带史VO挂经

coding 1

蠡口吴刘凌
接下来问了如果改成是一个binary tree的话，如何找到a path sum to k，a path必须是从上到下的

system design
经典捐款系统 运行三天

coding 2
这个题估计是一个新题库题，面试官有完整的一套code，description，和testcases
具体variable的形式和名字不记得了，you get the idea
输入
1. List&l

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

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

diversity?




补充内容 (2022-02-27 03:59 +8:00):
Graph是undirected，可以跳过input 1，直接看input 3就可以了 有path 0->1的话就有path 1->0 time cost也是一样的

写了一下第二题， 请大家看看有没有什么问题多多指教，time complexity我自己也搞不清楚 感觉是O(N^2)？
并且说一下 第一个条件canGoTo确实没有用上 因为假设timecost和points都必须给全了info

1. import java.util.*;
   
2. 
   
3. public class HighestPointsUnderTimeLimit {
   
4. 
   
5.     public static int highestPoint;
   
6.     public static int limit;
   
7.     public static int getHighestPoint(List<List<Integer>> canGoTo, int[] points, int[][] timeCost, int timeLimit){
   
8.         highestPoint = 0;
   
9.         limit = timeLimit;
   
10.         Map<Integer, Map<Integer, int[]>> srcToDestPointsCost = new HashMap<>();
    
11. 
    
12.         for(int i = 0; i < timeCost.length; i++){
    
13.             int src = timeCost[i][0];
    
14.             int dest = timeCost[i][1];
    
15.             int cost = timeCost[i][2];
    
16.             int srcPoint = points[src];
    
17.             int destPoint = points[dest];
    
18.             int[] srcToDest = new int[]{destPoint, cost};
    
19.             int[] destToSrc = new int[]{srcPoint, cost};
    
20.             srcToDestPointsCost.computeIfAbsent(src, v -> new HashMap<>()).putIfAbsent(dest, srcToDest);
    
21.             srcToDestPointsCost.computeIfAbsent(dest, v -> new HashMap<>()).putIfAbsent(src, destToSrc);
    
22.         }
    
23.         LinkedList<Integer> currPath = new LinkedList<>();
    
24.         currPath.add(0);
    
25.         dfs(srcToDestPointsCost, 0, points[0], 0, true, currPath);
    
26. 
    
27.         return highestPoint;
    
28.     }
    
29. 
    
30.     private static void dfs(Map<Integer, Map<Integer, int[]>> srcToDestPointsCost, int start, int currPoints, int currTime, boolean isStart, LinkedList<Integer> currPath){
    
31.         if((start == 0 && !isStart && currTime <= limit)){
    
32.             System.out.println(Arrays.toString(currPath.toArray()));
    
33.             highestPoint = Math.max(highestPoint, currPoints);
    
34.             return;
    
35.         } else if(currTime > limit){
    
36.             return;
    
37.         }
    
38. 
    
39.         if(start == 0){
    
40.             isStart = false;
    
41.         }
    
42. 
    
43.         Map<Integer, int[]> nextStops = srcToDestPointsCost.get(start);
    
44.         for(Integer nextStart : nextStops.keySet()){
    
45.             int[] info = nextStops.get(nextStart);
    
46.             int newPoints = currPoints + info[0];
    
47.             int newTime = currTime + info[1];
    
48.             currPath.add(nextStart);
    
49.             dfs(srcToDestPointsCost, nextStart, newPoints, newTime, isStart, currPath);
    
50.             currPath.remove(nextStart);
    
51.         }
    
52. 
    
53.     }
    
54. 
    
55.     public static void main(String args[]) {
    
56.         List<List<Integer>> canGoTo = new ArrayList<>();
    
57.         Integer[] l1 = new Integer[]{1, 2, 3};
    
58.         Integer[] l2 = new Integer[]{3};
    
59.         canGoTo.add(Arrays.asList(l1));
    
60.         canGoTo.add(Arrays.asList(l2));
    
61. 
    
62.         int[] points = new int[]{5, 10, 3, 20};
    
63.         int[][] timeCost = new int[][]{{0, 1, 10}, {0, 2, 4}, {0, 3, 60}, {1, 3, 40}};
    
64.         int timeLimit = 90;
    
65. 
    
66.         System.out.println(getHighestPoint(canGoTo, points, timeCost, timeLimit));
    
67.     }
    
68. }

复制代码

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

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

请问coding2这个题目 如果0可以到1 但是list中没有显示1可以到达0， 是否表示这个是directed graph 不能有0->1->0这条通路？ 比较像力扣漆吧漆？

csmyhappy 发表于 2022-2-26 11:29
请问coding2这个题目 如果0可以到1 但是list中没有显示1可以到达0， 是否表示这个是directed graph 不能有0 ...

graph 是undirected 第一个条件其实有点redundant

匿名者 发表于 2022-2-26 11:59
graph 是undirected 第一个条件其实有点redundant

这题好难啊 绝望

csmyhappy 发表于 2022-2-26 15:33
这题好难啊 绝望

这个题应该就是try everything

匿名者 发表于 2022-2-26 16:34
这个题应该就是try everything

是的 感觉DFS能做  Dijsktra做不了

第二题和airbnb的滑雪题很像

Donation SD 能说的更具体点吗？好多人都提到过 但是没有具体描述 多谢了！

csmyhappy 发表于 2022-02-26 17:41:32
是的 感觉DFS能做  Dijsktra做不了

怎么try everything? DFS 的同时看看时间够不够，而且看看能不能到起点？