10.11狗狗onsite

没怎么在地里发过面经 鉴于狗狗的面经还比较有价值 也是最后一个面试了... 来回馈一下论坛~~ 顺便给面试攒人品4轮 mtv
1. exam room 变形, 其实

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

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

t="" />

如果有用, 兄弟姐妹们来点米 thx!


补充内容 (2018-11-20 12:22):
忘了updates 已offer

打了个注释， 供君参考

1. static class Node{
   
2.                 int key;
   
3.                 Set<Node> to;
   
4.                 Set<Node> from;
   
5.                 public Node(){
   
6.                         to = new HashSet<>();
   
7.                         from = new HashSet<>();
   
8.                 }
   
9.         }
   
10.        
    
11.         public int minReverse(Node source, Node end){
    
12.                 Set<Node> visited = new HashSet<>();
    
13.                
    
14.                 Deque<Node> que = new ArrayDeque<>();
    
15.                
    
16.                 // init the que with nodes that can achieve with 0 reverse
    
17.                 if(DFS(que, source, visited, end)) return 0;
    
18.                
    
19.                 int time = 1;
    
20.                 while(!que.isEmpty()){
    
21.                         int size = que.size();
    
22.                         // for all the node in next layer
    
23.                         for(int i = 0; i < size; i++){
    
24.                                 Node temp = que.poll();
    
25.                                 // only reverse one edge
    
26.                                 for(Node node : temp.from){
    
27.                                         // if find the end node, return the current the layer
    
28.                                         if(DFS(que, node, visited, end)) return time;
    
29.                                 }
    
30.                         }
    
31.                         // use one more reverse edges
    
32.                         time++;
    
33.                 }
    
34.                 return -1;
    
35.         }
    
36.        
    
37.         private boolean DFS(Deque<Node> que, Node node, Set<Node> visited, Node end){
    
38.                 // find end
    
39.                 if(node == end) return true;
    
40.                 // already visited
    
41.                 if(visited.contains(node)) return false;
    
42.                
    
43.                 // add to next layer
    
44.                 que.offer(node);
    
45.                
    
46.                 // make it visited
    
47.                 visited.add(node);
    
48.                
    
49.                 // visited all the node it can achieve without reverse an edge
    
50.                 for(Node next : node.to){
    
51.                         if(DFS(que, next, visited, end)) return true;
    
52.                 }
    
53.                
    
54.                 // not find end
    
55.                 return false;
    
56.         }

复制代码

发一个第三题的代码，思路如下：
BFS + DFS，
BFS 第i层，表示最少reverse i edges可以到达的node
DFS 表示以当前点， 按正常path遍历的到的点，
BFS 每次expand都expand直接指向该点node  的所有点 所能到达的点。
时间复杂度是O(E + V);

代码如下：

1.         static class Node{
   
2.                 int key;
   
3.                 Set<Node> to;
   
4.                 Set<Node> from;
   
5.                 public Node(){
   
6.                         to = new HashSet<>();
   
7.                         from = new HashSet<>();
   
8.                 }
   
9.         }
   
10.        
    
11.         public int minReverse(Node source, Node end){
    
12.                 Set<Node> visited = new HashSet<>();
    
13.                
    
14.                 Deque<Node> que = new ArrayDeque<>();
    
15.                
    
16.                 que.offer(source);
    
17.                
    
18.                 if(DFS(que, source, visited, end)) return 0;
    
19.                
    
20.                 int time = 1;
    
21.                 while(!que.isEmpty()){
    
22.                         int size = que.size();
    
23.                         for(int i = 0; i < size; i++){
    
24.                                 Node temp = que.poll();
    
25.                                 for(Node node : temp.from){
    
26.                                         if(DFS(que, node, visited, end)) return time;
    
27.                                 }
    
28.                         }
    
29.                         time++;
    
30.                 }
    
31.                 return -1;
    
32.         }
    
33.        
    
34.         private boolean DFS(Deque<Node> que, Node node, Set<Node> visited, Node end){
    
35.                 if(node == end) return true;
    
36.                
    
37.                 if(visited.contains(node)) return false;
    
38.                
    
39.                 que.offer(node);
    
40.                 visited.add(node);
    
41.                
    
42.                 for(Node next : node.to){
    
43.                         if(DFS(que, next, visited, end)) return true;
    
44.                 }
    
45.                
    
46.                 return false;
    
47.         }

复制代码

已加米，求问第三轮应该用什么方法做比较好呢

来自一亩三分地官方APP

cszhazha 发表于 2018-10-12 13:09
已加米，求问第三轮应该用什么方法做比较好呢

来自一亩三分地官方APP

https://www.geeksforgeeks.org/mi ... source-destination/

第四轮没有看懂 LZ能给个例子吗？

wtcupup 发表于 2018-10-12 13:12
第四轮没有看懂 LZ能给个例子吗？

例如 4 3 2 3 2
第一次是两个2合并 变成 4 3 3 4
然后 4 6 4
然后 6 8 over

第二题请问楼主是用什么方法做的呀 之前看过这题但一直没想出什么好解法！感谢

zhengxixiao827 发表于 2018-10-13 02:07
第二题请问楼主是用什么方法做的呀 之前看过这题但一直没想出什么好解法！感谢

我是类似蠡口上的 数多少个corner rectangle  忘记题号了..... 一层一层扫 map存每两个点的pair

wannagotousa 发表于 2018-10-13 02:11
我是类似蠡口上的 数多少个corner rectangle  忘记题号了..... 一层一层扫 map存每两个点的pair

这题我也看了 所以找最小就是按照那个题的方法 一层层扫然后不断存pair和更新最小值？

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

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

wannagotousa 发表于 2018-10-13 02:15
嗯 ..  我也不知道这能不能过  反正面试官说他没见过我这方法 貌似满意

ok！祝楼主拿offer！