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

 找回密码
 立即注册
  • 否认完南京大屠杀又抨击犹太人 APA这是要撕全世界?
  • 中国发起“厕所革命”:各国管理洗手间方式大不同
  • 宋小宝龙凤胎曝光!颜值竟然这么高
  • 于正谈"袁姗姗滚出娱圈":自己经历过的一件大事
  • 上海戏剧学院艺考进入三试阶段 林妙可初试就落榜
  • 有点乱 张俪男友朱镇模自曝曾被章子怡暗恋
  • 美媒:美海关严查持F1签证者 多名中国留学生被遣返
  • 日媒:特朗普在贸易层面上点名批评中日 有何目的?
  • 美媒:特朗普欲将工厂搬回美 是否影响中方战略?
  • 揭秘中国生物安全实验室:研究世上最危险病原体
  • Ryzen将发布,AMD股价有望从10美元增长到25美元
  • Facebook股价创历史新高
  • 美联储加息与否将给市场带来影响
  • 市场虽有下行风险,但不建议脱离股市
Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
搜索
查看: 3017|回复: 8

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

[复制链接]

21

主题

403

帖子

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

帖子

160

积分

注册会员

Rank: 2

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


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

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



--

11

主题

219

帖子

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

主题

94

帖子

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

主题

86

帖子

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

求大神指点
--

30

主题

112

帖子

173

积分

注册会员

Rank: 2

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


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


--

25

主题

75

帖子

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

主题

1154

帖子

2303

积分

金牌会员

Rank: 6Rank: 6

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

22

主题

1122

帖子

2244

积分

金牌会员

Rank: 6Rank: 6

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

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

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