Google onsite

第四问还能有什么最优解么？

“第4轮烙印，居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更好的算法。” 如何证明呢？难道说之前第二轮log(n)的算法不能用吗？

hefang 发表于 2015-4-20 11:22
“第4轮烙印，居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更 ...

不能用因为他没有给定你相邻元素不相同的条件。证明方法是假设存在一个比线性快的刷法你要给出反例证明这个算法无法实现。我是给了一个例子Array [2,2,2] 如果你不线性的扫描一遍你不会知道这个数组不存在peak element

zyn334455 发表于 2015-4-20 10:47
第四问还能有什么最优解么？

好像可以一个字母一个字母的在矩阵中间找到位置（i,j）然后你得到一个（i，j）的序列。然后根据这个序列产生移动步骤。应该是o(m*n)复杂度吧。

jianghaon0 发表于 2015-4-21 01:12
好像可以一个字母一个字母的在矩阵中间找到位置（i,j）然后你得到一个（i，j）的序列。然后根据这个序列 ...

恩。。。不太明白是什么意思，是用一个hashtable记录每个字母和它出现的位置么？

zyn334455 发表于 2015-4-21 02:03
恩。。。不太明白是什么意思，是用一个hashtable记录每个字母和它出现的位置么？

比如说给你个矩阵
A B C
D E F
G H I
给你的string是“ECG”
然后你就找ECG在矩阵内的位置(1,1), (0,2), (2,0)根据这3个位置你就可以知道最后移动的步骤了
开始(0,0)->(1,1) "DR" (1,1)->(0,2) "LU" 等等
时间复杂度O(m*n)

jianghaon0 发表于 2015-4-21 02:37
比如说给你个矩阵
A B C
D E F

哦哦这样。。但假如说如果有重复字母呢？比如说矩阵里有M*N个元素，然后给定搜索单词长度为K，然后最坏情况是这M*N个元素里就只有给定搜索单词里的字母且单词的相邻字母在矩阵中互不相邻，平均每个字母出现了M*N/K次，那这样时间复杂度不就是O((M*N/K)^K)的复杂度了么，是指数级的？

补充内容 (2015-4-21 04:29):
哦这个最坏情况我好像举的有点问题。。。我再想想

zyn334455 发表于 2015-4-21 04:27
哦哦这样。。但假如说如果有重复字母呢？比如说矩阵里有M*N个元素，然后给定搜索单词长度为K，然后最坏情 ...

这个你要跟你的面试官讨论我问过他，输入假设是没有重复。开始做的时候你就要把各种情况跟他说好这样就没问题了。

jianghaon0 发表于 2015-4-21 05:20
这个你要跟你的面试官讨论我问过他，输入假设是没有重复。开始做的时候你就要把各种情况跟他说好这样就没 ...

OK，明白了，多谢楼主！

最后一轮矩阵的suppose应该用trie做，感觉就是leet code的新题word search2. 普通的backtrack对于large test不行