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 的大作中提到】
: 今天三星面试遇到一个设计题，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 的大作中提到】
: 电话簿的显示一般有字典排序的要求，所以用bst来存储就可以了，不过用trie确实用
: 的memory较少一些
:
: with
|
c****f
发帖数: 28 | 5 嗯，面试官就是说trie memory消耗太多，问可不可以改进？
【在 l*****a 的大作中提到】
: trie的一个功能是输入前一部分字符，可以推荐可能的单词
: 问题是需要每个node hold一个list of string吧，这样的话是不是memory用的很多？
|
T*****g
发帖数: 8 | |
c****f
发帖数: 28 | |
w*******e
发帖数: 395 | 8 bit map?
with
【在 c****f 的大作中提到】
: 今天三星面试遇到一个设计题，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 的大作中提到】
: 今天三星面试遇到一个设计题，how to design a phone book on mobile phone (with
: minimum memory usage)? 除了trie, 可不可以改进减少RAM消耗?
|
A*********c
发帖数: 430 | 10 这个和原题需求不一样。
电话号码本主要是存名字，然后支持快速插入，删除，前缀查询等
这个stack overflow的题目是光存号码。
【在 c****f 的大作中提到】
: 我查了下，可能他想要的答案是这个：
: http://stackoverflow.com/questions/7685649/most-efficient-way-t
|
z****8
发帖数: 7 | 11 能不能先sort电话号码，然后在压缩，不直接存电话号码，而是存电话号码相对上一条
的偏移量 |
