Google onsite

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

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

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

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

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

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

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

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

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

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

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

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

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不行