楼主: jianghaon0
跳转到指定楼层
上一主题 下一主题
收起左侧

Google onsite

🔗
zyn334455 2015-4-20 10:47:10 | 只看该作者
全局:
第四问还能有什么最优解么?
回复

使用道具 举报

🔗
hefang 2015-4-20 11:22:03 | 只看该作者
全局:
“第4轮烙印,居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更好的算法。” 如何证明呢?难道说之前第二轮log(n)的算法不能用吗?
回复

使用道具 举报

🔗
 楼主| jianghaon0 2015-4-20 21:45:24 | 只看该作者
全局:
hefang 发表于 2015-4-20 11:22
“第4轮烙印,居然问了第2轮一样的题目。。只不过没有相邻元素不相同的条件。让你证明为什么找不到比O(n)更 ...

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

评分

参与人数 1大米 +3 收起 理由
hefang + 3 对哦,可以举反例

查看全部评分

回复

使用道具 举报

🔗
 楼主| jianghaon0 2015-4-21 01:12:08 | 只看该作者
全局:
zyn334455 发表于 2015-4-20 10:47
第四问还能有什么最优解么?

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

使用道具 举报

🔗
zyn334455 2015-4-21 02:03:05 | 只看该作者
全局:
jianghaon0 发表于 2015-4-21 01:12
好像可以一个字母一个字母的在矩阵中间找到位置(i,j)然后你得到一个(i,j)的序列。然后根据这个序列 ...

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

使用道具 举报

🔗
 楼主| jianghaon0 2015-4-21 02:37:29 | 只看该作者
全局:
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)
回复

使用道具 举报

🔗
zyn334455 2015-4-21 04:27:58 | 只看该作者
全局:
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):
哦这个最坏情况我好像举的有点问题。。。我再想想
回复

使用道具 举报

🔗
 楼主| jianghaon0 2015-4-21 05:20:35 | 只看该作者
全局:
zyn334455 发表于 2015-4-21 04:27
哦哦这样。。但假如说如果有重复字母呢?比如说矩阵里有M*N个元素,然后给定搜索单词长度为K,然后最坏情 ...

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

使用道具 举报

🔗
zyn334455 2015-4-21 05:46:29 | 只看该作者
全局:
jianghaon0 发表于 2015-4-21 05:20
这个你要跟你的面试官讨论我问过他,输入假设是没有重复。开始做的时候你就要把各种情况跟他说好这样就没 ...

OK,明白了,多谢楼主!
回复

使用道具 举报

🔗
magicalcan 2015-5-28 15:52:40 | 只看该作者
全局:
最后一轮矩阵的suppose应该用trie做,感觉就是leet code的新题word search2. 普通的backtrack对于large test不行
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表