狗家VO过经

几周前面了狗家的VO，一共五轮，没有太难的题，但我自我感觉发挥不好，一道题给了很多提示才做出来，一道题没有写完，最后一道的follow up没有做出来。结果一周后recruiter居然打电话通知过了，安排两个team match mee

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

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

的产品评价系统，我正好有准备这个题目，这轮答的还可以。
第四轮：这道记不得了，应该不难，但我没有写完。
第五轮：类似最大岛屿面积，但岛屿包围的水也算岛屿的面积。

第二轮用bfs + priority queue就可以吧，按照时间的先后去遍历从A为起点的图，碰到已经处理过的或者时间点小于当前时间的直接过，最后visited数组里面一定是符合时间知道的人的顺序

1. from collections import defaultdict
   
2. from heapq import heappop, heappush
   
3. 
   
4. 
   
5. def whoKnowsMessage(messages):
   
6.     graph = defaultdict(list)
   
7.     member = set()
   
8.     for sender, receiver, time in messages:
   
9.         graph[sender].append((receiver, time))
   
10.         member.add(sender)
    
11.         member.add(receiver)
    
12.    
    
13.     availableMember = {}
    
14.     availableMember['A'] = 0
    
15.     pq = [(0, 'A')]
    
16.     while pq:
    
17.         time, person = heappop(pq)
    
18.         for receiver, receiveTime in graph[person]:
    
19.             if receiveTime < time:
    
20.                 continue
    
21.             if receiver in availableMember:
    
22.                 continue
    
23.             availableMember[receiver] = receiveTime
    
24.             heappush(pq, (receiveTime, receiver))
    
25.     res = {}
    
26.     for person in member:
    
27.         if person in availableMember:
    
28.             res[person] = True
    
29.         else:
    
30.             res[person] = False
    
31.    
    
32.     return res

复制代码

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

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

第二题应该就是dijkstra吧

求问最后一题有什么好思路吗？

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

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

我是从所有边上的0 出发DFS，把所有的0标记成一个特殊的值，然后再把剩下的0改成1。再DFS找最大岛。代码也比较复杂。

最后一题
从边上出发，把所有的水（0）都标记成2
这样matrix里面剩下的只有1（地）和0（被1包围的水）
然后做dfs，dfs遇到1和0都可以计入面积。跳过2

第二题是不是可以这样：
把所有event按照时间排序
scan一边，找到包含A的最小时间TA
TA之前的event都可以丢掉
TA之后的所有event，寻找A所在的连通图
连通图内的点都是true
union-find可解

请问最后一题有什么followup？

pop_flaky 发表于 2021-7-14 21:02
最后一题
从边上出发，把所有的水（0）都标记成2
这样matrix里面剩下的只有1（地）和0（被1包围的水）

从边出发，把水标记成2之后，matrix 的size 减去标为2的size 不就是最后答案了吗？

seabiscuit119 发表于 2021-7-14 21:40
从边出发，把水标记成2之后，matrix 的size 减去标为2的size 不就是最后答案了吗？

那是所有岛屿的面积之和
需要求其中最大岛屿的面积
岛屿之间可能有水隔开的

pop_flaky 发表于 2021-7-15 00:06
第二题是不是可以这样：
把所有event按照时间排序
scan一边，找到包含A的最小时间TA

嗯，我最后也是union find 做的。