google phone interviw

感觉像是一个三哥T T不过人感觉还是不错


给的例子：

Graph g = new Graph();

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

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

所以cycle detection最好是用recursive 的 DFS. (MD, 这点儿把老子整惨了)

say543 发表于 2015-6-9 05:34
self point 的cycle 用BFS 也可以detect阿? 为什么一定要recurisve DFS?

这要分两种情况讨论：
如果图是无向图，则可以用disjoint-set来detect cycle
如果是有向图，直接topological sort就ok了

zj45499 发表于 2015-3-27 12:04
g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);
这两种有什么区别么? 不是无向图?

就是abb跟ff组成了一个cycle嘛
这个图是有向的

tyr034 发表于 2015-3-24 09:37
请问 楼主：
g.addEdge(“abb”, “cde”);
这是说在 node abb和  node cde之间加edge?

是的 一个是source node 第二个是child node

最近这么多图的题。。。

很少练习这些

bless 卤煮

请问 楼主：
g.addEdge(“abb”, “cde”);
这是说在 node abb和  node cde之间加edge?

houqingniao 发表于 2015-3-24 08:35
最近这么多图的题。。。

很少练习这些

多练练吧....看还有个实现hashtable的

楼主能把你的解法分享一下么，谢谢

g.addEdge(“abb”, “ff”);
g.addEdge(“ff”, “abb”);
这两种有什么区别么? 不是无向图?

timtam85 发表于 2015-3-27 11:57
楼主能把你的解法分享一下么，谢谢

解法真的没啥好分享的啊 就是最基本的graph啊....

self point 的cycle 用BFS 也可以detect阿? 为什么一定要recurisve DFS?