美国华人网FuninUSA_唐人社区_北美华人论坛:找礼品卡,找折扣,找报价,找工作,找内推,找项目,找股票

 找回密码
 立即注册
  • 男生“换心”后秒变学霸!这才是真相
  • 18万元!日本无印良品推9平单间小屋:海边山脚都能建
  • 大疆发飙!举报干扰成都机场无人机奖100万
  • 把猫头鹰羽毛一撩 网友惊呼:竟是大长腿
  • 夸张!科学家揭开人类大秘密:《魔戒》小矮人成真
  • 捡回一条命!男子深海垂钓巨大鲨鱼上钩:结果意外
  • 胖子有救!利用大脑电磁刺激技术进行减肥:效果不错
  • 男子和机器人手臂玩刀戳手指缝:这结果没想到
  • 催眠是真的吗?其实 你被骗很多年了!
  • 担任戛纳主竞赛评委 范冰冰:深感荣幸 很有压力
  • 特朗普的狂想——不切实际的公司税计划
  • AMD:增长和损失同在,有改变才会有进步
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
  • Tom Lee警示下行风险,揭示市场三大“地雷”
  • 在Buffalo Wild Wings季度财报中出现了“天文误差”
  • 巴菲特该高兴了,IBM加息至每股1.5美元
  • 好消息!纳斯达克指数首破6000点,道指和纳指涨势喜人
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3022|回复: 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

求大神指点
--

新浪微博官方账号】美国华人网FunInUSA : 每日滚动更新美国商业投资就业招聘留学移民资讯。
回复 百度谷歌雅虎搜狗搜搜有道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

主题

226

帖子

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

主题

96

帖子

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
: ...................



--

17

主题

88

帖子

130

积分

注册会员

Rank: 2

积分
130
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

求大神指点
--

31

主题

116

帖子

178

积分

注册会员

Rank: 2

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


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


--

25

主题

76

帖子

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?

35

主题

1201

帖子

2394

积分

金牌会员

Rank: 6Rank: 6

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

22

主题

1166

帖子

2332

积分

金牌会员

Rank: 6Rank: 6

积分
2332
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|唐人社区

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

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