S*******C
发帖数: 822 | 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*******C
发帖数: 822 | 2 我的这种解法只能用姓名快速查询到电话号码，而不能用电话号码快速查询姓名，后者
需要把电话号码最为key，把姓名作为value存在HashMap中吧？ | s******7
发帖数: 1758 | | b**********5
发帖数: 7881 | 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 hashMap
number>
【在 S*******C 的大作中提到】
: 我的这种解法只能用姓名快速查询到电话号码，而不能用电话号码快速查询姓名，后者
: 需要把电话号码最为key，把姓名作为value存在HashMap中吧？
| S*******C
发帖数: 822 | 5 用linkedlist查询速度太慢
【在 s******7 的大作中提到】
: 电话薄这种几百几千，用个链表就可以了
| S*******C
发帖数: 822 | 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>
|
|
