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

 找回密码
 立即注册
  • 章子怡的好后妈人设崩塌? 继女被曝和奶奶生活
  • 好着呢!杨幂刘恺威参加女儿班级活动 一家人同框
  • 美图:我们用户大多是“白富美” 不愁赚钱
  • 网红面包店深夜发声明 承认面粉过期
  • 手机以换壳为本?华为余承东:没有创新才这么干
  • 腾讯二把手悄然交接 一人拿到大笔钱一人掌握更大权
  • 那些恐怖电影中的角色生活中原来长这样
  • 《神奇女侠》女神新手办亮相:脸崩了 但美腿还能玩一年
  • 再进华夏中原 小米之家郑州第二店正式开业
  • 中国人的睡眠:西藏最幸福 海南最可怜
    Logo1-800-PetMeds Free Shipping $49Take $10 Off Your First Order w/code: SAVE10 - 234 x 60
    ASICS AmericaPagoda Piercing Banner 234x60Sierra Trading Post
    搜索
    查看: 3018|回复: 8

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

    [复制链接]

    21

    主题

    405

    帖子

    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 : 每日微信滚动更新美国市场打折团购折扣Coupon讯息。
    回复 百度谷歌雅虎搜狗搜搜有道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

    主题

    224

    帖子

    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

    主题

    113

    帖子

    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

    主题

    1169

    帖子

    2332

    积分

    金牌会员

    Rank: 6Rank: 6

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

    22

    主题

    1143

    帖子

    2286

    积分

    金牌会员

    Rank: 6Rank: 6

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

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

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