AIRBNB skype 面经

题目： boogle game直接找到所以单词可能出现的位置，然后dfs
感觉这样的代码比较短。。45min勉强敲

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

gif" smilieid="112" border="0" alt="" />

SiyaoZhu 发表于 2016-12-8 10:40
我就是用了word break II 的代码 先找到了单词出现的所有位置 然后再来一个dfs来找到不重叠的最大情况

...

楼主你的"再来1个DFS”是地里那个dfs2()的解法吗 我在想能不能把每个word 都算出一个conflict count，一开始所有word都在result里 然后从count高的开始remove，直到所有word都没有conflict
是个greedy但感觉似乎是对的

SiyaoZhu 发表于 2016-12-10 00:01
最终结果可以有重复单词的 只要不overlap

答主能不能在讲清楚一点题目要求？是说在board上面，找到最多的不overlap的word吗？相同word只要可以放得下都加一？是按word search先找出所有的word位置然后再根据位置看看有没有overlap的？？

SiyaoZhu 发表于 2016-12-9 01:51
不是啊。。我是最最暴力的。。找出所有单词的位置，用一个map表示 然后dfs这个map找出不重复的最大

所以你的map就是word->list of letter indice，然后dfs用一个set of indice来判断重复？这个确实work

那你觉得我的方法会不会有什么问题

要去onsite了？ 加油加油～

请问是boggle game I 还是 II呀？ 具体要求是啥

小A要当码农 发表于 2016-11-25 13:13
请问是boggle game I 还是 II呀？ 具体要求是啥

boggle game这都出来两个版本了啊？小A这么严谨讲讲要求都是什么呗？

gy21 发表于 2016-11-26 05:40
boggle game这都出来两个版本了啊？小A这么严谨讲讲要求都是什么呗？

好像一个要求连续， 一个不要求呗。 不要求那个更难。。

楼主能详细说下吗？ 谢了

额 没有说过什么连续的事情啊。。
我记得 就是找board中找不能重复位置的最大单词数量。。找单词的时候还定义了一个曼哈顿距离。。就是用来表示不能斜着走的
题目一共就是这3句话。。
另外board里面的字母都是大写

小A要当码农 发表于 2016-11-26 06:14
好像一个要求连续， 一个不要求呗。 不要求那个更难。。

请问啥叫要求连续呀？什么是连续的呀？

SiyaoZhu 发表于 2016-11-26 08:38
请问啥叫要求连续呀？什么是连续的呀？

就是找的单词需要首位相接么？

请问能不能给一下代码，我只会写word search ii， 字母可以重复用，但是如果不能重复用好像很难，求指点