新鲜详细的狗家跪经， 有一道题请大家指教

楼主由于时间原因，没来得及刷狗家的题，所以不知道是不是利口原题。直接在面筋里描述一下题好了。 面的是L5。 毛子出了一道楼主觉得很难的题，做不出来。后来在利口上找了一圈也没找到。如果大家看到过类似题，或知道答案，请分享！

第一轮写码：
在一个网络里，每个节点有一个整数值。节点之间用端口相连。节点之间可以发送和接收消息，消息一定会到达，但不保证递送顺序。消息本身需要自己定义。没有任何方法给某个节点分配全局识别码。所有节点组成一个无向图。
要求设计算法求出全局所有节点的值的总和。每个节点上跑的程序相同（出发节点会给一个布尔标记）。
这题概念上和路由器之间传递路由表的算法有些相似。

要实现的方法已经给好：
发送（消息，端口）
接收（消息，端口）



第二轮设计：
设计一个文档或文件分享系统。要求可以上传，下载和分享给其他用户。文件大小在100KB~10

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

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

楼主意识到毛子那题我没有描述清楚，导致同学们以为一个局部优化的方法可以解这道题。看一维的情况。假如有一个路上的点本来是：

姨 伞 吴 姨 姨

补充内容 (2021-2-13 15:39):
我们不能说走到姨的时候把姨变成伞，然后走到伞的时候把伞变成吴，就说这条路可以走通；我们说这条路能走通的前提是整条路上所有的节点必须保持不增。也就是说，我们至少要把这条路变成下面这样才能说它走得通。

补充内容 (2021-2-13 15:40):
吴 吴 吴 姨 姨

现在就是求在二维的情况下所有这样的路径中分数最小的一个。不知这样描述会不会更清楚一些。

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

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

第四题我的想法是 如果这个格子A要走到下一个格子B 需要把自己变成多大加上本来已经停留在格子A累积的cost 那么多于下一个格子B来说  这就是走到我这里的Cost. 代码如下 不知道对不对 请大神指正.

1.     public static int getMinCost(int[][] matrix){
   
2.         int[] dx={0,0,-1,1};
   
3.         int[] dy = {-1,1,0,0};
   
4.         int m = matrix.length, n = matrix[0].length;
   
5.         int[][] costs = new int[m][n];
   
6.         for(int[] row:costs){
   
7.             Arrays.fill(row,Integer.MAX_VALUE);
   
8.         }
   
9. 
   
10.         Queue<int[]> q = new LinkedList<>();
    
11.         q.add(new int[]{0,0,0});
    
12.         costs[0][0] = 0;
    
13.         while(!q.isEmpty()){
    
14.             int[] cur = q.poll();
    
15.             int x = cur[0],y = cur[1], cost = cur[2];
    
16.             for(int k=0;k<4;k++){
    
17.                 int nx = x+dx[k],ny=y+dy[k];
    
18.                 if(nx>=0&&nx<m&&ny>=0&&ny<n){
    
19.                     int ncost = cost+Math.max(matrix[nx][ny]-matrix[x][y],0);
    
20.                     if(ncost<costs[nx][ny]){
    
21.                         q.add(new int[]{nx,ny,ncost});
    
22.                         costs[nx][ny] = ncost;
    
23.                     }
    
24.                 }
    
25.             }
    
26.         }
    
27.         return costs[m-1][n-1];
    
28.     }

复制代码

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

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

感觉应该是leetcode 174?

第四问 followup ：memo +dfs or memo + bfs
用matrix记录 每个位置的最小cost 如果当前cost 小于最小cost ，更新最小cost 并访问它, 否则skip.

yangshao 发表于 2021-2-13 09:33
感觉应该是leetcode 174?

这题我看了下描述感觉不太一样。毛子那题你在每个格子可以做的选择有1）往4个方向中任意方向走和2)给当前格子增加多少数值；仪器斯这题好像只需要选方向。

不过确实有可能是某种变形。

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

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

journalfbus 发表于 2021-02-12 17:40:14
dfs+memo就是我在面试中尝试的方向，但没figure out转移方程。时间不够了。

最后recruiter提到最优解需要用到堆。听起来像是司令骑的变种。

往四个方向搜索, 这题其实也不算是dp，可能是想复杂了

lyronly 发表于 2021-2-13 09:46
往四个方向搜索, 这题其实也不算是dp，可能是想复杂了

我一上来有分析过brute force的时间复杂度。如果直接搜不保存中间结果的话时间会爆掉。面试官直接说我们想更优的办法吧。

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

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

第四题是不是可以看成Dijkstra
从a走到相邻的b，cost是max（0，b-a）

不过第一轮的题目怎么做呀

第四题是 priority queue + bfs? 每次pop出cost最小的路径