脸书电面

kevintong 发表于 2017-9-2 14:44
我是自己写的bfs，然后面试官就问我代码什么时候会crash，我说输入不valid时候会crash，然后他很失望，问 ...

我觉得面试官问什么时候会crash是想让楼主做下back of envelope calculation. 例如，假设用户可以有100个好友，用户a到用户b距离是d层的话, 那么running time 就是100 ^ d。 一般cpu的运算速度大概是10^8 operations per few secs => 1年有30M秒 =》 3 * 10^15 => d 大约 14 层 左右。用过用单向dfs的话，而且用户a 到用户b有14层，大概需要1年的时间处理。如果用双向做的话就只需要半年，所以说bi-dfs优化挺多的。

用dfs降低空间复杂度？搜到六度多就停止往下搜了 只是这样时间就很久了

电面竟然会考bidirectional bfs 不容易啊

jigsaw_Becky 发表于 2017-9-6 09:58
你好，请问是只需要是几度好友就行了，还是需要把path打印出来？谢谢！

只有度数啊