狗家电面

下午刚面的，投的是苏黎世的Software Engineer岗，面试是一个三哥，上来互相自我介绍然后就给了一道题题意是有一群小伙伴在不同位置，中午约吃饭，附近有好几个cafe, 返回最快所有人聚首的时间。 给的inp

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

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

)访问过的时候返回当前的步数，当queue遍历完则返回nil

当中有个BUG直到带入数据才发现=-=不知道是不是凉了，哎，求点米看面经！谢谢！！

匿名者 发表于 2022-5-17 02:15
lz 面的什么level呀，感谢！

面的是L4

感觉这道题和 在空地上建立邮局，使得到达所有房子距离之和最小 本质上非常类似，不同点在于一个是求和，一个是求最大值；一个是2维Grid，一个是直接给出edge list （connection）。
应该就是BFS的思路（如果时间等同于步数的话）。
优化的话，就是根据人数和Cafe数，选择从人出发到Cafe，还是从Cafe出发到人。

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

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

而舅硫的简化版本？
union find 可以o(n) 判断 ppl 和 cafe是否联通。
用quick select找到所有人的重心， o(n)
find the nearest cafe by that median point? logm if sorted

leonsu7777 发表于 2022-5-16 07:09
而舅硫的简化版本？
union find 可以o(n) 判断 ppl 和 cafe是否联通。
用quick select找到所有人的重心， ...

只有ID , 没有坐标 怎么找重心？

lz 面的什么level呀，感谢！

这题能不能用hashmap 建立无向图 然后对所有的cafe分别做一次bfs 每次bfs都记录能到达的人的数量 当全部人都可以到达的时候 记录最小时间

have_fun 发表于 2022-05-17 12:57:47
这题能不能用hashmap 建立无向图 然后对所有的cafe分别做一次bfs 每次bfs都记录能到达的人的数量 当全部人都可以到达的时候 记录最小时间

对，这个跟我的解法差不多，就是建立图之后是从人出发还是cafe出发，时间复杂度应该是差不多的

收到通知过了约下一轮了，到时候分享VO