狗家intern conversion interview onsite 挂经

aliwithtaozi 发表于 2019-9-11 15:21
我coversion也没过 没事 楼主加油再面别的
组里给我写的feedback都特别好 大组里还有个hc的人 当时做projec ...

一开始很伤心，后来就释怀了，你也加油！

zezed 发表于 2019-9-11 15:38
这样讲吧，如果你对每一个元素都做binarysearch，就能找到每一个元素可以跳到的范围了吧。所以worst是O(n ...

我也明白你的意思...
每个元素bfs至多做一次这个没问题。但是你一个点可以找到多次，虽然找到的点不一定是需要继续bfs的，但是每次找点的时间复杂度还是是O(k)。

Candela 发表于 2019-9-11 16:18
我觉得第二题的follow up是可以O(n)做的吧？再开一个数组维护dp的prefix_sum, 更新dp的时候只需要check dp  ...

手动点赞

5290 发表于 2019/09/12 01:59:10


我也明白你的意思...
每个元素bfs至多做一次这个没问题。但是你一个点可以找到多次，虽然找到的点不一定是需要继续bfs的，但是每次找点的时间复杂度还是是O(k)。

代码优化下是不用重复填格子的，不过已经有正确答案了。

补充内容 (2019-9-11 21:12):
更新左右两端就好了，实际只要不断拓展右端。

请问楼主 “每次可以往右移一步，或者跳k步(跳的距离是固定的)” 的意思是可以在1～k中选择一个数，作为每次向右移动的步数吗？这样的话可以直接从第一个位置跳到最后嘛？

offeriscoming 发表于 2019-9-12 04:25
请问楼主 “每次可以往右移一步，或者跳k步(跳的距离是固定的)” 的意思是可以在1～k中选择一个数，作为每 ...

不是，是两种：
1、要是下一个index不是石头，那么就可以直接走到下一个index；
2、要是下一个index是石头，那只能跳k步

姐姐加油！

patpat楼主，请问楼主实习哪天结束的。。

第二题dfs+memo是O(n) 每个点的状态记下来至多只会visit一次

lapland 发表于 2019-9-14 04:48
patpat楼主，请问楼主实习哪天结束的。。

8.9  zszszszszs