吐槽一下 今日头条的面试

[davinci]

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

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

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

[wshcdr]

然后我用数学归纳法简要地证明了一下这个算法的正确性

我比较好奇，帖主是如何用数学归纳法来证明算法的正确性的。算法没问题，

[linbiaye]

@davinci 如果只有数十个节点就是没有问题的，规模小了性能问题可以忽略。

[wshcdr]

@000wangxinyu000 时间复杂度 O(n)空间复杂度 O （ n ），算法本身没啥问题

[davinci]

@wshcdr 假设链表长度为 k 时，算法正确。根据该算法易证长度为 k+1 时算法依然正确。
当长度为 1 时，算法显然正确。所以为 2 时也正确，为 3 时也正确。。。为 n 时也正确 n 为任意正整数

[Em5O7B1JGfjQnBry]

震惊 。。。居然有人用 Python 写递归， scheme 看了会沉默， haskell 看了会流泪。。。

[Felldeadbird]

坐等：《我就是面试楼主的面试官，当时有事……》

[dfguo]

个人认为公司不应该随便派人面试。面试官需要的技能比面试者高很多。一不小心就会这样了。。。

[pwcong]

特意画图研究了下

1->2

1->2
↑---↓

1 2
↑---↓

666 ，感谢楼主让我这个菜鸟学到了逆置列表的新姿势ε=ε=ε=┏(゜ロ゜;)┛

[davinci]

@pwcong 哈哈 楼主也是菜鸟

[MRJ]

@Shura 666

[dubaiwan]

没看上你呗，招人除了技术能力过硬，最主要的还是喜欢对方

[diangdiang]

弱弱问一句，是不是只要
if (head.next == null)
return head;

就可以了? 感觉 head.next == null 会在 head == null 前出现，　 head == null 没用到啊？

[superleexpert]

楼上说对啦~~

[davinci]

@diangdiang
@superleexpert 要考虑到直接传入空链表的情况

[luckymore0520]

表示上周末刚去头条面试，前后聊了 4 个人 8 个多小时，体验很不错。。。

再看楼主，怎么感觉 =.=
我感觉这个面试官要被查水表了。。。

[superleexpert]

@davinci 楼上的楼上

[davinci]

@luckymore0520 面试官被查水表不大可能吧。这也不是我的本意。我已经有其它公司的 offer 了，就是纯粹吐槽一下。感觉那天表现也不大好，即使面试官秒懂了我的思路，也不是稳拿 offer 。另外聊了 8 个多小时这么久感觉好夸张。。。

[lytofb]

head.next.next = head

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

nexthead = head.next
nexthead.next = head

不过招人就是这样，包括很多事情都是这样的，做了正确的事，其实不一定会得到正确的结果

[ibufu]

这不就是 leetcode 上的题目么

[davinci]

@lytofb 这样一改 我反倒觉得更不直观了。。。