snap VO 废

金元宝儿 发表于 2023-9-3 07:38
那就按照正反两面数字各生成一个sorted array，但他们的element set一样，都是一组牌的objects，每个牌去 ...

牌A的正可以和牌B的正反两面连在一起，B连A也一样。两个array怎么考虑即便只有两张牌就有的四种情况

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

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

realife 发表于 2023-9-3 18:18
你的意思是【1，2】，【1，3】，【1，1】这些都在节点1汇合？
这样找不出最长路径啊，而且【1，1】这种 ...

1. 
   
2. d = [[1, 2], [4, 5], [2, 2], [2, 3]]
   
3. 
   
4. g = defaultdict(list)
   
5. 
   
6. for i, (a, b) in enumerate(d):
   
7.     g[a].append(i)
   
8.     if a != b:
   
9.         g[b].append(i)
   
10. 
    
11. # defaultdict(list, {1: [0], 2: [0, 2, 3], 4: [1], 5: [1], 3: [3]})

复制代码

然后对每个value array做union find 求最大组吧

请问lz您面的是哪个组/org啊？是infra吗？
感觉第一题纯属倒霉。

匿名用户 发表于 2023-09-11 17:12:31
请问lz您面的是哪个组/org啊？是infra吗？
感觉第一题纯属倒霉。

好像不是组面，碰到这题确实有点倒霉，怎么也想不出最优解，虽然很快写了个解法出来

店面那题的“另一种”解法是利用node.next.left/right吧？感觉有很多edge case，BFS简单直接，面试够用了吧哈哈

1. public class ConnectNextRight {
   
2.     public Node connect(Node root) {
   
3.         if (root == null) {
   
4.             return null;
   
5.         }
   
6.         
   
7.         Queue<Node> queue = new LinkedList<>();
   
8.         queue.offer(root);
   
9.         
   
10.         while (!queue.isEmpty()) {
    
11.             int levelSize = queue.size();
    
12.             Node prev = null;
    
13.             
    
14.             for (int i = 0; i < levelSize; i++) {
    
15.                 Node current = queue.poll();
    
16.                
    
17.                 if (prev != null) {
    
18.                     prev.next = current;
    
19.                 }
    
20.                
    
21.                 prev = current;
    
22.                
    
23.                 if (current.left != null) {
    
24.                     queue.offer(current.left);
    
25.                 }
    
26.                 if (current.right != null) {
    
27.                     queue.offer(current.right);
    
28.                 }
    
29.             }
    
30.         }
    
31.         
    
32.         return root;
    
33.     }
    
34. }

复制代码

2013fall 发表于 2023-09-16 16:27:38
店面那题的“另一种”解法是利用node.next.left/right吧？感觉有很多edge case，BFS简单直接，面试够用了吧哈哈public class ConnectNextRight {

写了这个，要求优化，所以bfs看来不够另面试官满意

realife 发表于 2023-9-16 16:37
写了这个，要求优化，所以bfs看来不够另面试官满意

🙏要求很严格啊

楼主可以解释一下你的map的解法是什么么？ <val, list of cards> ?

个人理解第一题应该是考欧拉路径。更优化的方法是1.检查这个无向图中有没有欧拉路径，1.1 有的话，欧拉路径的长度就是longest path length 1.2 没有的话，就是会出现奇数度数的node多于2个的情况，这个时候我们需要remove 最少的edge来让奇数度数的node==2，这样剩下的edge能组成欧拉路径。