美国华人网FuninUSA|唐人社区|北美华人论坛:找好货,找礼品卡,找折扣,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • TNT确定《末日孤舰》第四季首播日期
  • 《权力的游戏》倒数第二季发布夜王动态海报
  • NBC取消《芝加哥正义》,全家桶第四子止步第一季
  • 2000年前首台天文计算机复原:精密度惊人
  • 科学家声称收到外星来电:宇宙中已走60亿光年
  • 蛟龙号从地球最深处带回“深海居民”:如外星怪物
  • 4分钟科普围棋规则:瞬间懂了
  • 大学生7楼钓外卖 宿管阿姨手书警告看哭
  • 飞机头突然断掉:其实 金属也会累
  • 谷歌自主处理器TPU太猛:AlphaGo只用一颗便完虐人类
  • 被美国收养的子女不能为亲属办绿卡
  • 多点开花 AMD快hold不住它的洪荒之力了
  • 6个月高位:强劲数据、强硬言论助力欧元
  • 化敌为友,诺基亚“牵手”苹果探索健康业务
  • 美元大跌——成也特朗普,败也特朗普
  • 小瞧高通! 你可就错了
  • 焦点:特朗普"2018预算案"周二首秀
  • 黄金十字:逆势扭转,贵金属是要翻身了啊!
  • IBM:这个蓝色巨人正在老去?
  • 警告:小心债券市场带来寒意
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3025|回复: 8

内推面经 -问一个数据结构的问题- 唐人社区|北美华人论坛

[复制链接]

21

主题

406

帖子

442

积分

中级会员

Rank: 3Rank: 3

积分
442
QQ
发表于 2016-10-4 23:08:14 | 显示全部楼层 |阅读模式
分享到:
{$content}

唐人社区-北美华人论坛-内推面经版-问一个数据结构的问题


  JobHunting
标 题: 问一个数据结构的问题


哪种数据结构search最高效?
我觉得是binary search tree,因为如果是balanced BST,O(lgN)的复杂度就能找到一
个element

哪种数据结构sort最高效?
这个我就不知道怎么答了,只听过哪种algorithm,没听过哪种数据结构的。基本上
sort一组数据,最快也得要O(NlgN)吧,用quick sort或者merge sort的话。但这几种
algorithm都能针对各种不止一种data structure吧,比如 Array, ArrayList,
linkedlist

求大神指点
--

回复 百度谷歌雅虎搜狗搜搜有道360奇虎

举报

28

主题

98

帖子

161

积分

注册会员

Rank: 2

积分
161
QQ
发表于 2016-10-5 00:45:22 | 显示全部楼层
JobHunting
标  题: Re: 问一个数据结构的问题


hashset就够了吧,也是O(1)

【 在 beetle1986 (beetle) 的大作中提到: 】
: search最高效的是hash table, O(1)



--

11

主题

231

帖子

230

积分

注册会员

Rank: 2

积分
230
QQ
发表于 2016-10-5 01:40:56 | 显示全部楼层
JobHunting
标  题: Re: 问一个数据结构的问题


你这个完全得看application啊
time vs space tradeoff

search一般来说当然binary search是不错的
但hashset能搞出O(1)来,如果hash function很好的话

sort也要看要求啊
哪怕是algorithm,一般NlogN,但是mergesort和quicksort都有不同的应用
整数的话,甚至可以radix sort搞出O(N)
扯上结构的话,linkedlist就经常不是很好用,因为没有O(1) random access
那arraylist也许会比较方便
或者直接上heap

我觉得这种问题就是看你的理解深度,我不认为能简单一个回答解决,而应该看实际的
tradeoff


【 在 laoqiu (老Q) 的大作中提到: 】
: 哪种数据结构search最高效?
: 我觉得是binary search tree,因为如果是balanced BST,O(lgN)的复杂度就能找到一
: 个element
: 哪种数据结构sort最高效?
: 这个我就不知道怎么答了,只听过哪种algorithm,没听过哪种数据结构的。基本上
: sort一组数据,最快也得要O(NlgN)吧,用quick sort或者merge sort的话。但这几种
: algorithm都能针对各种不止一种data structure吧,比如 array, ArrayList,
: linkedlist
: 求大神指点




--

17

主题

97

帖子

135

积分

注册会员

Rank: 2

积分
135
QQ
发表于 2016-10-5 01:44:41 | 显示全部楼层
JobHunting
标  题: Re: 问一个数据结构的问题


我也觉得这问题没有一个统一答案。但如果非要选一个,是不是array就是最好的答案
了,因为几乎什么sort algorithm都能在array上很好的实现啊。当然,我觉得这其实
只是说明array只是最common的data structure而已。。


【 在 sapphirewing (Audrey的树) 的大作中提到: 】
: 你这个完全得看application啊
: time vs space tradeoff
: search一般来说当然binary search是不错的
: 但hashset能搞出O(1)来,如果hash function很好的话
: sort也要看要求啊
: 哪怕是algorithm,一般NlogN,但是mergesort和quicksort都有不同的应用
: 整数的话,甚至可以radix sort搞出O(N)
: 扯上结构的话,linkedlist就经常不是很好用,因为没有O(1) random access
: 那arraylist也许会比较方便
: 或者直接上heap
: ...................



--

18

主题

90

帖子

135

积分

注册会员

Rank: 2

积分
135
QQ
发表于 2016-10-5 02:41:46 | 显示全部楼层
JobHunting
标  题: 问一个数据结构的问题


哪种数据结构search最高效?
我觉得是binary search tree,因为如果是balanced BST,O(lgN)的复杂度就能找到一
个element

哪种数据结构sort最高效?
这个我就不知道怎么答了,只听过哪种algorithm,没听过哪种数据结构的。基本上
sort一组数据,最快也得要O(NlgN)吧,用quick sort或者merge sort的话。但这几种
algorithm都能针对各种不止一种data structure吧,比如 array, ArrayList,
linkedlist

求大神指点
--

32

主题

120

帖子

185

积分

注册会员

Rank: 2

积分
185
QQ
发表于 2016-10-5 02:55:18 | 显示全部楼层
JobHunting
标  题: Re: 问一个数据结构的问题


search最高效的是hash table, O(1)


--

25

主题

78

帖子

130

积分

注册会员

Rank: 2

积分
130
QQ
发表于 2016-10-5 04:08:23 | 显示全部楼层
JobHunting
标  题: Re: 问一个数据结构的问题


非要选的话 我选search: hashtable
sort: heap or BST

【 在 laoqiu (老Q) 的大作中提到: 】
: 我也觉得这问题没有一个统一答案。但如果非要选一个,是不是array就是最好的答案
: 了,因为几乎什么sort algorithm都能在array上很好的实现啊。当然,我觉得这其实
: 只是说明array只是最common的data structure而已。。



--
Look. If you had one shot or one opportunity to seize everything you ever wanted in one moment.
Would you capture it or just let it slip?

34

主题

1219

帖子

2432

积分

金牌会员

Rank: 6Rank: 6

积分
2432
QQ
发表于 2016-10-26 07:41:53 | 显示全部楼层
这么强,支持楼主,佩服

23

主题

1177

帖子

2358

积分

金牌会员

Rank: 6Rank: 6

积分
2358
QQ
发表于 2016-10-29 22:22:11 | 显示全部楼层
介是神马?!!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

美国华人网|唐人社区|什么值得买FunInUSA.net发布的内推面经 -问一个数据结构的问题- 唐人社区|北美华人论坛帖子由网友提供或转载于网络,若发布的内推面经 -问一个数据结构的问题- 唐人社区|北美华人论坛侵犯了您的权益,请联系我们.
Sasa.com

Copyright ©2011 FunInUSA.NET All Right Reserved.  Powered by Discuz! X3.0 小黑屋

本站信息均由会员发表,不代表美国华人网FunInUSA|唐人社区的立场,如侵犯了您的权利请发帖投诉  技术支持: 美国华人网FunInUSA|唐人社区

安全联盟认证 安全联盟认证

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