Airbnb 跪经 + 2016-2017年airbnb面经汇总

想问下楼主 列表里带Design的题 是指这是design题？还是属于coding题但要用Design解？

okayfaner 发表于 2017-9-24 04:59
想问下楼主 列表里带Design的题 是指这是design题？还是属于coding题但要用Design解？

是coding题

kaikaiC 发表于 2017-9-24 04:22
感觉差很多。。。写了很久没解出来。。。
能麻烦描述一下怎么做的吗。。

Word Search II是“Find all words in the dictionary that can be found in the matrix”。
BoggleGame的第一步和Word Search II差不多，但是要找的是所有valid words在matrix中的位置信息(用Trie+DFS)。第二步是对这些位置信息进行DFS，看最多能取多少个words而使他们不发生重叠，也就是最终答案。
所以我的解法简单来说就是构造Trie + 2次DFS

LZJ981 发表于 2017-9-24 07:21
Word Search II是“Find all words in the dictionary that can be found in the matrix”。
BoggleGame ...

soga，明白了，谢谢！

kaikaiC 发表于 2017-9-24 08:00
soga，明白了，谢谢！

不客气，祝好运

请问楼主申请的什么职位？
还有楼主能分享一下waterland这题的思路吗？
谢啦

jiahan 发表于 2017-9-25 12:56
请问楼主申请的什么职位？
还有楼主能分享一下waterland这题的思路吗？
谢啦

当时申是full stack engineer，不过airbnb是入职bootcamp完后才选组。
waterland看之前的面经帖，感觉是开放式的题，不同面经里提到的具体细节不是完全相同。我的假设是：
1.如果左边land比滴水点低，则水向左留，直至最左边
2.如果左边land都比滴水点高(或齐平)，则尝试往右边流
3.如果右边land都比滴水点高(或齐平)，则水直接积攒在滴水点
这只是我的假设，具体的话还得看面试时面试官的需求。
求得新的滴水点array后，要打印waterland。打印时传入originalArray和newArray, 然后按层打印。

楼主，有两个问题想请教下，对于MenuCombinationSum，这个应该是DFS吧，DP能解决吗？对于MinimumNumberOfGraphNode，这个题目Union Find可以解决吗？我记得这个题目是有向图，应该是有向图缩强连通分量，然后再加上拓扑排序吧？可以简单讨论下吗？谢谢

knight0clk 发表于 2017-9-26 04:13
楼主，有两个问题想请教下，对于MenuCombinationSum，这个应该是DFS吧，DP能解决吗？对于MinimumNumberOfGr ...

MenuCombinationSum用DP也可以呀，类似DP背包问题.
MinimumNumberOfGraphNode如果是有向图的话union find不好使～  我一直以为这题是无向图，多谢指正！

LZJ981 发表于 2017-9-26 04:24
MenuCombinationSum用DP也可以呀，类似DP背包问题.
MinimumNumberOfGraphNode如果是有向图的话union fin ...

这个MenuCombinationSum不是让输出specific的组合吗？输出具体方案，只能递归吧？