Redian新闻
>
请问大家推荐的Harry Wang律师的联系信息?一个包子答谢。
avatar
请问大家推荐的Harry Wang律师的联系信息?一个包子答谢。# Immigration - 落地生根
B*1
1
之前似乎好几个人onsite google都遇到过的,但是今天在careercup上面居然看到说
interview要求o(n+m),请问怎么做到啊?
Longest Common Prefix from N strings of max length "m".
I gave a naive approach of O(n.m) and O(m.logn) with some adjustments but
Interviewer wanted something O(n+m) or better than O(n.m).
Please suggest solutions.
eg:
Flower
Flow
Flight
Output:
Fl
avatar
Y*1
2
thanks!
avatar
y*i
3
谢谢!
avatar
r*g
4
O(mlogn)是什么意思?怎么做的
如果是我,我肯定告诉它用trie,这样遍历一次就够了。不是么?
avatar
t*7
5
yes
avatar
b*r
6
i**[email protected]
713-471-8963

【在 y******i 的大作中提到】
: 谢谢!
avatar
k*n
7
I don't think there exists a solution lower than O(m*n)
you must at least access all the first m letters for each of the n strings
that's m*n reads and you cannot reduce a single operation from that.

【在 r*******g 的大作中提到】
: O(mlogn)是什么意思?怎么做的
: 如果是我,我肯定告诉它用trie,这样遍历一次就够了。不是么?

avatar
y*i
8
谢谢!请查收包子,没收到的话告诉我一声。

【在 b*********r 的大作中提到】
: i**[email protected]
: 713-471-8963

avatar
R*i
9
说的没错。至少要读这些字符吧。
或者说前处理不算在时间复杂度里面。

【在 k****n 的大作中提到】
: I don't think there exists a solution lower than O(m*n)
: you must at least access all the first m letters for each of the n strings
: that's m*n reads and you cannot reduce a single operation from that.

avatar
b*r
10
收到了,谢谢:)

【在 y******i 的大作中提到】
: 谢谢!请查收包子,没收到的话告诉我一声。
avatar
B*1
11
Thanks all. Just confirm I did not miss anything.
avatar
r*g
12
理解你的意思了,你是说每去除一个letter就是一次操作,所以肯定不会低于O(mn),
因为总是需要遍历完所以n个数,而且每次都是m。

【在 k****n 的大作中提到】
: I don't think there exists a solution lower than O(m*n)
: you must at least access all the first m letters for each of the n strings
: that's m*n reads and you cannot reduce a single operation from that.

avatar
B*1
13
但是其实肯定不到o(nm)的,因为可以先找到最短的2个substring的common prefix,然
后用这个prefix和剩下的匹配。
avatar
f*t
14
找两个最短的substring就是O(nm)时间复杂度了!
而且就算告诉你最短的两个substring,极限情况下所有的string都是相同的,这样时
间复杂度必然是O(nm),省不了的。

【在 B*******1 的大作中提到】
: 但是其实肯定不到o(nm)的,因为可以先找到最短的2个substring的common prefix,然
: 后用这个prefix和剩下的匹配。

avatar
B*1
15
o, right.
thanks

【在 f*******t 的大作中提到】
: 找两个最短的substring就是O(nm)时间复杂度了!
: 而且就算告诉你最短的两个substring,极限情况下所有的string都是相同的,这样时
: 间复杂度必然是O(nm),省不了的。

相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。