谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货

最近看过此主题的会员

H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 3270|回复: 18
收起左侧

[算法题] 关于电话本存储的数据结构

[复制链接] |试试Instant~ |关注本帖
我的人缘0
sherry900105 发表于 2015-1-15 11:37:09 | 显示全部楼层 |阅读模式
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
我记得去年上数据结构课的时候捞印老师说过数据库的主要数据结构是字典树和Hashmap来着。。如果没记错的话。。= =

然后这两天刷题看到了一道题是问电话本应该用什么数据结构存储,然后好多小伙伴答是用Hashmap存。具体这道题有没有其他的附加条件不知道,如果仅仅是问一个小的电话本存储应该就是Hashmap来着~

然后我的问题是:如果电话本用Trie存储的话,缺点是不是仅仅只有空间复杂度比较大啊?或者有没有小伙伴给还原一下原题。。就是Bloomberg他家的面经中的一道题。。总觉得不应该是这么简单的问题噗。。

谢谢各路大神们~~~看到我看到我看到我~~~~

评分

参与人数 1大米 +3 收起 理由
yabay91 + 3 感谢分享!

查看全部评分


上一篇:新人刷Leetcode求组队!
下一篇:Reorder List求大神debug,实在不知道错在哪里
我的人缘0
圆梦梦剧场 发表于 2015-1-15 23:30:04 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
sherry900105 发表于 2015-1-15 22:58
唔。。为啥我感觉hashmap的空间复杂度是O(n),trie的best case是O(log(m*n)) worst case 是O(m*n)。。。 ...

n是单词个数?m是单词平均长度?
那hashmap也应该是O(mn)吧?你不能对trie用character来统计,但是对hashmap用string来算
回复 支持 1 反对 0

使用道具 举报

全球28万学生4.7分推荐
我的人缘0
yabay91 发表于 2015-1-15 11:45:54 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
同问。。。觉得应该是trie。。。。求各位大大给个解答
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-15 12:11:40 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
yabay91 发表于 2015-1-15 11:45
同问。。。觉得应该是trie。。。。求各位大大给个解答

看到的所有答案都是hashmap呢。。其实我觉得貌似两个都可以 只是哪个好的问题吧==
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2015-1-15 14:11:49 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-15 22:25:54 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Adeath 发表于 2015-1-15 14:11
BST  参见
http://www.programmerinterview.com/index.php/data-structures/hash-tables-versus-binary-se ...

喂喂。。不是BST啦。。是Trie啦。。= =又见你。。
回复 支持 反对

使用道具 举报

我的人缘0
圆梦梦剧场 发表于 2015-1-15 22:29:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
为什么我觉得trie的空间复杂度比hashmap低。。
回复 支持 反对

使用道具 举报

我的人缘0
mayingjie116 发表于 2015-1-15 22:51:52 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
用Trie吧,还可以扩展一个字符串补全功能
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-15 22:53:58 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
mayingjie116 发表于 2015-1-15 22:51
用Trie吧,还可以扩展一个字符串补全功能

0 0 可是地里一水的Hashmap。。。我也不知道为啥了。。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-15 22:58:28 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
圆梦梦剧场 发表于 2015-1-15 22:29
为什么我觉得trie的空间复杂度比hashmap低。。

唔。。为啥我感觉hashmap的空间复杂度是O(n),trie的best case是O(log(m*n)) worst case 是O(m*n)。。。怎么看都是hashmap优于Trie吧。。
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2015-1-16 01:44:15 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
sherry900105 发表于 2015-1-15 22:25
喂喂。。不是BST啦。。是Trie啦。。= =又见你。。

你没仔细看 这篇文章就是讲电话本的数据结构的  
回复 支持 反对

使用道具 举报

我的人缘0
zcy1848 发表于 2015-1-16 01:46:48 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
觉得是Trie, 从空间复杂度的角度来说,trie可以省略存储重复字符,复杂度应该更小才对。还有更重要的一个问题是电话本要实现排序,用hashmap来存的话每次都都要排序,太浪费时间了吧。还有就是电话本的一个功能是输入几个字母,比如"t",可以显示以它打头的人名"tim", "tom",trie也可以实现这个功能。所以觉得还是trie更合适些
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-16 05:33:54 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
zcy1848 发表于 2015-1-16 01:46
觉得是Trie, 从空间复杂度的角度来说,trie可以省略存储重复字符,复杂度应该更小才对。还有更重要的一个问 ...

唔。。。谢谢回复啊!你这么一说貌似也对。。我只是记得当时老师讲的时候说Trie的空间复杂度要高一些来着。。。
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-16 05:35:25 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Adeath 发表于 2015-1-16 01:44
你没仔细看 这篇文章就是讲电话本的数据结构的

唔。。不好意思啊。。明天面试了。。所以急着赶着的一直在刷面经。。一会儿仔细看看~看到你说拿到Epic的offer了?你是什么时候毕业的啊?
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2015-1-16 07:06:36 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
sherry900105 发表于 2015-1-16 05:35
唔。。不好意思啊。。明天面试了。。所以急着赶着的一直在刷面经。。一会儿仔细看看~看到你说拿到Epic的o ...

嗯  对电话本来讲hashmap最大的缺点就是unsorted  
下周答辩  就毕业了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-16 10:03:02 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Adeath 发表于 2015-1-16 07:06
嗯  对电话本来讲hashmap最大的缺点就是unsorted  
下周答辩  就毕业了

那你找工作好快啊。。。我才刚开始一个多月。。还没有密集找呢。。不过你怎么这个时候毕业?是Phd?
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2015-1-16 11:08:40 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
sherry900105 发表于 2015-1-16 10:03
那你找工作好快啊。。。我才刚开始一个多月。。还没有密集找呢。。不过你怎么这个时候毕业?是Phd?

嗯算比较快的 主要也是时间紧迫 不快不行啊…  我是春季入学的  1月来的  硕士
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| sherry900105 发表于 2015-1-16 11:50:07 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
Adeath 发表于 2015-1-16 11:08
嗯算比较快的 主要也是时间紧迫 不快不行啊…  我是春季入学的  1月来的  硕士

唔。。1月入学。。不是已经应该毕业了么。。所以觉得你是Phd。。= =
回复 支持 反对

使用道具 举报

我的人缘0
Adeath 发表于 2015-1-16 12:14:45 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
sherry900105 发表于 2015-1-16 11:50
唔。。1月入学。。不是已经应该毕业了么。。所以觉得你是Phd。。= =

噢  我是那种做论文的硕士  课是早就上完了  论文稍微拖了一下  晚了一个月
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html






手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-25 12:13

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表