c****f 发帖数: 28 | 1 今天三星面试遇到一个设计题,how to design a phone book on mobile phone (with
minimum memory usage)? 除了trie, 可不可以改进减少RAM消耗? |
x*******z 发帖数: 31 | 2 同被问了这一道题。面试官提示regular expression. 但我不知道这道题怎么和正则表
达式联系起来。。。 |
q****m 发帖数: 177 | 3 电话簿的显示一般有字典排序的要求,所以用bst来存储就可以了,不过用trie确实用
的memory较少一些
with
【在 c****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天三星面试遇到一个设计题,how to design a phone book on mobile phone (with : minimum memory usage)? 除了trie, 可不可以改进减少RAM消耗?
|
l*****a 发帖数: 14598 | 4 trie的一个功能是输入前一部分字符,可以推荐可能的单词
问题是需要每个node hold一个list of string吧,这样的话是不是memory用的很多?
【在 q****m 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 电话簿的显示一般有字典排序的要求,所以用bst来存储就可以了,不过用trie确实用 : 的memory较少一些 : : with
|
c****f 发帖数: 28 | 5 嗯,面试官就是说trie memory消耗太多,问可不可以改进?
【在 l*****a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : trie的一个功能是输入前一部分字符,可以推荐可能的单词 : 问题是需要每个node hold一个list of string吧,这样的话是不是memory用的很多?
|
T*****g 发帖数: 8 | |
c****f 发帖数: 28 | |
w*******e 发帖数: 395 | 8 bit map?
with
【在 c****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天三星面试遇到一个设计题,how to design a phone book on mobile phone (with : minimum memory usage)? 除了trie, 可不可以改进减少RAM消耗?
|
A*********c 发帖数: 430 | 9 trie, compressed trie, tenary tree.
with
【在 c****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 今天三星面试遇到一个设计题,how to design a phone book on mobile phone (with : minimum memory usage)? 除了trie, 可不可以改进减少RAM消耗?
|
A*********c 发帖数: 430 | 10 这个和原题需求不一样。
电话号码本主要是存名字,然后支持快速插入,删除,前缀查询等
这个stack overflow的题目是光存号码。
【在 c****f 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我查了下,可能他想要的答案是这个: : http://stackoverflow.com/questions/7685649/most-efficient-way-t
|
z****8 发帖数: 7 | 11 能不能先sort电话号码,然后在压缩,不直接存电话号码,而是存电话号码相对上一条
的偏移量 |