Snap - Phone Screen L4 (January 2022)

Please give me rice :)

Coding Questions:

Suppose you are in a grid with your friends:
"100000"
"020000"
"202020"
"002002"The 1 represents your position. The 2s represent the position o

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

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

question. Make a tree from all the pairs of friends. Use a Union Find or Bellman-Ford.

Not sure if OP's union find or Bellman-Ford algorithms would be more efficient but I think this is doable by doing a DFS over all friend-friend pairs and calculating the distance between them in the grid as the edge weight. It would end something like O(n! + r*c) where n = number of friends and r, c are rows and columns of the input grid.

楼主过了吗

请问Union Find 怎么做，还有可以用bfs/dfs吗？

Can you share the union find idea ?

刷题汪巴思琪

热心的机器猫 发表于 2023-2-20 01:39
请问Union Find 怎么做，还有可以用bfs/dfs吗？

BFS and DFS won't work here. You can find the standard Union Find algorithms on LeetCode.