Palantir 电面面经

wulalawu 发表于 2019-10-7 11:53
楼主第三题是说的dfs还是bfs的思路呀？

求最短bfs好做写

一剑终情 发表于 2019-10-8 02:33
求最短bfs好做写

但是要经过所有waypoint的话是没有办法用bfs做的，因为可以绕回来

wulalawu 发表于 2019-10-7 13:25
但是要经过所有waypoint的话是没有办法用bfs做的，因为可以绕回来

我想了一下，如果允许绕回来的话，dfs和bfs都有点麻烦。
dfs要怎么保证绕回来走的是最短的？

一剑终情 发表于 2019-10-8 04:25
我想了一下，如果允许绕回来的话，dfs和bfs都有点麻烦。
dfs要怎么保证绕回来走的是最短的？

这个是NP Hard问题，面试的话没有办法得到最优解。
https://en.wikipedia.org/wiki/Travelling_salesman_problem
面试的expectation应该就是有想法或者暴力就可以了吧。

第二题的话，是不是直接就是第一问返回的array的长度如果等于0的个数就可以返回true了呀
第三题和airbnb之前一道题基本一样，不能到达应该是被-1包围而不是不能回头路，就是bfs，不过visited set不是单纯(i,j)作为key, 而是(i,j) + 当时在(i,j)收集到的所有treasure的x,y作为key
这样可以走回头路的条件是走到回头路的时候手上有新的treasure, 结束条件就是新enqueue的节点都在visited里了，bfs出来就是最短
楼主看下这个思路有问题么 :)

下巴君 发表于 2019-10-11 12:59
第二题的话，是不是直接就是第一问返回的array的长度如果等于0的个数就可以返回true了呀
第三题和airbnb之 ...

你好，我现在好像没有权限回打招呼，就在这里跟你说一下~我忙完这周应该会写个面筋，先大概跟你讲一下吧，debug就是公司所有权那道题，design是大学选课系统，coding有点像flood map的简化版

请问楼主可以更新一下后来Onsite的故事嘛？都遇到什么题了呀，感觉如何？

mummylqx 发表于 2019/12/02 08:53:21
请问楼主可以更新一下后来Onsite的故事嘛？都遇到什么题了呀，感觉如何？

Onsite面经我匿名发过了，搜Palantir昂赛应该就能找到

lizzielee 发表于 2019-12-2 12:33
Onsite面经我匿名发过了，搜Palantir昂赛应该就能找到

哦哦好的，谢啦