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.
相关阅读
现在面试还有人问java基础么？版友们能推荐个挂靠OPT的ICC?美特别募兵计划瞄准中国留学生 承诺可快速入籍 开启微信服务 ZT (转载)侯机厅一对让我恶心的老男女Level vs compensation 求offer建议求西雅图地区靠谱的opt挂靠和icc急死了！找工作遇到棘手问题？大家帮忙出出主意吧麻烦大家帮忙看一下求质数这段代码，求拍砖~收到opt ext.卡了,到期时间明年2月…问一道qualtric面经题狗的research&machine intelligence 大组是坑吗？请求用career fair on campus interview代替onsite是否合适？h1bdata.info 是不是好久没更新数据了以后谁要是面试被迂腐寒酸窝里斗的老中黑了 大可以将其名字，公司，职位公布在本版！！！刚跪的电面有人用过google voice 电面吗？求Twitter内推入门级问题，leetcode就是 leetcode.com吧用技术水平衡量人的二逼不得好死，被烙印干死Amazon入职两个月就被pip 求支招