m******9 发帖数: 968 | 1 为一个城市人口设计电话簿的数据结构。
要求就是:
如果输入phone num,比如输入800-111-XXXX, 就要把所有的 电话号码以800-111开头
的name都找出来
另外如果输入name,比如输入john,则要返回所有的first name等于john的电话号码。
我知道的办法就是建立2个trie:为phone num建立一个trie,为name再建立一个trie
大家知道这个题目的比较好的答案吗?谢谢 |
m******9 发帖数: 968 | |
g******i 发帖数: 354 | 3 If I am asked this question in interview, my immediate answer will be:
1) Build two HashMap
2) HashMap1 key is phone number, value is Arraylist to store all the name
with that phone number;
3) HashMap2 key is first name, value is ArrayList to store all the phone
number with that first Name.
【在 m******9 的大作中提到】 : 为一个城市人口设计电话簿的数据结构。 : 要求就是: : 如果输入phone num,比如输入800-111-XXXX, 就要把所有的 电话号码以800-111开头 : 的name都找出来 : 另外如果输入name,比如输入john,则要返回所有的first name等于john的电话号码。 : 我知道的办法就是建立2个trie:为phone num建立一个trie,为name再建立一个trie : 大家知道这个题目的比较好的答案吗?谢谢
|
t******e 发帖数: 1293 | 4 我觉得,从号码插名字,用B+树,每个节点都是10路的。因为电话号码的长度顶多是10
位。
从名字查号码,用trie。用B+树也可以,不过,如果碰到名字比较长的就慢了,而且
trie
还可以压缩表示。
【在 m******9 的大作中提到】 : 为一个城市人口设计电话簿的数据结构。 : 要求就是: : 如果输入phone num,比如输入800-111-XXXX, 就要把所有的 电话号码以800-111开头 : 的name都找出来 : 另外如果输入name,比如输入john,则要返回所有的first name等于john的电话号码。 : 我知道的办法就是建立2个trie:为phone num建立一个trie,为name再建立一个trie : 大家知道这个题目的比较好的答案吗?谢谢
|
m******9 发帖数: 968 | 5 你这个有些问题,如果我只查询号码的一部分,比如800-111-2222,我只查询800-111
,hashmap1就不行了。
另外hashmap2的问题是,不一定就是按照first name查询的,也可能按照last name查
询,
【在 g******i 的大作中提到】 : If I am asked this question in interview, my immediate answer will be: : 1) Build two HashMap : 2) HashMap1 key is phone number, value is Arraylist to store all the name : with that phone number; : 3) HashMap2 key is first name, value is ArrayList to store all the phone : number with that first Name.
|
s*****i 发帖数: 355 | 6 都用trie不好吗
10
【在 t******e 的大作中提到】 : 我觉得,从号码插名字,用B+树,每个节点都是10路的。因为电话号码的长度顶多是10 : 位。 : 从名字查号码,用trie。用B+树也可以,不过,如果碰到名字比较长的就慢了,而且 : trie : 还可以压缩表示。
|
g******i 发帖数: 354 | 7 你说的太对了。
我的设计是错的。
有没有正解呢?
111
【在 m******9 的大作中提到】 : 你这个有些问题,如果我只查询号码的一部分,比如800-111-2222,我只查询800-111 : ,hashmap1就不行了。 : 另外hashmap2的问题是,不一定就是按照first name查询的,也可能按照last name查 : 询,
|