w***y
发帖数: 6251 | 1 上周去面试，被问到boggle － 就是给一个dictionary, 从4X4的boggle里面找所有可
能的words. 幸好只是让我说算法，没有要求code//汗
我大概说了说思路，面试官表示认可。 然后就继续问：
假定现在这个boggle是N*N, 非常大的； 要求longest valid word （其实原题目说是
一个function F跟word length相关，让max F, 也就是找最长的word了）。
我也没太想明白怎么做， 我就大概说，可能需要用dynamic programming, 然后跟面试
的人讨论了一下substructure可能是什么样。后来因为下一个面试的人来了，我们也就
没有继续纠缠这个。
不过我想知道这个题到底该怎么做。 |
p*****2
发帖数: 21240 | 2
继续找就好了，一直找到不能再找
【在 w***y 的大作中提到】
: 上周去面试，被问到boggle － 就是给一个dictionary, 从4X4的boggle里面找所有可
: 能的words. 幸好只是让我说算法，没有要求code//汗
: 我大概说了说思路，面试官表示认可。 然后就继续问：
: 假定现在这个boggle是N*N, 非常大的； 要求longest valid word （其实原题目说是
: 一个function F跟word length相关，让max F, 也就是找最长的word了）。
: 我也没太想明白怎么做， 我就大概说，可能需要用dynamic programming, 然后跟面试
: 的人讨论了一下substructure可能是什么样。后来因为下一个面试的人来了，我们也就
: 没有继续纠缠这个。
: 不过我想知道这个题到底该怎么做。
|
D********g
发帖数: 650 | 3 可以考虑用当前找到的最长word的length 做pruning.
if 当前string是个合法的word并且长度>= longestWordSofar.length()，则update
longestword
if 当前string是个合法prefix，继续找下去
需要字典支持isPrefix操作
【在 w***y 的大作中提到】
: 上周去面试，被问到boggle － 就是给一个dictionary, 从4X4的boggle里面找所有可
: 能的words. 幸好只是让我说算法，没有要求code//汗
: 我大概说了说思路，面试官表示认可。 然后就继续问：
: 假定现在这个boggle是N*N, 非常大的； 要求longest valid word （其实原题目说是
: 一个function F跟word length相关，让max F, 也就是找最长的word了）。
: 我也没太想明白怎么做， 我就大概说，可能需要用dynamic programming, 然后跟面试
: 的人讨论了一下substructure可能是什么样。后来因为下一个面试的人来了，我们也就
: 没有继续纠缠这个。
: 不过我想知道这个题到底该怎么做。
|
g**********y
发帖数: 14569 | 4 把字典建成一棵加强版的Trie, 就是在Trie的基础上，计算每个节点可最多延长的路径
长度。然后用这个Trie来做辅助工具，剪枝遍历。
【在 w***y 的大作中提到】
: 上周去面试，被问到boggle － 就是给一个dictionary, 从4X4的boggle里面找所有可
: 能的words. 幸好只是让我说算法，没有要求code//汗
: 我大概说了说思路，面试官表示认可。 然后就继续问：
: 假定现在这个boggle是N*N, 非常大的； 要求longest valid word （其实原题目说是
: 一个function F跟word length相关，让max F, 也就是找最长的word了）。
: 我也没太想明白怎么做， 我就大概说，可能需要用dynamic programming, 然后跟面试
: 的人讨论了一下substructure可能是什么样。后来因为下一个面试的人来了，我们也就
: 没有继续纠缠这个。
: 不过我想知道这个题到底该怎么做。
|
p*****2
发帖数: 21240 | 5
我面Google搞了个trie，结果没写完程序。最后人家说就是想要暴力的。
【在 g**********y 的大作中提到】
: 把字典建成一棵加强版的Trie, 就是在Trie的基础上，计算每个节点可最多延长的路径
: 长度。然后用这个Trie来做辅助工具，剪枝遍历。
|
w***y
发帖数: 6251 | 6 i c
那就是：
第一个位子（0,0)开头的words,肯定要搜完所有可能
后面的就是利用了当前的maxL word 和当前prefix可能延长的maxL去剪枝
所以比找所有valid words需要的计算还是少一些的
【在 g**********y 的大作中提到】
: 把字典建成一棵加强版的Trie, 就是在Trie的基础上，计算每个节点可最多延长的路径
: 长度。然后用这个Trie来做辅助工具，剪枝遍历。
|
n********k
发帖数: 40 | 7 一听字典，统计单词就是trie没跑儿。
我幼稚地认为，如果一个面试官跟你说了不要代码，就要往hash，balanced binary
search tree和trie这三个上面想了，对于trie，我惯例的回答是：“我知道prefix
tree可以On时间On空间实现，这是基因工程中最基本的算法，但是写起来很复杂，你不
会要我写吧？”然后开始狂喷
要是要代码，一切比longest increasing subsequence更复杂的算法都不要费时间去想
，一定有更简单的。 |
d******u
发帖数: 397 | |
