snap VO 废

面了有两个多月了，因为有一题一直不知道怎么做，还是发出来看看有没有更好的解法。

店面是给二叉树加个next 链接那题，这题不在tag里。知道有个很巧妙的解法，一时半会想不起来，就来了个层序遍历解。
做完问能不能优化，这会也大概想起来具体解法了，就回忆着写出了。是个烙印在那边7-8年了，还很有热情不容易，负责
一些scope挺大的项目。夸了他

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

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

前面心情不佳有影响。
最后一轮设计distributed cache，面试官很满意。每轮都有一些bq题，不觉得会丢分。

第一轮的题很想知道到底在考什么，有很smart的解法吗？

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 求最大组吧

1. class TreeNode:
   
2.     def __init__(self, val=0, left=None, right=None, next=None):
   
3.         self.val = val
   
4.         self.left = left
   
5.         self.right = right
   
6.         self.next = next
   
7. 
   
8. def connect(root):
   
9.     if not root:
   
10.         return root
    
11. 
    
12.     level_start = root  # 指向每一层的起始节点
    
13. 
    
14.     while level_start:
    
15.         current = level_start  # 用于遍历当前层级的节点
    
16.         next_level_start = None  # 用于指向下一层级的起始节点
    
17. 
    
18.         while current:
    
19.             if current.left:
    
20.                 if next_level_start is None:
    
21.                     next_level_start = current.left
    
22.                 else:
    
23.                     current.next = current.left
    
24.                 current = current.left
    
25. 
    
26.             if current.right:
    
27.                 if next_level_start is None:
    
28.                     next_level_start = current.right
    
29.                 else:
    
30.                     current.next = current.right
    
31.                 current = current.right
    
32. 
    
33.             current = current.next  # 移动到当前层级的下一个节点
    
34.         level_start = next_level_start  # 移动到下一层级的起始节点
    
35.     return root
    
36. 
    
37. # 示例用法：
    
38. # 创建一个二叉树
    
39. #        1
    
40. #       / \
    
41. #      2   3
    
42. #     / \   \
    
43. #    4   5   7
    
44. root = TreeNode(1)
    
45. root.left = TreeNode(2)
    
46. root.right = TreeNode(3)
    
47. root.left.left = TreeNode(4)
    
48. root.left.right = TreeNode(5)
    
49. root.right.right = TreeNode(7)
    
50. 
    
51. # 连接每个节点到它的下一个相邻节点
    
52. connected_root = connect(root)
    
53. 
    
54. # 打印连接后的二叉树
    
55. print(connected_root.left.next.val)  # 输出 3，因为 2 的下一个相邻节点是 3
    
56. print(connected_root.left.left.next.val)  # 输出 5，因为 4 的下一个相邻节点是 5
    

复制代码

店面那题的“另一种”解法是利用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. }

复制代码

不能按end排序，用start binary search来build edge吗

金元宝儿 发表于 2023-9-2 15:20
不能按end排序，用start binary search来build edge吗

不明白什么意思，怎么找最长呢？一张牌只能用一次，【1，2】了就不能再按【2，1】备选

忘了说点数是从0到6，还有个条件是说最多26张牌，就是不知道这个有什么用处

Chasedream.df 发表于 2023-9-2 20:48

这题不用recursion是最符合要求的解法
我一开始以为是贴了domino那题的解法呢

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

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

感觉domino那题是扫一遍建个图，然后找图里面的最长路径。

richard_515 发表于 2023-9-3 10:30
感觉domino那题是扫一遍建个图，然后找图里面的最长路径。

我一直没有弄明白的就是一张牌可以翻面，等于有两个选择。如果没有smart的方法处理的话就等于有
2 ^n条路径。不知道你讲的建图是怎么建的

realife 发表于 2023-09-03 11:02:40
我一直没有弄明白的就是一张牌可以翻面，等于有两个选择。如果没有smart的方法处理的话就等于有
2 ^n条路径。不知道你讲的建图是怎么建的

可以翻面就是无向图，节点就是1，2，3这些数字，每张牌都是一个路径。感觉自己连自己的路径需要处理一下。

richard_515 发表于 2023-9-3 11:05
可以翻面就是无向图，节点就是1，2，3这些数字，每张牌都是一个路径。感觉自己连自己的路径需要处理一下。

你的意思是【1，2】，【1，3】，【1，1】这些都在节点1汇合？
这样找不出最长路径啊，而且【1，1】这种成环的怎么处理