i****h
发帖数: 321 | 1 我只知道suffix array可以用来计算longest common prefix。。。
能给个link吗？谢谢。 |
|
|
m******9
发帖数: 968 | 3 他说的方法挺好的
longest palindrome, 就可以用string 和 reverseed string, 然后DP找LCS, 现场
coding也比较方便.
更好的就是你提到的suffix tree |
|
u**s
发帖数: 50 | 4 Simple application of suffix tree. |
|
s****t
发帖数: 36 | 5 刚刚面完amazon的，facebook的是上周五的，
amazon：
1.找出一组数里面相加起来为y的pair
2.设计一个 parkinglot。
没什么别的问题，基本上30分钟没到就说他没什么问题了，问了他几个问题基本上撑到
40
分钟。时间太短是不是没戏啊？是个印度人。2面。
facebook：
1.implement strstr()
2.如果很多次strstr query，但是base的string不变的话，用什么structure，如果
base string大到内存放不下，那用什么structure。
suffix tree， Btree |
|
a*u
发帖数: 97 | 6 同问～
如果不是，prefix sum and suffix sum are not sorted, how to use binary search? |
|
c********t
发帖数: 1756 | 7 这个分类好，以后我们可以分级讨论。
不知hash table 相关的题算哪一类；
还有suffix tree相关问题? |
|
j**l
发帖数: 2911 | 8 如果题目看过弄懂了，开国大老的题做起来也就和新手上路一样了。
关键是锻炼自己的思维，举一反三。这样在做从没见过的长老级以上的题目时候很有用。
Hash表算中高级站友，就怕问到解决冲突，再Hash的一些细节。
Suffix和trie，弄懂原理也快，就是怕让你实际写个完整代码，据说在面试短短时间是
不够的。 |
|
|
w******1
发帖数: 520 | 10 用树来做。
Generalized Suffix Tree |
|
x***y
发帖数: 633 | 11 We can reduce Hamilton Path to this problem as follows:
assume that the largest weight of all the edges in HP is K (or a larger value to make reduction possible), and this is the length of each string we will use. So, we reduce HP problem by: if for two nodes X, Y and the weight of their edge is m, then we convert the node to 2 strings x', y', such that the length of largest common substring between x' suffix and y's prefix is K-m( when K is large enough, this is possible). Then, the each HP pro |
|
s********e
发帖数: 28 | 12 I agree! 我也一直有这个疑问。
不管楼主说的是找longest common substring or longest common subsequence in
string and reversed string, 在下面这个例子中都是不对的。There is NO
palindrome in "abcXYZcba", however the longest common substring is abc or
cba, the longest common subsequence is abcXcba, or abcYcba, or abcZcba.
suffix tree 的解法也有这个问题。这是我长久以来的疑问，难道是我对palindrome的
理解有误？可以不连续？
哪位大侠给解答一下？ |
|
y*c
发帖数: 904 | 13 DP还没好好做过
经典的方块里面找方块还没搞明白
听说suffix tree很久了，还没时间学过
再加上明天是 5 14........ |
|
a****x
发帖数: 89 | 14 我先给的N^3,问有什么改进? 我第一个念头也是suffix tree，后来马上意识到DP更直
接，也好code |
|
j**l
发帖数: 2911 | 15 总结一下好了。
涉及一个string的palindrome，包括求最长，求所有奇数长，求所有偶数长
可以用以下两种方法
方法一，化归为求string和逆string的LCSubString, 可以用DP, 也可以用suffix tree
方法二，直接用DP, 利用L[i][j] = L[i+1][j-1] && s[i] == s[j]
我们可以规定，当i >= j的时候L[i][j] = true
这样，对特殊情形L[i][i+1]也适用L[i][j] = L[i+1][j-1] && s[i] == s[j]
二重循环的技巧是，
第一重是步长k, palindrome的长度为k+1
第二重是palindrome的起始点i
下面的例子只是找所有长度大于1的奇数
for (int k = 2; k < N; k += 2)
for (i = 0; i < N - k; i++)
如果找所有长度为偶数的呢，那就可以改为
for (int k = 1; k < N; k += 2)
如果找全部长度不为1的呢，那就改为
for (int k = 1; k < N; k++) |
|
j**l
发帖数: 2911 | 16 方法一DP确实不行，小尾羊说要用suffix tree做。
方法二的那个DP, 暂时没看出有什么问题。
对这道题，二重循环也够用了，DP可能是牛刀 |
|
|
h**k
发帖数: 3368 | 18 longest common substring?
sigh,不会suffixs tree,都没有办法去fb面试。 |
|
r****o
发帖数: 1950 | 19 多谢。想问两个问题:
1. 像字符串索引这样的题目什么时候用prefix tree好，什么时候用suffix tree好呢?
2. 一个integer array，只有一个数出现1次，剩下的都出现2次，找到那个特殊的。
为什么hashtable大小是(N-1)/2+1呢? 如果array里面的数可以任意，不局限于[1..n]
，这个hashtable的大小还是(N-1)/2+1吗？
[在 ZhangBZ (向日葵) 的大作中提到: 】
hashtable
array |
|
j**l
发帖数: 2911 | 20 这些难题要么涉及不容易找到状态转移方程的DP，要么需要想到很巧妙的trick，要么
涉及trie, suffix tree等一些高级的数据结构，不准备的话现场短时间确实很难做出来。
但是这些题只是锦上添花，而且这些题的变体无穷无尽，你不能保证在有限的复习时间中把它们全部都背下来。所以，关键是总结出它们的思想方法而不是背诵题目本身。
就好比高考数学，压轴的大题能做出来最好，但是前面的容易题和中等题，绝对是拿分
的重点。又好比欧洲足球联赛，联赛冠军经常在小四强联赛中拿分不多，但对中下游的
球队几乎不会翻船，总是一场又一场的全取三分。利物浦双杀曼联又如何，平局太多还
是让曼联拿走了冠军。
面试官不问难题不等于不能考察你的能力了，甚至可能要求更苛刻。比如求x的n次方，
能想到利用二进制数得到log(N)的方法么，能想到结合矩阵把结论推广到求菲波纳切数
列么？比如统计句子中单词的个数，能想到只用一重循环的检测脉冲技巧么？再比如求
n的阶乘，能同时想到迭代法，递归法，尾递归法，动态规划法么？能很好的解决
overflow问题么？能否实现大数阶乘么？能否想到如何求出结尾的0的个数么？能否想
到如何求 |
|
N*D
发帖数: 3641 | 21 顶，说出了俺的肺腑之言啊
这些难题要么涉及不容易找到状态转移方程的DP，要么需要想到很巧妙的trick，要么
涉及trie, suffix tree等一些高级的数据结构，不准备的话现场短时间确实很难做出
来。
但是这些题只是锦上添花，而且这些题的变体无穷无尽，你不能保证在有限的复习时间
中把它们全部都背下来。所以，关键是总结出它们的思想方法而不是背诵题目本身。
就好比高考数学，压轴的大题能做出来最好，但是前面的容易题和中等题，绝对是拿分
的重点。又好比欧洲足球联赛，联赛冠军经常在小四强联赛中拿分不多，但对中下游的
球队几乎不会翻船，总是一场又一场的全取三分。利物浦双杀曼联又如何，平局太多还
是让曼联拿走了冠军。
面试官不问难题不等于不能考察你的能力了，甚至可能要求更苛刻。比如求x的n次方，
能想到利用二进制数得到log(N)的方法么，能想到结合矩阵把结论推广到求菲波纳切数
列么？比如统计句子中单词的个数，能想到只用一重循环的检测脉冲技巧么？再比如求
n的阶乘，能同时想到迭代法，递归法，尾递归法，动态规划法么？能很好的解决
overflow问题么？能否实现大数阶乘么？能否想到如何求出结 |
|
|
r****o
发帖数: 1950 | 23 什么时候用suffix tree, 什么时候用prefix tree呢？
好像两个都可以用于字符串匹配的问题。 |
|
r****c
发帖数: 2585 | 24 两个应用不同啊
suffix tree一般用来表达一个或多个string internal, like substring of a string
prefix tree (trie) 只是表达几个strings' substring which starts from
beginning |
|
r****o
发帖数: 1950 | 25 那能用prefix tree的场合应该也可以用suffix tree吧?
string |
|
y****n
发帖数: 579 | 26 来自主题: JobHunting版 - 一道面试题 觉得是suffix/prefix tree加Levenshtein distance。
把distance小的给output出来。 |
|
f*********5
发帖数: 576 | 27 1)create a generalized suffix tree for A[0..n] and its reverse string
B[0..n]
###u need to make sure that u can get LCA of two nodes with O(1).
This step is difficult,i think unless u understand it very well,
otherwise it is very difficult to recite..
2) for (i=1;i
find max {LCA(a[i],b[n-1-i]),LCA(a[i+1],b[n-1-i])}
3) the max LCA is just the length of longest parlindrome,
i or i+1 is just the center of the parlindrome |
|
|
g****n
发帖数: 431 | 29 看看这个办法行不行：
先把A和B两个字符串相同的prefix和suffix去掉，因为相同的前缀、后缀不影响答案。
然后需要做
的就是要么在A'的左端insert，右端delete；要么在A'的左端delete，右端insert。尝
试2次，就
可以得到解。
举例：
str B：ABCDE
case 1-
str A：ACDEF
去掉前后缀后，A'为：CDEF，B'为BCDE,比较可知在A'左端insert，右端delete即可。
case 2-
str A:BFCDE
去掉前后缀后，A'为：BF，B'为:AB,比较可知在A'左端insert，右端delete即可。
case 3-
str A:XABCE
去掉前后缀后，A'为：XABC，B'为:ABCD,比较可知在A'左端delete，右端insert即可。
大家看看有没有返利。
volunteered. |
|
K******g
发帖数: 1870 | 30 题目太长，是一个关于suffix array的题目
大家都应该有书吧？翻一下就好了 |
|
B*****t
发帖数: 335 | 31 先找出两个seq的suffix array，然后在SA上找max window，找max window的过程和
已知中序，后续遍历，重建二叉树的方法很象。 复杂度O(nlogn)
of matching
window is 4. ( |
|
l*****a
发帖数: 14598 | 32 不错
难道是generalized suffix tree？？？
BTW，第三题可以用两个heap解决
max heap+min heap |
|
j*****g
发帖数: 223 | 33 Hm...看着像suffix tree. 研究研究..... |
|
j*****g
发帖数: 223 | 34 Still looking at @ihasleetcode suggested Dr.Dobbs algorithm which looks like
a suffix tree matching.
As for @done, does your algorithm pass on this test case?
string : abc
pattern: b*
It's a not match. But in your code, the inner loop will break out when
comparing 'a' vs 'b'. after breaking out, the outer loop will advance s
pointer, so next time, p1 will be pointing at 'b', and s1 will be pointing
at 'b'. After that, seems your algorithm will match them and return 1.
Can you double check?
BTW, ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 35 No need suffix tree or any advanced data structure. No need dynamic
programming. All you need is two pointers,
iterating through the pattern and string at the same time. Need to take
extra care for special cases.
I have wrote the code below:
bool match(const char *str, const char *pattern) {
const char *p1 = pattern, *p2 = str;
if (*p1 && *p1 != '*' && *p1 != *p2)
return false;
while (*p1) {
while (*p1 == '*')
p1++;
if (!*p1) return true;
while (*p2 && *p1 != *p2)
... 阅读全帖 |
|
j*****g
发帖数: 223 | 36 想出来个新方法，至少看上去挺简单的，不用recursion, 动态规划，suffix tree, 或
脑筋急转弯的算法。
case 1。看看一个普通的pattern string (not edge case):
*str1*str2*str3*
where 1) strN is basically a-z plus '.' 2) assume we've already collapsed
multiple consecutive *'s into a single *.
在这种情况下, 去匹配target string就是一个贪心算法:
start = target;
foreach (strN)
{
new_start = strstr(target + start, strN);
if (new_start == NULL) return false;
start = new_start + len(strN) + 1;
}
return true;
case 2。再看看其他pattern string的情况:
如果pattern string is like... 阅读全帖 |
|
i**********e
发帖数: 1145 | 37 谢谢楼主的总结，我觉得都非常全面，包含了CS的各个基础。而且有些问题很难，不好答。（A*这个算法能当场写出来也太牛了吧）
但是我觉得有些方面面试比较少会问的吧（就算问到也是解释概念就可以了，不会要求
coding），例如：
black-red (BR/AVL is a stretch)
Suffice/prefix trees (trie)
例如，black-red tree是用来干嘛的，suffix/prefix trees在哪一方面有所辅助，为
什么等等。因为这些都是比较复杂的，面试不宜问太复杂的算法。
比较常见的面试题几乎都逃不了 Linked list 和 Binary Tree，前者考你对 pointer
的熟练，后者则考你递归的思路。字符串处理也是常见题（尤其对C/C++语言程序员来
说）。
在object-oriented语言方面，时常被问到的有（以下针对的是C++语言）：
1）什么是virtual function? virtual function 怎么在编译器里实现？
2）在何时destructor应该是virtual? 为什么？
3）怎么实现一个singleton... 阅读全帖 |
|
l*****a
发帖数: 14598 | 38 suffix array
please check programming pearls |
|
a**********2
发帖数: 340 | 39 3.O(n)使用suffix tree，写个伪代码就可以了吧
6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回 |
|
a**********2
发帖数: 340 | 40 3.O(n)使用suffix tree，写个伪代码就可以了吧
6.存leaf上不就行了么？从当前节点开始做一个dfs，找到就返回 |
|
l*******y
发帖数: 1498 | 41 我只会用手一步步画出来，感觉画出来就比较麻烦了。要是写算法，那就有点BT了。 |
|
s*******e
发帖数: 93 | 42 build a suffix tree for the long string? |
|
s*******e
发帖数: 93 | 43 我不知道以前讨论的结果，不过第一题用suffix tree 应该就可以了吧
*
j i m
i m
m
第二题反查的话需要做到用号码的一部分也查出人名吗？如果只需要通过完整的号查出
人名就hash就好了吧（好像iPhone 4就只能这样）。 |
|
l*****v
发帖数: 498 | 44 1个小时，phone screen
1道coding，非常简单要一行一行的念给他听，我刚开始的时候愣了好一会，没想到这
么简单。可能是warn up吧。
1道design，让我设计一个gambling 的游戏。先是框架，然后drill down。我借机说了
一些design pattern(factory observer)
2 道algorithms
2.1 tasks schedule， task之间有depedency
2.2 巨大的input string 里面找子窜 的次数和位子。我说用suffix tree。
开头问我对他们公司什么产品感兴趣，为什么要离开现在的公司。我反正歌功颂德了一
番但明显马屁没拍对。有没有版友有好的建议，每回这种问题我都答不好，虽然我知道
general rule是looking for more challenge，但好像总是没法让对方满意。 |
|
d****j
发帖数: 293 | 45 Bless 一下！
2.2. input String很大的话，再用suffix tree不是占用更大的空间了吗？
我对why choose our company?这样的问题也很头疼，这些大公司要challenge的东西都
大同小异啊，e.g. large scale. 显然回答起来都会很general，不能深入
同问 |
|
f******7
发帖数: 941 | 46 面的是Business services division. 见了2个组的人，5个人，4老印，1老美。Onsite
的时
候才知道这个组是做ERP软件的。
简历上的东西问得很少，只问了现在正在做的工作（跟ERP相关）。至于技术题目，都
是一些很常规
的题目。
第一个，聊了很久ERP方面的东西，最后只问了一道技术题。
An array of continuous integers, only one number is duplicate, find out
this number. What about there is a number is missing, how to find out
both the duplicate and missing numbers.
第二个，问了heap跟stack的区别，以及什么情况下会OutOfMenoryException。然后就
是技术
题了。
Reverse a string. e.g. he is a man => man a si eh
Reverse a string without reversing the words. e.... 阅读全帖 |
|
|
l*****a
发帖数: 14598 | 48 来自主题: JobHunting版 - 最长回文串 你这个复杂度是多少？
有一种O(N2)很直接的
string is a[0]..a[n-1],
assume a[i] (i=1..n-2) is the middle(or a[i+1])
judge whether a[i+k]==a[i-k] then k++ or get the
longest palindrome with center a[i]...
最快的是generalized suffix tree,O(N),but need extra space
store A and reverse string B in the GST,
for(i=1;i
find max LCA(a[i],b[n-1-i])and LCA(a[i],b[n-i]) |
|
c******e
发帖数: 1032 | 49 来自主题: JobHunting版 - 最长回文串 suffix tree o(n) |
|
r*****b
发帖数: 8 | 50 给a list of number, 返回前top K个：用min-heap？不过如果内存不够怎么办啊？
找两个链表的交集，具体是什么意思？
算阶乘：
可以事先存好一些值，比如存好K!, 当N>K时，就只要计算N*(N-1)*...*(K+1)*(K!)
这样做可以么？
设计电话簿的题：为什么要用suffix tree啊？ |
|
