t*r
2 楼
还有，TRIE的 插入和查找都是 O(1) 我的理解多么
i*e
3 楼
Trie 的插入和查找是 O(N), N = 字符串的长度。
Trie 是 prefix tree 的简称。
网上有很多关于 trie 的教程，相信你可以很快就掌握。
至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
【在 t**r 的大作中提到】
: 还有，TRIE的 插入和查找都是 O(1) 我的理解多么
Trie 是 prefix tree 的简称。
网上有很多关于 trie 的教程，相信你可以很快就掌握。
至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
【在 t**r 的大作中提到】
: 还有，TRIE的 插入和查找都是 O(1) 我的理解多么
i*e
4 楼
Trie 的应用挺强大的，例如 auto complete (suggestion)，boggle 游戏的优化，还
有这个 word rectangle 这个 puzzle 题：
http://www.mitbbs.com/article_t/JobHunting/31916637.html
有这个 word rectangle 这个 puzzle 题：
http://www.mitbbs.com/article_t/JobHunting/31916637.html
s*y
5 楼
How is the space complexity of the trie you create in the previous post:
求一道 面世题 的解答思路
【在 i**********e 的大作中提到】
: Trie 的插入和查找是 O(N), N = 字符串的长度。
: Trie 是 prefix tree 的简称。
: 网上有很多关于 trie 的教程，相信你可以很快就掌握。
: 至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
求一道 面世题 的解答思路
【在 i**********e 的大作中提到】
: Trie 的插入和查找是 O(N), N = 字符串的长度。
: Trie 是 prefix tree 的简称。
: 网上有很多关于 trie 的教程，相信你可以很快就掌握。
: 至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
i*e
6 楼
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 的大作中提到】
: How is the space complexity of the trie you create in the previous post:
: 求一道 面世题 的解答思路
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 的大作中提到】
: How is the space complexity of the trie you create in the previous post:
: 求一道 面世题 的解答思路
s*y
7 楼
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 的大作中提到】
: 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.
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 的大作中提到】
: 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.
i*e
8 楼
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 的大作中提到】
: 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
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 的大作中提到】
: 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
s*y
9 楼
icic
I did not read your algorithm carefully.
Thanks.
words
【在 i**********e 的大作中提到】
: 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
I did not read your algorithm carefully.
Thanks.
words
【在 i**********e 的大作中提到】
: 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
i*e
10 楼
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
【在 s*****y 的大作中提到】
: 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
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
【在 s*****y 的大作中提到】
: 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
f*t
11 楼
请问children是怎样存的？一个node可能有26种child，分别对应26个字母。用一个指
针存"head of its children"是什么意思？是用26个指针吗？那不是还是存了一个
array?
【在 i**********e 的大作中提到】
: 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
针存"head of its children"是什么意思？是用26个指针吗？那不是还是存了一个
array?
【在 i**********e 的大作中提到】
: 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
h*8
12 楼
mark一下，学习
i*e
13 楼
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 write a non-recursive insert()
function. You can choose to insert in a way such that its children are
always sorted in order. If it's sorted, it's faster to search, but still
take at worst 26 iteration. Use a bitmap (a 32-bit integer) can overcome
this shortcoming.
【在 f*******t 的大作中提到】
: 请问children是怎样存的？一个node可能有26种child，分别对应26个字母。用一个指
: 针存"head of its children"是什么意思？是用26个指针吗？那不是还是存了一个
: array?
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 write a non-recursive insert()
function. You can choose to insert in a way such that its children are
always sorted in order. If it's sorted, it's faster to search, but still
take at worst 26 iteration. Use a bitmap (a 32-bit integer) can overcome
this shortcoming.
【在 f*******t 的大作中提到】
: 请问children是怎样存的？一个node可能有26种child，分别对应26个字母。用一个指
: 针存"head of its children"是什么意思？是用26个指针吗？那不是还是存了一个
: array?
g*y
14 楼
实现简单的suffix tree build还是很容易的，你可以告诉面试官，Ukkonen 95年做了
个O(n)的，现在你让兄弟写，那是没戏，但我可以给你查出来。
【在 i**********e 的大作中提到】
: Trie 的插入和查找是 O(N), N = 字符串的长度。
: Trie 是 prefix tree 的简称。
: 网上有很多关于 trie 的教程，相信你可以很快就掌握。
: 至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
个O(n)的，现在你让兄弟写，那是没戏，但我可以给你查出来。
【在 i**********e 的大作中提到】
: Trie 的插入和查找是 O(N), N = 字符串的长度。
: Trie 是 prefix tree 的简称。
: 网上有很多关于 trie 的教程，相信你可以很快就掌握。
: 至于 suffix tree 就比较复杂，面试一般都不太问。至少不会变态到叫你写代码。
f*t
15 楼
谢了。
看了前面某回帖，没想到用array存children也就一些指针，居然会多耗几倍的内存……
【在 i**********e 的大作中提到】
: 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.
看了前面某回帖，没想到用array存children也就一些指针，居然会多耗几倍的内存……
【在 i**********e 的大作中提到】
: 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.
相关阅读
现在申OPT 请问多久能批下来保险LCA 今天还没file,是不是不赶趟了，求blessLife Technologies 这个公司怎么样？做题更有压力了一道题请问大家recruiting incentive是啥[H1B] 现在开始电面， 然后onsite， 还能赶上今年的H1B吗？BB是那家公司？大家看看这样做合适不合适H1B receipt收到，算占名额了吗？统计真是个low pay 的行业啊问下professional references (for after the interview)没有咋办？H1B换工作期间回国Seeking a couple of Java developers for Google Mountain ViOPT extension非典型面试题微软401k给MATCH多少？还没有LCA，催HR, 还来得及申请h1b吗大家觉得我应该找什么工作？