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

 找回密码
 立即注册
  • "新闻联播"迎来新的男主播刚强 与海霞搭档亮相
  • 刘若英谈与周迅19年友情:有些东西一直不变真好
  • Selina离婚后放得开:我胸前是满满的大平台
  • 世界第二个“三亲宝宝”降生!一个娃两个妈
  • 画面惊呆!母子双双变性成世界首对变性父女
  • 赵又廷自曝不为人知的秘密 竟还和老婆高圆圆有关
  • 痛并快乐着!林心如升级当妈 辛苦挤奶仍大呼开心
  • 赵薇晒“她的年会” 和杨子姗王森重返二十岁
  • 汪小菲深情告白女儿:那么爱 有谁能理解?
  • 谢娜大方晒下巴的伤疤 她说受伤时曾血流成河
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3015|回复: 8

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

    [复制链接]

    20

    主题

    400

    帖子

    439

    积分

    中级会员

    Rank: 3Rank: 3

    积分
    439
    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奇虎

    举报

    26

    主题

    93

    帖子

    148

    积分

    注册会员

    Rank: 2

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


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

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



    --

    11

    主题

    218

    帖子

    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
    : 求大神指点




    --

    16

    主题

    93

    帖子

    119

    积分

    注册会员

    Rank: 2

    积分
    119
    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
    : ...................



    --

    16

    主题

    85

    帖子

    120

    积分

    注册会员

    Rank: 2

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

    求大神指点
    --

    28

    主题

    109

    帖子

    164

    积分

    注册会员

    Rank: 2

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


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


    --

    24

    主题

    72

    帖子

    124

    积分

    注册会员

    Rank: 2

    积分
    124
    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?

    33

    主题

    1120

    帖子

    2234

    积分

    金牌会员

    Rank: 6Rank: 6

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

    20

    主题

    1093

    帖子

    2184

    积分

    金牌会员

    Rank: 6Rank: 6

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

    本版积分规则

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

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

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

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

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