一道graph面经题讨论

最近面的salesforce的一道题，我记得我在谷歌面经里面看到过这题。

题目描述是，有一个图的node 代表一个城市， 每两个城市之间有一个correlation 的weight. 比如城市

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

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

该是 (a, b) 或者 (a, c)  不能是（a， b， c） 因为b c的weight大于1.5。  

xiaozhuxiaozhu 发表于 2021-10-2 19:21
这个例子 怎么去掉边呢。

比如三个城市 ,a, b, c， threshold是 1.5

如果我没理解错你的意思，任何路径只要包含了E(b, c)，或者任何超过threshold.的边，就算超过threshold不合格。那么建adjacency list的时候，也就没必要把E(b, c)加进来了。

1. 
   
2. 
   
3. uf = UnionFind()
   
4. for u, v, w in edges:
   
5.     if w > threshold:
   
6.         continue
   
7.      uf.union(u, v)

复制代码

xiaozhuxiaozhu 发表于 2021-10-2 18:51
感谢分享，我看了一下那题，我刷过那道。 我题目描述可能不清楚。
salesforce这题， 比如在leetcode的   ...

只看最大权重的边的话，把大于threshold的edge去掉然后Prim/Kruskal，看最大的一颗MST？

SoWhat0309 发表于 2021-10-2 16:34
https://leetcode.com/problems/fi ... threshold-distance/

LC 1334, 当时用的Floyd-Warshall（2

感谢分享，我看了一下那题，我刷过那道。 我题目描述可能不清楚。
salesforce这题， 比如在leetcode的  https://leetcode.com/problems/fi ... threshold-distance/
n = 4,  edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
leetcode返回了 3. 因为city 3有两个相邻城市。

salesforce这题需要返回(0,1,2,3,4)。 因为因为0 到 1 的weight 是 3 《= 4， 1到3的weight 是 4 <= 4， 所以 0和 3也是相关的。
但是如果把 1-2的weight改成 5， 答案应该是 (0,1) (3,1) 或者 (3,2)

我是用 Hierholzer's Algorithm做的， 感觉不太对。

https://leetcode.com/problems/fi ... threshold-distance/

LC 1334, 当时用的Floyd-Warshall（2 <= n <= 100，O(n^3) 还算能过）

SoWhat0309 发表于 2021-10-2 17:03
只看最大权重的边的话，把大于threshold的edge去掉然后Prim/Kruskal，看最大的一颗MST？

我当时应该做错了。 轻敌salesforce了，前几轮题难度适中，最后一轮。感觉这题挺好的，就是我不会。。
我明天给你加大米。

xiaozhuxiaozhu 发表于 2021-10-2 19:08
我当时应该做错了。 轻敌salesforce了，前几轮题难度适中，最后一轮。感觉这题挺好的，就是我不会。。
...

现在再看了下貌似把超重的边去掉然后Union Find就可以了（剩下的边权重没区别），用不到MST。我也想复杂了…

SoWhat0309 发表于 2021-10-2 17:16
现在再看了下貌似把超重的边去掉然后Union Find就可以了（剩下的边权重没区别），用不到MST。我也想复杂 ...

这个例子 怎么去掉边呢。

比如三个城市 ,a, b, c， threshold是 1.5
a 到 b的weight 是 1.2
a到 c 的weight 是 1
b到 c的weight 是 2

去掉 b 和 c的边？

请问楼主这是什么岗位？NG吗？