|
g*****i
发帖数: 2162 | 2 suffix array的lcp 怎么在nlogn算?有code看看吗?
tree |
|
g*****i
发帖数: 2162 | 3 Wikipedia只给出了O(n)的算法reference,这个估计interview也写不出来.
谁能给个容易写的nlogn算法? 谢谢. |
|
a********1
发帖数: 750 | 4 我想错了，是nlog^2n 当然还是比n^2好
我晚上贴上来吧 |
|
|
B*******1
发帖数: 2454 | 6 这哥们写的code也挺难学的，其实不就是qsort就好了？ |
|
|
a********1
发帖数: 750 | 8 嗯，，不过lz的问题是nlogn的构造
感觉快的string算法的基本思想都差不多，就是把已知的比较结果发挥到极限。 |
|
|
m**q
发帖数: 189 | 10 考古到一道老题：
给个string,判断这个string是否是某个pattern的周期循环
（这个pattern不确定）要nlgn复杂度 我给了算法 ，
不能cover所有情况，提醒后，给了正确算法，然后code,没错
我的思路是用suffix array，创建后sort，然后在sorted array中
比较相邻的元素，如果前面的字符串长度小于后面，则后面的字符串
应该包含前面的，且两个字符串的差就是循环的pattern - 如果对于
所有的相邻元素都成立，则可以确定原string是这个pattern的循环
大家看看有更好的思路么
abcdabcd:
abcdabcd abcd
bcdabcd abcdabcd
cdabcd bcd
dabcd --> bcdabcd
abcd cd
bcd cdabcd
cd d
d dabcd
ababab:
ababab ab
... 阅读全帖 |
|
b***e
发帖数: 1419 | 11 貌似判最长的自相交O(n)可以搞定。用suffix tree. |
|
u***q
发帖数: 21 | 12 我回答的是把字典的单词存到suffix tree里，然后将给定string的字母的排列组合在
树中搜索。她提醒我排列组合会很多，我就说可以先只取2到3个字母的排列组合搜索单
词的开头，这样可以大大减少组合数，她表示同意。还问了我怎么产生这些组合，我说
没有重复字母的话，简单的for loop就可以。有重复的情况，我没想出来，她也没盯着
不放。后来她告诉我Java有现成的library产生排列组合，我还真不知道这个。 |
|
k****n
发帖数: 369 | 13
这不就是传统数据库么。。。
数据放在一个静态数组或者list里面，用BTREE或者HASHMAP做name的index
can
老题就看经典好了，IR领域的经典题，看怎么做模糊检索
大概就是做cyclic suffix tree，或者bi/tri-gram的index什么的
但是为什么这个能match到itveabcu呢？最起码结尾应该是ou吧？ |
|
|
I***A
发帖数: 6 | 15 这几天一直在考古这类题目的老题 也包括像Spell Checker之类的；发现大多数
问题是围绕 suffix tree, trie, hash table;之类的数据结构展开；但是究竟在什么
情况下用那一种,如何设计字典, 觉得很迷惑，有没有大牛能解释一下这类问题的解答
要领？ 尤其是什么时候用哪个数据结构合适？ 先谢谢了！ |
|
B*******1
发帖数: 2454 | 16 来自主题: JobHunting版 - 问个算法题 求一个字符中连续出现次数最多的子串
abcbcbcabc 中，连续出现的字符串为bc,连续三次
abcccabc中，最多的为c
要是不要求连续的话用suffix array很好弄，但是连续的，怎么弄才好呢？
谢谢。 |
|
l******c
发帖数: 2555 | 17 来自主题: JobHunting版 - 问个算法题 suffix tree |
|
a**********2
发帖数: 340 | 18 来自主题: JobHunting版 - 问个算法题 建suffix tree，节点上计数 |
|
b******g
发帖数: 1721 | 19 来自主题: JobHunting版 - 问个算法题 这个suffix tree本身就是连续substring啊。
你的意思是不是“如果不是连续的就不知道怎么弄了”？ |
|
b******g
发帖数: 1721 | 20 来自主题: JobHunting版 - 问个算法题 bcd 是后缀，而且在suffix tree里面，bc是从root出发的substring。可以bottom up
计数，正如airplane1022所描述的。 |
|
m**q
发帖数: 189 | 21 来自主题: JobHunting版 - 问个算法题 我觉得连续的子串也可以用suffix array啊
比如 abcbcbcabc
0123456789
0 abc
9 abcbcbcbcabc
5 bcabc
3 bcbcabc
1 bcbcbcabc
9 c
6 cabc
4 cbcabc
2 cbcbcabc
把sort后的array扫一遍，对于相邻的两个子串，判断它们的最长公共前缀
的长度是否是个等差数列，且这个等差数列的差等于相邻的两个子串的
index之差 |
|
c*****e
发帖数: 3226 | 22 2-3-4 tree, suffix tree, ....
特别是那些business applications适合那种数据类型。。要零时抱佛脚一下。/
wikipedia 有点冗长。 |
|
H***e
发帖数: 476 | 23 我本来不想看这两样的，但是发现好像有考到的？
虽然觉得面试考这个很刁难，可总是觉得这块没攻过，心里不舒服
查了下，发现都很繁琐。。
谢谢了 |
|
|
S**I
发帖数: 15689 | 25 ☆─────────────────────────────────────☆
sugarbear (sugarbear) 于 (Thu Apr 7 00:42:48 2011, 美东) 提到:
找 二叉树 两个最大的相同子树
没答上来。
见了四个，被拒了。 第二个是manager，后来主动写信跟我联系，说把我推荐给industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更难吧？ 求祝福！
☆─────────────────────────────────────☆
boohockey (Pursuit of Dreams!) 于 (Thu Apr 7 10:27:03 2011, 美东) 提到:
bless
这道题有没有正解
industry recruiting team，不知道是不是有转机？ 觉得industry recruiting应该更
难吧？ 求祝福！
☆─────────────────────────────────────☆
grass (美丽人生) 于 (Thu Apr... 阅读全帖 |
|
g*****e
发帖数: 282 | 26 概率题没看懂。。。
“twitter的follow关系”是对每个pair当key么？那样这个hashtable不是一般的大了
最后一题是拨电话求可能的对应字符串的翻版吧，suffix tree？代码很难写 |
|
g*****e
发帖数: 282 | 27 概率题没看懂。。。
“twitter的follow关系”是对每个pair当key么？那样这个hashtable不是一般的大了
最后一题是拨电话求可能的对应字符串的翻版吧，suffix tree？代码很难写 |
|
|
m***n
发帖数: 2154 | 29 double hashing or suffix tree ? |
|
i*********7
发帖数: 348 | 30 应该是类似Trie tree的原理。具体不清楚。不太可能用suffix tree吧。
我记得第一步是将所有元素的字符串分别作为子节点接到根节点。接下来就忘了。。 |
|
b********e
发帖数: 215 | 31 随便瞄了一眼好像还挺复杂的，这个面试的时候考的多吗？有必要掌握吗？ |
|
|
|
w****x
发帖数: 2483 | 34 不需要, trie tree就可以了, 你要是搞懂了我鄙视你 |
|
|
|
Z*****Z
发帖数: 723 | 37 昨天看了一眼，很多string的问题都能用上，及其牛笔。我觉得至少由哪些问题知道可
以用东东做吧。 |
|
|
h**********l
发帖数: 6342 | 39 binary search 长的那个string
想象空格把长string 分成 一个array of strings
最坏还是 M*N, 平均 N*logM,
用 suffix tree可以 N+M最坏，N+logM平均 |
|
j********e
发帖数: 1192 | 40 M是数组string的长度吧？
用binary search，最坏也不是M*N，也是N*logM.每次分割，不会有unbalance
的情况。
不知道你suffix tree怎么弄到N+logM. |
|
d**********x
发帖数: 4083 | 41 suffix tree吧
那破玩意我就没仔细看过。。。
，我 |
|
a********d
发帖数: 195 | 42 2.2 麻烦谁能给个java的例子么？好像是suffix tree但是具体的还不是很明白。
4的话用lru的思路行么？linkedlist + hashtable，不过每次time tick都要更新链表
和hash好像不好。 |
|
M**********7
发帖数: 378 | 43
suffix tree反正我现场不可能用的，这题就是每次找串从中心开始扩展，平方的复杂
度。不知道有没更好的。
我就是用的这种，time tick用timer的callback，尽量用一个timer 然后根据元素的时
间戳更新下次查看时间。 |
|
M**********7
发帖数: 378 | 44 亲到时别太执着了，到时候可以想一个你能当时做的思路，然后同时抛出这两个思路，
吹一下suffix树，然后说这个现在肯定写不完啥的。对方估计会让你写另外一个。 |
|
f******h
发帖数: 45 | 45 但是 建suffix tree 还是需要至少 O（nlgn）的复杂度吧。 |
|
i***e
发帖数: 452 | 46 这个题用suffix array 比较好做啊。 programming pearl chapter 15章的内容。 O（
nlongn). |
|
r**********g
发帖数: 22734 | 47 标准算法吧
construct suffix tree
find deepest internal node
trace from root
O(n) |
|
p*****2
发帖数: 21240 | 48
刚才看了一下。construct suffix tree好写吗？从来没写过呀。 |
|
r**********g
发帖数: 22734 | 49 我觉得值得一学。suffix tree搞好了以后无数东西都解决了
n^ |
|
g**e
发帖数: 6127 | 50 如果不用写build suffix tree代码的话还是可以写一下的
n^ |
|
