h**********d
发帖数: 4313 | 1 这是prefix tree吧
楼主说的suffix tree是怎么用的？ |
|
g*********s
发帖数: 1782 | 2 co-confused. prefix and suffix tree are different. |
|
A*********3
发帖数: 70 | 3
可以事先存好一些值，比如存好K!, 当N>K时，就只要计算N*(N-1)*...*(K+1)*(K!)
我也是这么回答的
suffix tree－因为是按照姓名存储的，比如Mary就一个字母一个树节点存储，a是M的
孩子 |
|
|
z**c
发帖数: 625 | 5 把careercup那本书的第四版的第20章的第8题做一下,我觉得帮助挺大 |
|
z****o
发帖数: 78 | 6 这个是标准的Suffix Array的 nLogn 吧 |
|
g*******s
发帖数: 490 | 7 汗，没看清楚，以为是subsequence, substring就是suffix tree了 |
|
e****a
发帖数: 449 | 8 1 就是test是不是满足 soduko， careercup 150 上有
2 最优解我知道的是 suffix tree 加 LCA, o(n), 也是比较原来的和反转的string,
不过有点复杂。
3 题目出自： 一个任意的长方形如何分成最少的正方形
除了3 我遇到的都是很基本的题，应该是要给出最优解写无bug代码 3也许不难，不过
我没见过。 |
|
h*****1
发帖数: 74 | 9 how about this:
in-order traversal to get a string. then use suffix tree to find the two
identical strings. it is O(n) time and O(n) space. |
|
g*****i
发帖数: 2162 | 10 第六题是suffix tree吧
第二题板上讨论过,当时没仔细看,谁能给个link吗?
第五期我也不知道,求解.
应用 |
|
g**e
发帖数: 6127 | 11 第一题难道不是base10->base26？
double lock checking with volatile instance. it's not a good design however.
check wiki page for private inner class implementation.
第五题有个trick，他们没有限制子字符串的长度。所以单个字符也是一个子字符串。
题目就成了寻找第三个重复的字符…… 一个hashmap或者bit array就行了……
第六题最佳解法suffix tree找longest common ancestor， O(n)。要现场写估计不太
可能。
第七题，问过当事人，只读不写。应该容易点了吧 :)
应用
写,
包括
smart
其 |
|
g*********s
发帖数: 1782 | 12 1. word edit distance.
i know it's dp. but what are the legal edit moves?
say, "abcdefg" -> "gabcdef", the distance is 2 or not?
if it's allowed to delete/insert @ any pos, we just delete @ tail and
insert @ head. but the dp recursion definition seems not to cover this
case.
2. longest palindrome substring.
O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
give a clear description of this solution? |
|
h*****1
发帖数: 74 | 13 第二题能写出N^2 的算法就可以了吧。至于那个N的算法，我觉得知道就可以了。要真
考那个Ukkonen的suffix tree 算法，那真是太疯狂了。 |
|
s*****y
发帖数: 897 | 14 同问，suffix tree和trie的要当场写吗？ |
|
g**e
发帖数: 6127 | 15 面试的人没几个知道suffix tree和trie的
某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree |
|
g*********s
发帖数: 1782 | 16 1. word edit distance.
i know it's dp. but what are the legal edit moves?
say, "abcdefg" -> "gabcdef", the distance is 2 or not?
if it's allowed to delete/insert @ any pos, we just delete @ tail and
insert @ head. but the dp recursion definition seems not to cover this
case.
2. longest palindrome substring.
O(N^2) is simple. the optimal is O(N) with suffix tree + lca? anyone can
give a clear description of this solution? |
|
h*****1
发帖数: 74 | 17 第二题能写出N^2 的算法就可以了吧。至于那个N的算法，我觉得知道就可以了。要真
考那个Ukkonen的suffix tree 算法，那真是太疯狂了。 |
|
s*****y
发帖数: 897 | 18 同问，suffix tree和trie的要当场写吗？ |
|
g**e
发帖数: 6127 | 19 面试的人没几个知道suffix tree和trie的
某投行的一个哥们还问我两遍我trie是不是拼错了，应该是tree |
|
d*******l
发帖数: 338 | 20 suffix tree..
There's a class of counter example in this format:
A A .. A B A A .. A A
1 2 .. i-1 i i+1 i+2 .. 2i |
|
r******r
发帖数: 700 | 21 把 longestPrefixPalindrome(String test) 改进了一点，从后面往前面扫描，先找最
大的；如果找到，立即返回。complexity 降到了：
O（n-1/2）* O（n/2）average case.
这还算 O(n^2) 吧？ 再看看 suffix tree.
// ILLINOISURB
public static String longestPrefixPalindrome(String test){
for(int i=test.length()-1; i>=0; i--){
String maxPrefix = test.substring(0, i);
if( isCharPalindrome(maxPrefix) ){
return maxPrefix;
}
}
}
);
- |
|
g******0
发帖数: 221 | 22 We used this book for our class: Introduction to Algorithm by CLRS.
Is there any other books people use for preparing for job interviews? Or is
this enough?
What data structures/algorithms do we have to know for interviews? Here is a
list I compiled. linked list, stack, queue, array, heap, bst, quick sort,
merge sort, radix sort(?), insertion sort(?), DFS, BFS, Dijkstra's(?), max
flow/min cut(?), KMP(?), suffix tree(?).
(?) indicates the items which I don't know if is required.
Any suggestion to... 阅读全帖 |
|
g**e
发帖数: 6127 | 23 来自主题: JobHunting版 - 请教两个题 build suffix tree with constant longest common ancestor access. O(n)
build trie map |
|
g*****i
发帖数: 2162 | 24 longest common substring用suffix tree做似乎比dp好.
第四题mark previous node什么意思?我感觉和visited flag差别不大吧
machine
我说的遍历，通过visited flag防止重复。结果要求不能做visited flag，他给了提示
后，原来算是mark previous node，然后不往回走。事后想想认为这样子后面还是有可
能会转回原位置的说。 |
|
g******0
发帖数: 221 | 25 how to find the maximum palindrome in a string using suffix tree in O(n)
time?
xie xie! |
|
a*****a
发帖数: 46 | 26 没看明白，能详细解释下么？
是说Suffix tree能在O(1)时间找到含'~'和含'^'的子串的LCP么？那么对于 abceedba
这个例子，怎么发现ab不是呢？
谢谢！ |
|
|
a*********0
发帖数: 2727 | 28 i believe you should store prefix rather than suffix |
|
a*********0
发帖数: 2727 | 29 really? as far as i know, trie is a suffix tree without path collasping |
|
a*********0
发帖数: 2727 | 30 how about build a suffix tree and search every path starting with the next
char of *
match |
|
a*********0
发帖数: 2727 | 31 suffix tree is the tree of the input string, not the regular expression |
|
q*****9
发帖数: 85 | 32 找出一个字符串中最短的 并且是只出现过一次的一个子串， 这个答案是可以有多个的，
例子: bbbb 返回 bbbb
maaabccc 返回 m和b
baabba 返回 aa, bb, ab
这道题可以用suffix tree解决, O(n), O(n)，还有没有其他更subtle的方法？
毕竟为这一个功能建个后缀树有点夸张。
|
|
b*****n
发帖数: 760 | 33 1. You have a class that supports to input sample records and to compute the
average of the samples. The class has two members: total and count. How
would you make the class thread-safe? If 99% of the time average() is called
, how to optimize for that?
2. Talk about your recent interesting project/bug.
3. You have 100 files, each containing 10G sorted integers. How to merge all
integers into one sorted file?
4. Write a function to reverse digits of an integer. E.g. 123 --> 321, -890
--> -98.
5.... 阅读全帖 |
|
|
|
t**r
发帖数: 3428 | 36 还有，TRIE的 插入和查找都是 O(1) 我的理解多么 |
|
|
s*****y
发帖数: 897 | 38 How is the space complexity of the trie you create in the previous post:
求一道 面世题 的解答思路 |
|
i**********e
发帖数: 1145 | 39 The space complexity depend on how many words you insert into the trie, and
also the common prefixes they all shared. In addition, it also depends on
how you represent a trie node's children. For example, representing its
children as a linked list is more space efficient than an array of children
nodes.
In all cases, the trie is more efficient in terms of space and speed
compared to hash table for the purposes of checking prefixes of a string. |
|
s*****y
发帖数: 897 | 40 Ye. That is my question. Base on the input of that puzzle, it seems that the
trie will occupy a lot of memory as you create a tire for so many words in
a 1.6MB file.
I did not check carefully how similar are their prefix though.
and
children |
|
i**********e
发帖数: 1145 | 41 You don't need to create a trie that store all words.
If you're finding a rectangle of size mxn, you only need to store all words
of length m and length n only in the trie.
the
in |
|
s*****y
发帖数: 897 | 42 icic
I did not read your algorithm carefully.
Thanks.
words |
|
i**********e
发帖数: 1145 | 43 Here are some statistics on how much time and memory to create a trie with
all words in the dictionary:
Each node has 26 trie nodes. (children represented as an array)
Time: < 1sec, Memory: 45 MB
Each node has a pointer to the head of its children. (children represented
as linked list)
Time: < 1sec, Memory: 10 MB
the
in |
|
f*******t
发帖数: 7549 | 44 请问children是怎样存的？一个node可能有26种child，分别对应26个字母。用一个指
针存"head of its children"是什么意思？是用26个指针吗？那不是还是存了一个
array? |
|
|
i**********e
发帖数: 1145 | 46 1) array trie definition
struct Trie {
// pointer to its 26 children.
// children[i] == NULL means that particular child doesn't exist.
Trie *children[26];
bool end; // marker to indicate if current letter is end of a word.
};
2) linked list trie definition
struct Trie {
// pointer to its first child.
Trie *son;
// pointer to its sibling node.
Trie *next;
};
For 1) -- array trie definition, the insert(const char *s) function is easy
to write. For 2), is a little more tricky to writ... 阅读全帖 |
|
f*******t
发帖数: 7549 | 47 谢了。
看了前面某回帖，没想到用array存children也就一些指针，居然会多耗几倍的内存…… |
|
f*****i
发帖数: 835 | 48 先把10个字母以下单词对应该的number都找出来，做成multi_hash_map, key是number,
value是单词，
然后number的suffix tree里每一个对着hash_map查 |
|
P**********c
发帖数: 3417 | 49 是用suffix tree还是针对这个题目有更简单直观的解法？ |
|
k****n
发帖数: 369 | 50 太感谢了！
suffix tree，不过真的要白板编么？能不能写下阿
key is to reduce disk access
if it is possible to keep it in memory, then first bucket files with sizes,
then inside the bucket use (MD5 => file) hash map.
ob)
thread
have no idea，求布道
生成正方形uniform分布的点，丢弃圆外面的点
笛卡尔坐标系就麻烦多了，距圆心距离不同概率不同
Open question好多，我最讨厌这种，谁知道面试官prefer什么答案阿 |
|
