GG六月onsite

cxl89 发表于 2017-7-5 06:08
请问第三轮里面要求打印path是用bfs做的吗？每次bfs的时候build一个图然后倒着print？多谢楼主

我的做法是，bfs时将path也push到queue里。不过这样空间复杂度可能有点大

weighted graph，如果不用priority queue做大概time complexity要到 v三次方了，但是normal queue应该是会得到正确的结果。

yanshuining 发表于 2017-7-6 02:06
我的做法是，bfs时将path也push到queue里。不过这样空间复杂度可能有点大

lz，为什么要path也入queue，有什么理由嘛
维护一个precede array也是可行的吧。

yanshuining 发表于 2017-7-6 02:06
我的做法是，bfs时将path也push到queue里。不过这样空间复杂度可能有点大

明白了，多谢楼主。

cuijinxxx 发表于 2017-7-6 02:59
lz，为什么要path也入queue，有什么理由嘛
维护一个precede array也是可行的吧。

不是很明白你的意思，能再详细说一下嘛？

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

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

楼主，请问第五轮中如何评价两个句子是语义相似的？这是我能想到的情况：两个句子的长度一样，并且对应的词语要么相同，要么就是出现在同义词的map中。

daguanyuan 发表于 2017-7-6 05:00
楼主，请问第五轮中如何评价两个句子是语义相似的？这是我能想到的情况：两个句子的长度一样，并且对应的词 ...

是的。两个句子同义就是判断，句子中的word是否相同或者同义

请教第四轮的题目，不太清楚同事关系。
例如：p2的manager是p1。p2和p3是同事，那p3的manager也是p1吗?
p1的同事是p4, 那p2的manager是p1和p4?
谢谢！

感谢楼主分享


补充下第五题followup 用个union find