Google Onsite 面筋

bdhmwz 发表于 2018-3-28 18:35
只找到了Minimize Max Distance to Gas Station 这一道和第二轮的相似，没有找到二维的，不过思想应该是 ...

是的，如果用BFS，可以构造parent，来backtrack回那条path。

楼主是其他四轮答案都写出来了吗？
关键你第4轮也做出来了啊，为什么还是会挂。。。

补充内容 (2018-3-29 00:17):
顺便问下楼主多久收到回复的啊

houpy 发表于 2018-3-29 00:16
楼主是其他四轮答案都写出来了吗？
关键你第4轮也做出来了啊，为什么还是会挂。。。

我每一轮都答出来了，才挂这是迷之烙印，其他公司碰到的烙印都还ok，在狗碰到了4个烙印还是躲不过

周4面，第二周周二出来的

trthank829 发表于 2018-3-29 00:22
我每一轮都答出来了，才挂这是迷之烙印，其他公司碰到的烙印都还ok，在狗碰到了4个烙印还是躲不过

周4 ...

太可惜了楼主。。。我周一面试那天也是有2个

trthank829 发表于 2018-3-29 00:02
是的，如果用BFS，可以构造parent，来backtrack回那条path。

感觉不能用BFS，lz可能死在了这题上。。。
https://stackoverflow.com/questi ... ing-cycle-in-graphs

wtcupup 发表于 2018-3-29 00:40
感觉不能用BFS，lz可能死在了这题上。。。
https://stackoverflow.com/questions/2869647/why-dfs-and-n ...

找cycle干嘛不用union find？

wtcupup 发表于 2018-3-29 00:40
感觉不能用BFS，lz可能死在了这题上。。。
https://stackoverflow.com/questions/2869647/why-dfs-and-n ...

估计这个题目确实得用bfs，bfs的时候把起点不标成visited，然后回到起点的时候退出bfs，然后按照楼主说的根据parents构建出来那个cycle

补充内容 (2018-3-29 03:02):
StackOverflow第一个答案说bfs搞不定不完全对，其他答案说的比较对，bfs只是复杂一点，不是搞不定。另外楼主补充的找最小cycle的话，肯定得bfs

randrand1 发表于 2018-3-29 03:00
估计这个题目确实得用bfs，bfs的时候把起点不标成visited，然后回到起点的时候退出bfs，然后按照楼主说的 ...

如果是这样和dfs没什么差别，dfs照样可以这么做，用bfs有其他特殊的理由么？比如说就要找最短的cycle

sonofspring 发表于 2018-3-28 20:40
请问面试官的组成可以问  recuiter 么？ recuiter 只给我发了具体的面试时间，地点。。谢谢！

可以问么？ 不知道怎么问，会不会觉得我们是种族主义者？

randrand1 发表于 2018-3-29 03:00
估计这个题目确实得用bfs，bfs的时候把起点不标成visited，然后回到起点的时候退出bfs，然后按照楼主说的 ...

dfs也可以啊, visited里面除了放node, 还同时存储到达该node的step, 一旦找到一个cycle,就知道该cycle的长度了.然后找到最短的cycle.
不知道这样做对吗?