脸书店面二面

论坛匿名用户 发表于 2019-6-20 18:46
不是原题，要求要输出具体的路径（坐标），用DP不行吧。

用DP 再单独开个数组 存每一格的上一步

glorian0127 发表于 2019-6-20 20:46
用DP 再单独开个数组 存每一格的上一步

这样做也行。不过我觉得DP的优势在于求最短路径而不是具体的路径。

fb最近还有hc吗

        很有用的信息！

没headcount的可能性比较大，不知道他家什么时候开始有新的名额，楼主不要放弃。

楼主第一题做到O(1) space是把原数组变成prefix sum了吗

论坛匿名用户 发表于 2019-6-20 18:46
不是原题，要求要输出具体的路径（坐标），用DP不行吧。

用DP也可以，需要再开一个矩阵记录每一个点是通过哪个方向来的（向下还是向右），然后从右下角找回左上角就能找到路径。摸摸楼主，祝别的面试顺利！

woshilxd912 发表于 2019-6-21 07:09
楼主第一题做到O(1) space是把原数组变成prefix sum了吗

我觉得解法应该是这样，然后再双指针。我现场写的估计有问题，看来是挂在这道题了。面试官也没给啥提示，就一句你觉得对就行，就开始下一题了。

论坛匿名用户 发表于 2019-6-20 18:49
也有可能。如果面试官不喜欢你，挂的理由太好找了。

你做题之前和他说思路了吗？还是就直接写了？

cecilianxf 发表于 2019-6-21 20:30
你做题之前和他说思路了吗？还是就直接写了？

说了思路再写的。我觉得我第一题写的有些问题，所以被挂也不算太冤。