Amazon常见设计题——设计电话簿求解 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Amazon常见设计题——设计电话簿求解

Amazon常见设计题——设计电话簿求解# JobHunting - 待字闺中

S*C2015-03-27 07:03

1 楼

一道Amazon常见设计题，其他公司也考过
设计个电话本, 可以用那些数据结构？
Design a phone book application. He was mainly looking for the data
structure. Follow up question was to write a code to insert data into a trie!
要求是可以根据人名字找到他的电话号码，根据电话号码可以找到人名字，一个人名字
下，可以有好几个号码，但是一个号码只对应一个人
我的解法：用trie储存所有人名String，trie node中有一个List类型的成员
变量来储存这个人的电话号码，这个解法是不是最优的？如果不是最优又该怎么做呢？

S*C2015-03-27 07:03

2 楼

我的这种解法只能用姓名快速查询到电话号码，而不能用电话号码快速查询姓名，后者
需要把电话号码最为key，把姓名作为value存在HashMap中吧？

s*72015-03-27 07:03

3 楼

电话薄这种几百几千，用个链表就可以了

b*52015-03-27 07:03

4 楼

1）为什么我看到这种题，大家都用trie，为什么没人用hashmap？把人名hash 为
key，为value?
2) to do the reverse lookup, phone number -> name, the total possible number
of combination就是10^10, so why not just use an array?
or u can use a hashmap of , as name->id
and then to reverse lookup, u can use an integer array
to store one's phone numbers, u can use hashMapnumber>

【在 S*******C 的大作中提到】

: 我的这种解法只能用姓名快速查询到电话号码，而不能用电话号码快速查询姓名，后者
: 需要把电话号码最为key，把姓名作为value存在HashMap中吧？

S*C2015-03-27 07:03

5 楼

用linkedlist查询速度太慢

【在 s******7 的大作中提到】

: 电话薄这种几百几千，用个链表就可以了

S*C2015-03-27 07:03

6 楼

1）用hashmap为什么没trie好，是因为大量相似的String作为key浪费大量空间，比如
Jessica和Jessie中很多字母"Jessi"都重复，用trie就不会有重复。
2)int array原则上是可以的，但只能在你有数亿的号码时用才比较好，这样要用10^10
的空间，如果只有几千的号码的话还是hashmap比较好

number

【在 b**********5 的大作中提到】

: 1）为什么我看到这种题，大家都用trie，为什么没人用hashmap？把人名hash 为
: key，为value?
: 2) to do the reverse lookup, phone number -> name, the total possible number
: of combination就是10^10, so why not just use an array?
: or u can use a hashmap of , as name->id
: and then to reverse lookup, u can use an integer array
: to store one's phone numbers, u can use hashMap: number>