h*****g
发帖数: 312 | 1 一个application， 比如gmail，你type in name in the address，“J－A－C－K
”，你每type 一个字母， pop出来的email address都会update。比如type J的时候出
来Jack，Jay，John，Jon；type A的时候就只有Jack和Jay了，再type C就只有Jack。
问如何organize这个？
我知道用trie可以，但要用hashtable 得咋做？
例如，开始把 Jay, John,JACK等都hash 上去了之后，当你type: J的时候，怎么去
hashtable里找以J开头的呢？ 当type：Ja呢？如何去找以Ja开头的呢？ | c****p
发帖数: 6474 | 2 多层链表/hash表？
【在 h*****g 的大作中提到】
: 一个application， 比如gmail，你type in name in the address，“J－A－C－K
: ”，你每type 一个字母， pop出来的email address都会update。比如type J的时候出
: 来Jack，Jay，John，Jon；type A的时候就只有Jack和Jay了，再type C就只有Jack。
: 问如何organize这个？
: 我知道用trie可以，但要用hashtable 得咋做？
: 例如，开始把 Jay, John,JACK等都hash 上去了之后，当你type: J的时候，怎么去
: hashtable里找以J开头的呢？ 当type：Ja呢？如何去找以Ja开头的呢？
| i**********e
发帖数: 1145 | 3 用 hashtable 的话直接 hash Jay,John, JACK to "j", Jay and Jack to "ja"，
John to “jo"，以此类推。。。（在 C++ 这个叫 hash_multimap，一个 key 可以有
多个对应的 values）
输入 "J" 的时候就直接做 hashtable lookup for key "j"，"Ja" 的时候就 lookup
key "ja" 就好了。
用 hashtable 其实类似于用 n-ary tree（也就是 prefix tree/trie），每个 node
有 26 个孩子 ("a-z")。hashtable 的坏处是每次 lookup 都要用 hash function 来
计算，而且还可能有冲突而导致效率更慢。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
