V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Sponsored by
LinkedIn
不坐班的神仙工作 · 去任何你想去的地方远程,赚一线城市的工资
2000 个不用出门 Social 的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
davinci
V2EX  ›  职场话题

吐槽一下 今日头条的面试

  •  6
     
  •   davinci · 2017-03-08 11:10:35 +08:00 · 40258 次点击
    这是一个创建于 2028 天前的主题,其中的信息可能已经有所发展或是发生改变。

    上周去今日头条面试。其中一道算法题的预处理步骤需要用到链表逆置。我写了一个递归函数。

    def reverse(head):
        if head==None or head.next==None:
            return head
        result = reverse(head.next)
        head.next.next = head
        head.next = None
        return result
    

    结果面试官看了几分钟,没看懂觉得有问题。然后我用数学归纳法简要地证明了一下这个算法的正确性,他想了几分钟还是觉得有问题,然后我又举了一两个简单例子展示该算法的运行过程,他看了一会儿想了一会儿还是觉得不对劲。末了,他叫我在这等一会,便抱着电脑出去了。我在屋子里等了半天也不见人影,大概过了有半小时,我走出面试房间,看到他,他说今天就面到这了。想想也是有些无语。

    第 1 条附言  ·  2017-03-08 14:07:23 +08:00
    这个问题背景是 用链表来表示十进制数字。两个链表相加。
    即使在实际开发中几十位的十进制数字应该也是一个很大的数了。在链表只有几十个节点的情况下。迭代和递归其实性能差距并不大。
    86 条回复    2018-02-05 00:36:42 +08:00
    mickeyandkaka
        1
    mickeyandkaka  
       2017-03-08 11:19:53 +08:00
    确实是对的。
    看起来面试官希望的是非递归的实现。估计当时没看懂。
    nagato
        2
    nagato  
       2017-03-08 11:27:07 +08:00
    对的吧,面试官说哪不对了?
    nbndco
        3
    nbndco  
       2017-03-08 11:28:46 +08:00
    其实这种应用用递归不是很合适。
    当然这个面试官自己都弄不明白我觉得……
    jacsice
        4
    jacsice  
       2017-03-08 11:30:35 +08:00   ❤️ 2
    为什么我看到今日头条就想黑一下呢
    coderluan
        5
    coderluan  
       2017-03-08 11:31:50 +08:00   ❤️ 10
    《震惊,面试官居然看不懂递归排序,全世界的程序员都哭了》

    你不起个这种标题,过的了技术面,也过不了 HR 面。

    PS :我感觉面试官当时脑子里有别的事,一时懵逼了,之后也是去干别的事了。
    Shura
        6
    Shura  
       2017-03-08 11:33:50 +08:00 via Android   ❤️ 5
    面试官说你不按常理出牌,我只背了迭代实现,你写个递归,我。。。
    jackisnotspirate
        7
    jackisnotspirate  
       2017-03-08 11:35:05 +08:00
    呵呵,当年面试小米我也写了个二分查找的递归,然后也面试官说不对。。。
    server
        8
    server  
       2017-03-08 11:37:16 +08:00
    坐等面试官
    airqj
        9
    airqj  
       2017-03-08 11:39:57 +08:00
    靠!
    不就是工作久了忘了吗?
    你小子至于拿到这来让我丢人现眼吗 :)
    eamon666
        10
    eamon666  
       2017-03-08 11:41:10 +08:00
    面试的时候切忌和面试官争论 毕竟你的目的是拿到 OFFER 你对了有什么用?
    高风亮节的人真的已经不多了
    zer
        11
    zer  
       2017-03-08 11:41:20 +08:00
    楼上是当事人现身说法?
    dogfeet
        12
    dogfeet  
       2017-03-08 11:41:30 +08:00
    def reverseImpl(head):
    if head.next == None:
    return head
    result = reverseImpl(head.next)
    head.next.next = head
    return result

    def reverse(head):
    if head == None:
    return head
    ret = reverseImpl(head)
    head.next = None
    return ret

    不会 Python ,写成这样是不是对的呀?
    davinci
        13
    davinci  
    OP
       2017-03-08 11:43:05 +08:00   ❤️ 1
    @eamon666 你说得对。面试的过程还是很友好平和的。没有争论。
    dbdd
        14
    dbdd  
       2017-03-08 11:47:18 +08:00
    面试为啥要写递归,如果他不懂他就不会觉得你正确,如果他不觉得你正确你就有可能拿不到 offer 。。。

    当面写代码其实对面试官压力更大。。。
    imn1
        15
    imn1  
       2017-03-08 11:49:04 +08:00
    这帖应该是今日头条
    davinci
        16
    davinci  
    OP
       2017-03-08 11:51:07 +08:00
    @dogfeet 两个版本 都有问题
    Mirana
        17
    Mirana  
       2017-03-08 11:54:56 +08:00
    这种递归栈太深了
    lyragosa
        18
    lyragosa  
       2017-03-08 11:58:54 +08:00   ❤️ 2
    我很少写递归的原因是,我写程序都会下意识的在脑子里面跑一遍。

    如果写递归,我感觉我脑子就如同 stackoverflow 了一样难受。

    所以我很少写,要写递归都是要下意识的告诉自己不要把这个程序放到脑子里面跑,不然就是炸裂一般的痛苦。
    davinci
        19
    davinci  
    OP
       2017-03-08 11:59:22 +08:00
    @Mirana 的确,最好还是要写循环迭代。当时觉得写循环更容易出错,所以选择写递归更简洁明了。
    dogfeet
        20
    dogfeet  
       2017-03-08 12:04:17 +08:00
    @davinci 不是 2 个版本哟,是一个。本意是, head == None 只需要第一次判断一次, head.nex = None 只需要最后递归完后原先的头节点执行一次。中间递归的过程中可以省略这 2 步。所以 reverse 调用的 reverseImpl 。

    不过可能有问题吧,没装 py 环境没试 :(
    eamon666
        21
    eamon666  
       2017-03-08 12:08:48 +08:00   ❤️ 1
    @zer 你这个出现了“幻读”了 我的 LS 才是你该回复的呀 233
    x86
        22
    x86  
       2017-03-08 12:12:07 +08:00
    @coderluan 《震惊,某程序员手写递归排序,男的看了沉默,女的看了流泪》
    jmc891205
        23
    jmc891205  
       2017-03-08 12:12:13 +08:00
    说句题外话 我觉得出 Python 面试题的时候应该尽量不要涉及链表
    Python 对于任何链表适合解决的问题 都有其他更方便的数据结构可以用
    jmc891205
        24
    jmc891205  
       2017-03-08 12:12:44 +08:00
    @x86 楼主写的不是排序啊哈哈 UC 震惊部拒绝了你
    leyle
        25
    leyle  
       2017-03-08 12:13:38 +08:00   ❤️ 1
    震惊!今日头条招人黑幕,技术面试官竟然做出如此事情。。。
    davinci
        26
    davinci  
    OP
       2017-03-08 12:14:46 +08:00
    @dogfeet 这样写代码量过大。有种简单问题复杂化的感觉。脑补了一下,应该是对的。
    hornets
        27
    hornets  
       2017-03-08 12:15:01 +08:00
    @airqj 今日头条面试官?
    timle1029
        28
    timle1029  
       2017-03-08 12:29:50 +08:00   ❤️ 1
    @dogfeet
    def reverse(head):
    pre = None
    while head is not None:
    next = head.next
    head.next = pre
    pre = head
    head = next
    return pre

    会不会这样更好一点..
    mringg
        29
    mringg  
       2017-03-08 12:47:35 +08:00 via iPhone
    如果只是实现功能,递归毫无问题吧。
    ps.话说楼上怎么有的扯到排序了
    tiancaiamao
        30
    tiancaiamao  
       2017-03-08 12:51:35 +08:00
    @dbdd 不不不,当面写代码还是面试者压力大一些,心态不一样。
    davinci
        31
    davinci  
    OP
       2017-03-08 12:52:29 +08:00
    @tiancaiamao 完全同意。
    uuweZhou
        32
    uuweZhou  
       2017-03-08 12:53:25 +08:00
    这种面试官...水平会不会太次

    单链表逆序的递归实现这种比较基础的题都...

    补充一个 java 实现:

    ```java

    public static Node reverse(Node head){

    if (head==null||head.getNext()==null) {
    return head;
    }

    Node reversedHead=reverse(head.getNext());

    head.getNext().setNext(head);

    head.setNext(null);

    return reversedHead;
    }

    public static Node reverse1(Node head){

    if (head==null) {
    return head;
    }

    Node pre=head;

    Node cur=head.getNext();

    Node tem;

    while(cur!=null){

    tem=cur.getNext();

    cur.setNext(pre);

    pre=cur;
    cur=tem;
    }

    head.setNext(null);
    return pre;
    }

    ```
    lekai63
        33
    lekai63  
       2017-03-08 13:05:21 +08:00
    非程序员。。看了下这代码。。感觉跟那个解汉诺塔的算法一样~~
    lgh
        34
    lgh  
       2017-03-08 13:06:44 +08:00 via iPhone
    为什么一直没人说 == None 这个判断,不是应该用 is None 么?
    Anybfans
        35
    Anybfans  
       2017-03-08 13:09:44 +08:00
    @lgh #34 is None 感觉要快一点 其他两者没区别吧
    falcon05
        36
    falcon05  
       2017-03-08 13:10:25 +08:00 via iPhone
    只有我觉得他出去是找个 case 运行了一下代码吗?
    000wangxinyu000
        37
    000wangxinyu000  
       2017-03-08 13:46:29 +08:00   ❤️ 1
    这种做法是不是存在两个问题:
    1 )如上面某位说的,栈递归太深了。递归次数多了执行的时候会报错。
    2 )性能问题:你这种做法相当于,每次递归在函数栈上申请了一个临时变量,用这个临时变量指向当前递归的链表上的节点。等递归一个一个退栈的时候,通过索引这些临时变量把链表反向串起来。这种做法内存和时间的开销是不是比较大。
    linbiaye
        38
    linbiaye  
       2017-03-08 13:56:24 +08:00
    @000wangxinyu000 说得对,性能都是其次,主要问题是链表长了这个程序就得跪。
    linbiaye
        39
    linbiaye  
       2017-03-08 13:57:29 +08:00
    @davinci 楼主没有考虑输入规模。
    davinci
        40
    davinci  
    OP
       2017-03-08 14:01:03 +08:00 via iPhone
    @linbiaye
    @000wangxinyu000 在那个问题背景下 链表长度最多只有几十个节点 如果从性能考虑 这种情况下 差距应该不大吧
    wshcdr
        41
    wshcdr  
       2017-03-08 14:03:48 +08:00
    然后我用数学归纳法简要地证明了一下这个算法的正确性

    我比较好奇,帖主是如何用数学归纳法来证明算法的正确性的。算法没问题,
    linbiaye
        42
    linbiaye  
       2017-03-08 14:04:23 +08:00
    @davinci 如果只有数十个节点就是没有问题的,规模小了性能问题可以忽略。
    wshcdr
        43
    wshcdr  
       2017-03-08 14:10:37 +08:00
    @000wangxinyu000 时间复杂度 O(n)空间复杂度 O ( n ),算法本身没啥问题
    davinci
        44
    davinci  
    OP
       2017-03-08 14:12:14 +08:00 via iPhone
    @wshcdr 假设链表长度为 k 时,算法正确。根据该算法易证长度为 k+1 时算法依然正确。
    当长度为 1 时,算法显然正确。所以为 2 时也正确,为 3 时也正确。。。为 n 时也正确 n 为任意正整数
    svenFeng
        45
    svenFeng  
       2017-03-08 14:13:15 +08:00 via Android
    震惊 。。。居然有人用 Python 写递归, scheme 看了会沉默, haskell 看了会流泪。。。
    Felldeadbird
        46
    Felldeadbird  
       2017-03-08 14:20:07 +08:00
    坐等:《我就是面试楼主的面试官,当时有事……》
    dfguo
        47
    dfguo  
       2017-03-08 14:21:09 +08:00
    个人认为公司不应该随便派人面试。面试官需要的技能比面试者高很多。一不小心就会这样了。。。
    pwcong
        48
    pwcong  
       2017-03-08 14:24:02 +08:00
    特意画图研究了下

    1->2

    1->2
    ↑---↓

    1 2
    ↑---↓

    666 ,感谢楼主让我这个菜鸟学到了逆置列表的新姿势ε=ε=ε=┏(゜ロ゜;)┛
    davinci
        49
    davinci  
    OP
       2017-03-08 14:27:06 +08:00 via iPhone
    @pwcong 哈哈 楼主也是菜鸟
    MRJ
        50
    MRJ  
       2017-03-08 15:05:59 +08:00
    @Shura 666
    dubaiwan
        51
    dubaiwan  
       2017-03-08 15:19:41 +08:00
    没看上你呗,招人除了技术能力过硬,最主要的还是喜欢对方
    diangdiang
        52
    diangdiang  
       2017-03-08 15:28:30 +08:00
    弱弱问一句,是不是只要
    if (head.next == null)
    return head;

    就可以了? 感觉 head.next == null 会在 head == null 前出现,  head == null 没用到啊?
    superleexpert
        53
    superleexpert  
       2017-03-08 15:29:20 +08:00
    楼上说对啦~~
    davinci
        54
    davinci  
    OP
       2017-03-08 15:37:46 +08:00 via iPhone
    @diangdiang
    @superleexpert 要考虑到直接传入空链表的情况
    luckymore0520
        55
    luckymore0520  
       2017-03-08 15:41:45 +08:00
    表示上周末刚去头条面试,前后聊了 4 个人 8 个多小时,体验很不错。。。

    再看楼主,怎么感觉 =.=
    我感觉这个面试官要被查水表了。。。
    superleexpert
        56
    superleexpert  
       2017-03-08 15:47:51 +08:00
    @davinci 楼上的楼上
    davinci
        57
    davinci  
    OP
       2017-03-08 15:49:44 +08:00 via iPhone
    @luckymore0520 面试官被查水表不大可能吧。这也不是我的本意。我已经有其它公司的 offer 了,就是纯粹吐槽一下。感觉那天表现也不大好,即使面试官秒懂了我的思路,也不是稳拿 offer 。另外聊了 8 个多小时这么久感觉好夸张。。。
    lytofb
        58
    lytofb  
       2017-03-08 15:50:42 +08:00
    head.next.next = head

    这块改一下就好了,改成下面这样。

    nexthead = head.next
    nexthead.next = head

    不过招人就是这样,包括很多事情都是这样的,做了正确的事,其实不一定会得到正确的结果
    ibufu
        59
    ibufu  
       2017-03-08 15:51:13 +08:00
    这不就是 leetcode 上的题目么
    davinci
        60
    davinci  
    OP
       2017-03-08 15:53:41 +08:00 via iPhone
    @lytofb 这样一改 我反倒觉得更不直观了。。。
    yuankui
        61
    yuankui  
       2017-03-08 16:38:22 +08:00
    "把链表逆置"这种操作就跟"把汽车翻过来"一样
    看起来好像很牛逼的样子,实际上没什么鸟用..
    irenicus
        62
    irenicus  
       2017-03-08 16:49:43 +08:00
    没毛病
    a1310747
        63
    a1310747  
       2017-03-08 16:50:27 +08:00
    @nagato 長門?
    yanchao7511461
        64
    yanchao7511461  
       2017-03-08 16:54:25 +08:00
    首先..我觉得链表逆序其实没啥好考的...其次我觉得 lz 写的是对的.... 虽然 head.next.next = head 这里不好理解。但理解了就很清晰了。面试官有点蠢..... 不过面试确实是运气的成分更大。
    CloudnuY
        65
    CloudnuY  
       2017-03-08 17:06:38 +08:00
    大概是你的变量名没有叫 amazing !!!、 shocking !!!
    aihimmel
        66
    aihimmel  
       2017-03-08 17:11:20 +08:00 via Android
    @a1310747 应该是的
    diangdiang
        67
    diangdiang  
       2017-03-08 17:33:33 +08:00
    @davinci 螺旋稳
    guomiaoyou7784
        68
    guomiaoyou7784  
       2017-03-08 17:35:15 +08:00
    面试官没看懂,可以要求跑几个 test case 。或者手动模拟一遍。感觉楼主被面试官坑了
    hanbing135
        69
    hanbing135  
       2017-03-08 17:57:14 +08:00 via Android
    面试官不懂估计懵逼了
    sakurajiang
        70
    sakurajiang  
       2017-03-08 19:17:07 +08:00
    楼主是校招内推吗?
    xiaoyao9933
        71
    xiaoyao9933  
       2017-03-08 19:52:39 +08:00
    怎么觉得这种递归下去的调用栈,比直接复制个新链表的开销还要大。。哪位大神给我讲讲内存开销呗?
    danielmiao
        72
    danielmiao  
       2017-03-08 20:13:49 +08:00
    个人感觉用 stack 简单清晰明了,考官可能想看看你是不是足够了解 stack , queue 的特性?

    def reverse(node):
    stack = []
    while node != None:
    stack.append(node)
    node = node.next
    head = stack.pop()
    last = head
    while len(stack) > 0:
    last.next = stack.pop()
    last = last.next
    last.next = None
    return head

    很少写 python ,我猜是对的
    lsmgeb89
        73
    lsmgeb89  
       2017-03-08 20:14:13 +08:00 via Android
    这个递归第一次看确实有点绕,但也不至于跑了 case 都看不懂。
    danielmiao
        74
    danielmiao  
       2017-03-08 20:26:58 +08:00
    不会贴代码。。。。。
    def reverse(node):
    stack = []

    while node != None:
    stack.append(node)
    node = node.next
    //end of while

    head = stack.pop()
    last = head

    while len(stack) > 0:
    last.next = stack.pop()
    last = last.next
    last.next = None
    //end of while

    return head
    Jimrussell
        75
    Jimrussell  
       2017-03-08 22:23:40 +08:00 via Android
    听说今日头条的面试是国内大厂里平均最难的…看了这个帖子我只是觉得这个面试官没连刷过 leetcode ,链表逆置用递归在面试题里是很常见的考法。
    mianju
        76
    mianju  
       2017-03-08 22:29:31 +08:00
    @CloudnuY 那变量名用 exciting 、 naive 、 simple 会不会更容易过?
    bhagavad
        77
    bhagavad  
       2017-03-08 22:53:37 +08:00
    大概三年前去面过一次头条,一面搞了两个小时,还是周六,能看出面试官还是挺不错的,因为下午直接接了前东家的 offer ,就没有再去二面。
    两年前从前东家离职时直接又给原来的面试官发了简历,又去面了一次。笔试同样是链表翻转,我用 C++ 写的,结果新面试官直接说不会 C++,当时就有种“卧槽,这都行?”的感受,具体细节记不清了,但是只记得对面试官印象极差,一是把控不了整个面试过程,二是技术水平极差,就是一个个子不算高,稍微有点胖的哥们,年龄不大,应该工作没几年。还有最受不了的是二面的时间间隔,没有任何人告诉我需要等多长时间,我印象中去门口前台问了三四次需要多长时间,每次间隔应该都是半小时左右的,然后二面面试官才过来。上来就牛逼哄哄的说你原来做过阅读是吧,阅读排版具体是怎么做的?剩下的其他问题都忘了,唯一记得的就是没有问任何 Android 相关的东西。
    应该是头条人太多了,所以也良莠不齐,自那以后再也没去面过头条,以后也不会再去了。
    smallSohoSolo
        78
    smallSohoSolo  
       2017-03-08 23:20:24 +08:00 via Android
    中肯的说,你确定你挂在了这道题上?
    song4
        79
    song4  
       2017-03-08 23:33:30 +08:00
    算法没毛病,给出归纳法证明更是加分项。

    很多面试官心里想得不是面试你这个人,而是百般刁难你并以此展示自己的牛逼。如果遇到这种面试官,而你又让他吃相太难看,那你肯定挂了。

    面试是一个偶然性相当大的事情,要看开啊。
    ssoftlns
        80
    ssoftlns  
       2017-03-09 09:54:31 +08:00
    看来面试官是个不懂装懂的傻 x
    iceny
        81
    iceny  
       2017-03-09 14:51:52 +08:00
    大厂么
    mingyun
        82
    mingyun  
       2017-03-09 21:40:31 +08:00
    今日头条算大厂,虽然我没用过
    wuyadong
        83
    wuyadong  
       2017-03-09 22:20:33 +08:00
    前段时间,我也面过今日头条。确实能感觉到面试官的水平没有那么好。
    dddddyyyy
        84
    dddddyyyy  
       2017-09-28 14:39:18 +08:00
    楼主最后去哪了?
    markx
        86
    markx  
       2018-02-05 00:36:42 +08:00
    我正好想问个问题, 关于面试的题目, 大家通常会优先用递归还是迭代啊? 我现在用递归总觉得心里有点障碍,总担心面试官会说空间上效率不够高,让我再用迭代写一次。
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1324 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 55ms · UTC 18:28 · PVG 02:28 · LAX 11:28 · JFK 14:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.