t*r
2 楼
还有,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
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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
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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 请问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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 请问children是怎样存的?一个node可能有26种child,分别对应26个字母。用一个指
: 针存"head of its children"是什么意思?是用26个指针吗?那不是还是存了一个
: array?
f*t
15 楼
谢了。
看了前面某回帖,没想到用array存children也就一些指针,居然会多耗几倍的内存……
【在 i**********e 的大作中提到】![](/moin_static193/solenoid/img/up.png)
: 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 的大作中提到】
![](/moin_static193/solenoid/img/up.png)
: 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.
相关阅读
赞被AMAZON速据,少量面经请问phone interview该怎么选时间?求教, H1还是L1Getco刚被Epic onsite之后给拒了,个人一点感想。。感觉EE在湾区普遍比CS同等学历base要低个10-20%OPT submit 的时候是December 6 是不是太晚了?Test Engineer/Lead needed in Boise, IDPIE题: Phone number to words iterative 解法[合集] 这年头 怎么都往CS里头跳?qualcomm 新鲜电面面经非常勿扰 美国西海岸专场开播了,一共四期关于leetcode上的一道题Bloomberg家面intern也要onsite了啊?关于面经的讨论-在统计版急问:OPT开始工作的话需要向ISS报告吗怎么找国内的工作?化学方面的猎头?在县政府的IT部门码工好么?这次真看走眼了[ Job Opening] ebay QA Engineer