n******2
发帖数: 47 | 1 Bloomberg的这个问题答案是什么？
假设给你一个文件（可能很大），每行还有人名，和电话号码，设计数据结构使得给
出人名，迅速的查其电话号码。如果要支持给出first name查电话，给出last name查
电话号码呢？如果要在查询支持名字中含wild card呢？
pre-fix tree? bloomberg一般不会问这么难的算法题吧？ 那就得用三个hashtable
on full name, first name and last name? 似乎又不合适，而且也没办法处理wild
card。 |
p********7
发帖数: 549 | 2 我觉得这个是个开放性问题吧，没有固定答案的。我认为pre-fix tree不是很难的数据
结构啊，很常见的。
还有就是如果要支持用first name，last name和full name查，就是用pre-fix tree，
建立一个tree就能搞定了。
比如 paul cheng 8001001000
同时在一个树存paul 在'l'节点存 cheng 8001001000
也存cheng 在'g'节点存 paul 8001001000
也存paul cheng 在'g'存 8001001000
如果加了wild card，也能搞定。
你需要把可能的情况都考虑进去，虽然建立这个tree就需要很多memory了。
比如Paul 可能的wild card组合是p* p*aul p*ul p*l..... |
r**u
发帖数: 1567 | 3 build tree的时候不要考虑wild card吧. 不然tree可以无限增长啊. search的时候
match wild card好点.
【在 p********7 的大作中提到】
: 我觉得这个是个开放性问题吧，没有固定答案的。我认为pre-fix tree不是很难的数据
: 结构啊，很常见的。
: 还有就是如果要支持用first name，last name和full name查，就是用pre-fix tree，
: 建立一个tree就能搞定了。
: 比如 paul cheng 8001001000
: 同时在一个树存paul 在'l'节点存 cheng 8001001000
: 也存cheng 在'g'节点存 paul 8001001000
: 也存paul cheng 在'g'存 8001001000
: 如果加了wild card，也能搞定。
: 你需要把可能的情况都考虑进去，虽然建立这个tree就需要很多memory了。
|
