y*****i
发帖数: 141 | 1 自己顶一下。
KMP不适合多次查询的情况，Aho-Corasick适合查前缀而不是任意位置的子串，所以只
能是suffix tree吧？ |
|
r*********n
发帖数: 4553 | 2 那可以把所有词的suffix都放到trie里面去，这样查找速度最快，但是预处理复杂度很
高，不过如果查找次数很多，预处理的overhead平均下来也就不算什么了。 |
|
h*********2
发帖数: 192 | 3 问大家一个题：
Given a string, find the longest overlapping suffix. E.g., "banana", return
"ana".
题目很短，感觉overlap就是指末字符和首字符重合的字串。
大家遇到过这题吗？ |
|
|
r****t
发帖数: 10904 | 5 喔你是找suffix, 那就reverse之后找prefix罗, 一行有点难看，但是还是可以的：
os.path.commonprefix([w[::-1] for w in set_of_words])[::-1]
能work. |
|
w********9
发帖数: 8613 | 6 这是Shorter Oxford American English Dictionary第五版列出的与德语或者日耳曼语
相关的英语词根或词汇。
-at, suffix2. + -dom, suffix. + -ed, suffix1. + -ed, suffix2. + -en, suffix1
+ -en, suffix2 + -en, suffix5 + -en, suffix6 + -er, suffix1. + -er, suffix3
. + -er, suffix5. + -est, suffix1. + -est, suffix2. + -et, suffix2. + -eth,
suffix1. + -hood, suffix. + -ing, suffix1. + -ing, suffix3. + -ish, suffix1.
+ -kin, suffix. + -le, suffix1 + -le, suffix3 + -less, suffix. + -ling,
suffix1. + -ling, suffix2 + -ly, suffix1. + -ly, s... 阅读全帖 |
|
T**r
发帖数: 7016 | 7 老大，不好意思，这个贴比较长。
我把NAT搞定了，现在MSVPC guest也能上internet，即使host在公司的VPN上。但是
host
不能看到guest，guest却可以看到host（公司IP）。我需要host能看到guest，因为
guest上
有一些web application需要demo。
whatismyip.com显示两个是同一个IP，而且应该是我VPN的IP，我ISP的IP是75开头，公
司是
144开头。
下面是host 和guest的ipconfig 和route print，其中host里有一些vitualbox和
vmware的遗留下来的一些设置，以前装过，没有搞出来，现在用的是MS VPC。
******************
host ipconfig: *
******************
C:\Documents and Settings\ga2334>ipconfig
Windows IP Configuration
Ethernet adapter VMware Network Adapter VMnet8:
Co... 阅读全帖 |
|
i***h
发帖数: 12655 | 8 用C++ STL, 还好了
下面的代码少了最后一步, 也没有sanity check
但也不难
当然效率不是最好的
#include
#include
#include
#include
using namespace std;
bool
compstr(char* a, char* b)
{
return strcmp(a,b)<0;
}
void
suffixArray(char *a, char *b)
{
char *m = (a>b)? a-1 : b-1;
char* suffix[strlen(a)+strlen(b)];
for(int i = 0; i
suffix[i] = a+i;
}
for(int i=0; i
suffix[strlen(a)+i] = b+i;
}
sort(suffix, suffix+strlen(a)+strlen(b), comp... 阅读全帖 |
|
a********n
发帖数: 1287 | 9 用suffix array
char* LongestCommonSubStr( char* a, char* b )
{
if( !a || !b )
{
return NULL;
}
int sizea = strlen( a );
int sizeb = strlen( b );
char** suffix = new char*[sizea + sizeb];
int suffixIdx = 0;
for( int i = 0; i < sizea; i++ )
{
suffix[suffixIdx++] = a + i;
}
for( int i = 0; i < sizeb; i++ )
{
suffix[suffixIdx++] = b + i;
}
std::sort( suffix, suffix + sizea + sizeb, Comp() );
int maxLen = 0;
char* ... 阅读全帖 |
|
a******u
发帖数: 69 | 10 master new grad：
base 都是 110K
startup
4年option 两万，占整个公司万分之五
startup的engineering team暂时不到30人。
Google 4年给GSU 250
感觉在Startup会学到多一点东西。
G的
max suffix match
定义suffix和suffix match
Example：banana
suffix: a, na, ana, ...,
suffix match: 一个非suffix但等于suffix的substring。
问：找最长的suffix match。
最优解是O(n) |
|
p*****2
发帖数: 21240 | 11 找到这题的出处了。还没看太懂。
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely defines a string, which after being "
inserted" in front of the given su... 阅读全帖 |
|
w****y
发帖数: 56 | 12 is it the problem here?
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely ... 阅读全帖 |
|
w****y
发帖数: 56 | 13 is it the problem here?
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
A typical problem seen quite often is: given a string find its shortest
substring, such that the concatenation of one or more copies of it results
in the original string. Again the problem can be reduced to the properties
of the failure function. Let's consider the string
A B A B A B
and all its proper suffix/prefixes in descending order:
1 A B A B
2 A B
3 /the empty string/
Every such suffix/prefix uniquely ... 阅读全帖 |
|
s******c
发帖数: 99 | 14 https://www.interviewstreet.com/challenges/dashboard/#problem/4edb8abd7cacd
简单说来，就是计算String 和所有suffix 的similarity并加和
比如 ababaa
所有suffix是 "ababaa", "babaa", "abaa", "baa", "aa" and "a"
他们与ababaa 的similarity 是 6,0,3,0,1,1 所以结果就是 6+3+0+0+1+1=11
另一个例子 aa
suffix是"aa","a"
similarity 就是 2, 1，结果是2+1=3
我的算法是先定义一个similarity function,计算任意两String的similarity值。在处
理问题的时候，生成所有的suffix，string有多长，就有多少个suffix，然后计算每个
suffix和原来String的similarity，最后相加。
运行的结果是只过了4/10个testcase。之后的报错是time limited exceeded. 做过的
人知道是什么原因吗？下... 阅读全帖 |
|
l******t
发帖数: 490 | 15 解答：Allah為什麼有時候用複數代詞“我們”
The Quran, Allah and Plurality Issues (Sam Shamoun)
The Quran, much like the Holy Bible, uses plural pronouns for God even more
so than what we find in God’s true Word. Here are several examples:
This is part of the tidings of the things unseen, which We reveal unto thee
(O Apostle!) by inspiration: Thou wast not with them when they cast lots
with arrows, as to which of them should be charged with the care of Mary:
Nor wast thou with them when they disputed (the point). S... 阅读全帖 |
|
D*V
发帖数: 3096 | 16 SINGAPORE – Internet minders voted Monday to allow virtually unlimited new
domain names based on themes as varied as company brands, entertainment and
political causes, in the system's biggest shake-up since it started 26 years
ago.
Groups able to pay the $185,000 application can petition next year for new
updates to ".com" and ".net" with website suffixes using nearly any word in
any language, including in Arabic, Chinese and other scripts, the Internet
Corporation for Assigned Names and Number... 阅读全帖 |
|
r****s
发帖数: 1025 | 17 这个应该用suffix trie，注意看清楚了，不是suffix tree。
build一个suffix trie可以在O(n)time （Ukkonen's algo)。一般面试的时候直接
build suffix就足够了。
用suffix trie可以轻松解决任何substring问题， 包括longest palindrom问题。 |
|
e********3
发帖数: 229 | 18 抛个砖.有错哪里可以优化请吃出.
public class IntegerToEnglishWord {
public static void main(String[] args) {
IntegerToEnglishWord itew = new IntegerToEnglishWord();
System.out.println(itew.integerToEnglishWord(123456789));
}
public String integerToEnglishWord(long num) {
String res = "";
if (num == 0) {
return "zero";
}
boolean neg = false;
if (num < 0) {
num = -num;
neg = true;
}
Map阅读全帖 |
|
k*i
发帖数: 220 | 19 网上查到说可以用 suffix tree:
The longest palindrome of txt[1..n] can be found in O(n) time, e.g. by
building the suffix tree for txt$reverse(txt)# or by building the
generalized suffix tree for txt and reverse(txt).
具体在建立了 suffix tree之后如何查找 longest palindrome ？
那位高人给指点一下？ |
|
e****a
发帖数: 449 | 20 . 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是
经常在
mitbbs 学习大牛们的帖子. 整理了版上一年内的 和 careercup 上的一些面经, 比较
乱, 大家
可以参考下, 基本上概括了店面的所有题，onsite的大部分题. 非常感谢版上的常驻大
牛小牛们给
我的帮助，现在牛牛们都忙着发财... 阅读全帖 |
|
l******t
发帖数: 2243 | 21 congrats!
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统和网络的基本知识, 还有就是... 阅读全帖 |
|
|
B*******1
发帖数: 2454 | 23 用suffix array的话，需要建立string 和reverse string的混合的suffix array，还
是只需要建立一个string的suffix array,还是没有弄懂整个用suffix array怎么做，
请指教。 |
|
b*****o
发帖数: 715 | 24 你说的对，programming pearls的作者在这里犯了个错误。他假设两个字符串比较只需
要O(1)。而实际上最坏情况是O(1)。
但是貌似suffix tree的算法在最坏情况也是O(n^2)。因为build tree的时候，每次两
个子字符串比较最坏也可能需要O(n)。
一个这样子的例子就是全a串"aaaaa.....aaa"。两个suffix string比较时间平均是n/2。
这使suffix array和suffix tree的最坏时间复杂度分别是O(n^2 log(n))和O（n^2）。 |
|
j******2
发帖数: 362 | 25 看了下，好像不是很简单的啊，尽是些paper。。。
这个suffix array和suffix tree的linear算法要不要掌握啊？本来是在搞DP，结果被
这个longest common substring引得来看这个suffix tree/array，投入的时间越来越
多，但是150和leetcode上都没啥suffix tree/array的问题啊，只有个strstr还蛮简单
的。。。
不是科班出身的就是累啊，千疮百孔的。。。 |
|
G****a
发帖数: 10208 | 26 【 以下文字转载自 JobHunting 讨论区 】
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司: Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公
司。 有一点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经
验, j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统... 阅读全帖 |
|
G****a
发帖数: 10208 | 27 【 以下文字转载自 ECUST 讨论区 】
发信人: BackChina (BackChina), 信区: ECUST
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经 (转载)
发信站: BBS 未名空间站 (Sun Mar 20 18:08:27 2011, 美东)
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司: Blackrock, BOA, Morgan stanley, GS, Fa... 阅读全帖 |
|
B*******a
发帖数: 801 | 28 【 以下文字转载自 JobHunting 讨论区 】
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司: Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公
司。 有一点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经
验, j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统... 阅读全帖 |
|
B*******a
发帖数: 801 | 29 【 以下文字转载自 JobHunting 讨论区 】
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司: Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公
司。 有一点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经
验, j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统... 阅读全帖 |
|
x**********g
发帖数: 327 | 30 【 以下文字转载自 JobHunting 讨论区 】
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非
湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针
对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司:
Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公司。 有一
点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经验
,
j2ee, .net, LAMP 知道一些, 后来突击学习了操作... 阅读全帖 |
|
s*******l
发帖数: 60 | 31 【 以下文字转载自 JobHunting 讨论区 】
发信人: evaeva (evaeva), 信区: JobHunting
标 题: 生物PHD 转行找CS， 报Offer和罗嗦的面经
发信站: BBS 未名空间站 (Sat Mar 19 06:10:37 2011, 美东)
. 在版上潜水快一年了 收获非常大 现在拿到了比较满意的offer, 中型IT公司，环境
还不错，非湾区和NYC， 一年8万多。发找工作的经历回馈本版, 给还在找工或者将要找工的同学
参考.主要针对转行的，没有经验的同学，如果有说的不对的或者废话的, 大家可以直接忽略,因为
本人是菜鸟.
背景: 生物phd, WSN, 计算机 master.毫无工作经验，无实际project经验. 面过的
公司: Blackrock, BOA, Morgan stanley, GS, Facebook, Google 和给offer的公
司。 有一点统计和 ML的知识背景,后来证明毫无用处. c++和 java比较熟悉 没有大project经
验, j2ee, .net, LAMP 知道一些, 后来突击学习了操作系统... 阅读全帖 |
|
s*x
发帖数: 3328 | 32 haha,我就是搞理论的.我今天去面,一个哥们给我出道题,其实那道题目我见过,是我最
近发的一个论文里边的,不过有点久了一时没想到.我临时想出一个很直接的算法,平方
时间的,然后用Java写出来,很直接很直接的想法,也怪我平时练得少,code写出来自己看
都觉得乱糟糟的,后来我俩研究半天觉得我写的code还是没有大问题的,他把code抄他本
子上留着写报告,其实我写code的时候想起来我当初怎么解决这个问题用线性时间的了.
就是构造一个suffix tree,然后套lca的[O(n),O(1)]的算法,这些都是现成的算法,不过
我也和面的人说了,non trivial,临时这点时间写出Java代码来是不可能了.我现画了个
suffix tree给他看,看他表情应该是只知道 B tree 的样子,后来我又用他给的例子加
上我画的树演示给他看我的算法怎么样的,最后他认同我的线性算法了,但是还是对如何
O(n)构造出suffix tree和如何O(1)求出lca表示怀疑,我当时也不好说什么了,确实,如
果我没写过那个paper我也真不一定能想起这些东西来.但是在学校里就有这个机会学习
这些东... 阅读全帖 |
|
k***e
发帖数: 556 | 33 来自主题: JobHunting版 - 新鲜面试题 it seems that suffix trie did not work. if we set up suffix tree for
separated urls, we still need to check every url for match. if we combine
the urls into a big suffix tree, then it is hard to use the tree labels for
searching.
*o*ve*ou => o, ve, ou, 然后分别用o, ve, ou 查询
I don't know why you think this did not work. I think we can extend that
idea. It is infact k-gram method in the information retrieval. for example,
2-gram of google will be go, oo, og, gl, le. We preprocess all the urls to
get i |
|
s*******i
发帖数: 712 | 34 我和你想的差不多，最后说的算法就是suffix array。但真的没法code啊，太复杂了。
而且page
name都是string，要处理过才方便用suffix的办法。最绝望的是我把算法说了一下，
interviewer
对这类suffix算法貌似完全没有概念，听得很蒙。不知他想要什么样的答案。 |
|
g*******y
发帖数: 1930 | 35 Hint1:
I was told by krone, that you has to combine this problem with LCA (lowest common anceaster).
Hint2:
You surely start from considering txt and reverse of txt.
Hint3:
Keep in mind that a leaf node in a suffix tree corresponds to a suffix. Obviously, if you are looking at a specific suffix, you can get a pointer to the corresponding leaf node in O(1) time.
Hint4:
Also keep in mind that finding a palindrome is somewhat unlike finding
longest common substring in which two common substrings do |
|
r**u
发帖数: 1567 | 36 suffix tree 应该可以干这事吧。每一行是一个string，找所有suffix，放suffix
tree，tree node要记录出现次数，出现次数最多的就是结果。 |
|
f*********5
发帖数: 576 | 37 suffix tree :basically store one string at its suffix string array
prefix tree(Trie): store a number of strings.
for my understanding, suffix tree will be used to substring related issues
while trie/prefix tree will be used to store a large number of data,for
example,
dictionary |
|
c*******t
发帖数: 1095 | 38 听说suffix可以做到O(n)
那比如abcbbddecba
正向suffix：
|(1:abcbbddecba)|leaf
tree |
| |(3:cbbddecba)|leaf
|(2:b)|
| |(5:bddecba)|leaf
| |
| |(6:ddecba)|leaf
| |
| |(11:a)|leaf
|
| |(5:bddecba)|leaf
|(3:cb)|
| |(11:a)|leaf
|
| |(7:decba)|leaf
|(6:d)|
| |(8:ecba)|leaf
|
|(8:ecba)|leaf
逆向suffix
|(1:abceddbbcba)|leaf
tree |
| | |(4:eddbbcba)|leaf
| |(3:c)|... 阅读全帖 |
|
h**********d
发帖数: 4313 | 39 bless lz
这题可以详细说说 suffix tree是怎么存电话本信息的吗，谢谢！
1.设计个电话本 可以用那些数据结构
我说suffix tree, 哈希表
问了这两种方法的比较，还考了suffix tree的插入， |
|
r*******e
发帖数: 7583 | 40 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(t... 阅读全帖 |
|
r*******e
发帖数: 7583 | 41 1. "abcdefg" -> "abcdef" -> "gabcdef", the distance is 2
deletion and the addtion are counted as 2 edits, not a single one
2. one can build a (basic) suffix tree for the string txt1$txt2#, where `$'
is a special terminator for txt1 and `#' is a special terminator for txt2.
The longest common substring is indicated by the deepest fork node that has
both `$...' and `...#' (no $) beneath it.
The longest palindrome of txt[1..n] can be found in O(n) time, by building
the suffix tree for txt$reverse(t... 阅读全帖 |
|
r*******g
发帖数: 1335 | 42 Hi
能否详细说说suffix tree怎么做，如果像你们讨论的那样suffix tree很难O(n)构造出
来，那这个题的复杂度究竟是多少呢？我能想到的就是构造两个suffix tree混在一起
，然后再找LCA。
你这里的lcs是什么意思？
谢谢了 |
|
S**I
发帖数: 15689 | 43 ☆─────────────────────────────────────☆
sharc (sharc) 于 (Mon Aug 22 15:15:14 2011, 美东) 提到:
刚从G家onsite归来。新鲜面经奉上。
总共5轮，4轮technical interview, 一个thesis discussion。在technical里，有编
程题，有open design。我记得的问题有：
1. 编程题：一堆字符串。找longest common prefix。
我的方法就是找最短的字符串，对它的每个字符，逐个与其他字符串对应位置比较。（
求更好方法）
2. open question: 一堆文件，size差别极大( from KB to many GB). 找出所有内
容相同的文件。
3. 编程题： 有一个observer 类，监视另一个类foo 的成员变量的值，每当那个值被
修改，就要调用 该observer.updated() 方法。需要实现 foo.registerObserver(ob)
, foo.unregisterObserver( ob )... 阅读全帖 |
|
b*******d
发帖数: 750 | 44
duplicate
可以用修改后的suffix tree么？build suffix是linear time，虽然那个算法非常复杂
，很难一下写出来。但是其上每个node的path（从根开始的path）都是一个substring
。把每个node设计成
node {
char c；
List startPos；// 记录下这个node的从根到该node的path的起始点在原
string的位置。是个list因为可能有很多个这种string。
int pathLen; // 记录下这个node的从根到该弄得的path的长度,即该substring的
length。
}
build suffix tree的时候，如果add node时候，发现该node已经存在，说明该
substring已经存在，如果存在一个startPos + pathLen == curStartPos,说明存在一
个连续repeated的substring。
应该是linear time |
|
s*****n
发帖数: 162 | 45 用suffix tree的话，对于这种sequence的suffix，它们不重合，比如
0 1 1 2 3 5 8 13 21 34
suffix
34
21 34
13 21 34
8 13 21 34
5 8 13 21 34
3 5 8 13 21 34
2 3 5 8 13 21 34
1 2 3 5 8 13 21 34
1 1 2 3 5 8 13 21 34
0 1 1 2 3 5 8 13 21 34 |
|
j******2
发帖数: 362 | 46 DP用的就是suffix array吧？用generalized suffix tree是另一种，不过还是决定把
它搞搞清楚了。好像很多DP问题都可以用suffix tree来搞。 |
|
b****g
发帖数: 192 | 47 刚刚试了一下，DP和suffix tree都能做。
但是不知道用suffix tree是不是最快，因为careerCup 150里的那道题是看第二个
String的任意子串是不是在第一个string里。你的问题只需找出最长的子串。不知道用
suffix的方法是不是多余。但我又想不出更好的方法。 |
|
j******s
发帖数: 48 | 48 map reduce吧
for node and its adj list,
map emit(node,adj+" 1") and emit(adj,node+" 0")
suffix " 1" stands for I have a friend **
suffix " 0" stands for I am the friend of **
reduce output all combination of value with different suffix "0" and "1",
which is I am the friend of **, and I have a friend **.
And it needs to detect that ** and ** is the same person. (Mutual friend)
传统的bfs没想到如何提高并行度. |
|
s********u
发帖数: 1109 | 49 C++写了一个，如果不用DP的话，把这个map去掉即可，试了一两个字符串似乎没问题。
vector wordBreak( string s, map< string, vector >& cache){
vector vs;
vector suffixSet;
string tmp;
if( s.size() == 0 ){
vs.push_back(s);
return vs;
}
if(cache.count(s) > 0)
return cache[s];
string prefix, suffix;
for(int i = 1; i <= s.size(); i++){
prefix = s.substr(0,i);
if( isWord(prefix) ){
... 阅读全帖 |
|
s********u
发帖数: 1109 | 50 之前有人放过这个题，就是提供一个bool isWord(string s)的函数，要求得到一个
string拆成若干个word的所有组合，word之间用空格隔开。
自己写了下，用递归 + memoization，想问问这个题有iteration的做法么？如果是每
个string有唯一解（只有一种拆法）呢？
vector wordBreak( string str, map >& cache){
vector vs;
if( str.empty() ){
vs.push_back(str);
return vs;
}
if(cache.count(str) > 0)
return cache[str];
string prefix;
string suffix;
vector segSuffix;
for( int len = 1;len <= str.s... 阅读全帖 |
|
