V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
peneazy
V2EX  ›  程序员

为啥大家的面试段子都是手写红黑树,而不是手写 AVL 树或堆树一类的

  •  
  •   peneazy · 2016-12-09 16:01:12 +08:00 · 16950 次点击
    这是一个创建于 2666 天前的主题,其中的信息可能已经有所发展或是发生改变。
    29 条回复    2017-12-26 14:09:20 +08:00
    raysonx
        1
    raysonx  
       2016-12-09 16:09:30 +08:00
    紅黑樹插入和刪除對要處理的各種情況相對 AVL 樹多得多,我覺得大多數人如果不是天天折騰這個,徒手擼一個紅黑樹還是很困難的(比如我)。
    raysonx
        2
    raysonx  
       2016-12-09 16:10:14 +08:00
    紅黑樹原理不複雜,但是要處理的各種細節多得要死要死。
    simpleapples
        3
    simpleapples  
       2016-12-09 16:19:49 +08:00
    看成面试段子手...
    lantianziyun
        4
    lantianziyun  
       2016-12-09 16:24:34 +08:00
    面试杀手锏,完全不会写红黑树的飘过。
    misaka19000
        5
    misaka19000  
       2016-12-09 16:57:32 +08:00 via Android
    红黑树规则比较多,不好好理顺的话会吐血的
    话说这东西我都要背下来才能手写,你们一般是怎么搞才能不靠死记硬背而把各种情况都搞定?
    hitmanx
        6
    hitmanx  
       2016-12-09 17:18:36 +08:00
    红黑树一般存在于段子里和吹牛里,我是不太相信什么公司会考手写红黑树之类的,哪怕是 google 。
    enenaaa
        7
    enenaaa  
       2016-12-09 17:25:08 +08:00
    @hitmanx google 那段子不是面试者自己爆出来的吗。 老实说如果不是事先准备,能当场正确写出红黑树平衡算法的 google 员工,我想也不多。
    dtfm
        8
    dtfm  
       2016-12-09 17:28:03 +08:00
    @hitmanx 我在网上看见过百度某年笔试题中似乎有过,但不清楚这是真来自百度笔试题还是网友瞎编的,但确实我也不认为大多数程序员能笔试手写出能跑的红黑树,写个二分查找意思意思就行了。
    hitmanx
        9
    hitmanx  
       2016-12-09 18:00:06 +08:00
    @enenaaa 我看过有人(好像是老外)写的关于应聘 google 的文章。印象比较深的就是讲其中一个优秀的应届生面试 google 失败,他自觉得算法准备得很好,比如准备了红黑树的几种旋转。但是被作者批了,大概意思是除了前几天刚学过红黑树的在校生,不会有人能清晰地记得红黑树的所有旋转方法,包括 google 自己的员工。而且作为一道面试题,这也不是很合适,因为不是在 20-30 分钟内就能凭借自己能力推导出来的。拿这个筛选,最后考察的不是能力,而是有没有“准备过”,这和面试筛选的初衷有点背道而驰。所以我觉得即使要考核,更可能的并不是直接上来就问红黑树,而是一道包装过的,表面上看上去根本不像红黑树的红黑树题。
    fatedier
        10
    fatedier  
       2016-12-09 18:39:19 +08:00
    @hitmanx 说的很对呀,我觉得问一下红黑树和 AVL 树各自特点就好了,其实就是看一下对方的学习态度。
    peneazy
        11
    peneazy  
    OP
       2016-12-09 19:02:12 +08:00 via Android
    @raysonx 算法愉悦身心
    catror
        12
    catror  
       2016-12-09 19:12:00 +08:00 via Android
    面试手写过最复杂的是堆排序
    9hills
        13
    9hills  
       2016-12-09 23:03:57 +08:00 via iPhone
    因为要挑一个面试时大部分人写不出来(比如我)却都知道很基本的原理的

    用来衬托面试者的眼高手低,形成戏剧性的落差,别的东西没有这个效果。
    msg7086
        14
    msg7086  
       2016-12-10 01:16:12 +08:00
    面试题应该要弱化准备过程,而强化思考过程。
    xiamx
        15
    xiamx  
       2016-12-10 07:53:06 +08:00 via Android
    跟面试官的经历有关,有些学校只讲红黑树, 2-3 树,不讲其他的
    q397064399
        16
    q397064399  
       2016-12-10 07:59:50 +08:00
    这有什么难的
    Map map = new TreeMap();
    手动斜眼,已经写完了
    linux40
        17
    linux40  
       2016-12-10 09:07:00 +08:00 via Android
    我也觉得堆比红黑树难。。。
    aheadlead
        18
    aheadlead  
       2016-12-10 09:33:56 +08:00
    @hitmanx 南京 Wind
    lsmgeb89
        19
    lsmgeb89  
       2016-12-10 09:45:53 +08:00
    都是段子而已,面红黑树有什么意义?

    真的要写的话,也是对着论文抄算法,没有意义。
    q397064399
        20
    q397064399  
       2016-12-11 07:55:39 +08:00
    @lsmgeb89 应该面一下 多线程红黑树 如何加锁 解锁
    提升容器吞吐能力
    farseeraliens
        21
    farseeraliens  
       2016-12-11 18:34:54 +08:00 via iPhone
    @q397064399 多线程不适合用树吧……
    farseeraliens
        22
    farseeraliens  
       2016-12-11 18:35:47 +08:00 via iPhone
    @linux40 c++stl 有现成的,并不难
    q397064399
        23
    q397064399  
       2016-12-11 18:57:42 +08:00
    @farseeraliens
    你考虑下,红黑树的插入 是可以加锁的,
    插入时 只要当前节点的黑父是锁住的,就可以保证整体有序
    读的话,就肯定会出现丢失的情况,
    goubenger
        24
    goubenger  
       2016-12-11 22:42:14 +08:00
    真不是段子,不要小看小公司的面试,手写红黑树手写哈希表我都遇到过!
    linux40
        25
    linux40  
       2016-12-12 09:32:40 +08:00 via Android
    @farseeraliens 别说自带的那个残废。
    linux40
        26
    linux40  
       2016-12-12 09:34:57 +08:00 via Android
    @farseeraliens 顺便说夸张点,自带的那个我闭着眼睛都能写出来。
    imbahom
        27
    imbahom  
       2016-12-12 14:24:56 +08:00
    通常,有面试官问我红黑数这种问题。
    我一般扭头就走。
    不是因为,这个职位用不到还问这个。
    而是因为。
    我 tmd 真的不会
    farseeraliens
        28
    farseeraliens  
       2017-10-20 13:18:46 +08:00 via iPhone
    @linux40 能说一下 stl 的堆有什么问题吗?
    linux40
        29
    linux40  
       2017-12-26 14:09:20 +08:00 via Android
    @farseeraliens merge decrease_key
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1017 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 30ms · UTC 19:42 · PVG 03:42 · LAX 12:42 · JFK 15:42
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.