吐槽一下 今日头条的面试

[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

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

这个问题背景是 用链表来表示十进制数字。两个链表相加。
即使在实际开发中几十位的十进制数字应该也是一个很大的数了。在链表只有几十个节点的情况下。迭代和递归其实性能差距并不大。

[mickeyandkaka]

确实是对的。
看起来面试官希望的是非递归的实现。估计当时没看懂。

[nagato]

对的吧，面试官说哪不对了？

[nbndco]

其实这种应用用递归不是很合适。
当然这个面试官自己都弄不明白我觉得……

[jacsice]

为什么我看到今日头条就想黑一下呢

[coderluan]

《震惊，面试官居然看不懂递归排序，全世界的程序员都哭了》

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

PS ：我感觉面试官当时脑子里有别的事，一时懵逼了，之后也是去干别的事了。

[Shura]

面试官说你不按常理出牌，我只背了迭代实现，你写个递归，我。。。

[jackisnotspirate]

呵呵，当年面试小米我也写了个二分查找的递归，然后也面试官说不对。。。

[server]

坐等面试官

[airqj]

靠!
不就是工作久了忘了吗？
你小子至于拿到这来让我丢人现眼吗 ：）

[eamon666]

面试的时候切忌和面试官争论 毕竟你的目的是拿到 OFFER 你对了有什么用？
高风亮节的人真的已经不多了

[zer]

楼上是当事人现身说法？

[dogfeet]

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]

@eamon666 你说得对。面试的过程还是很友好平和的。没有争论。

[dbdd]

面试为啥要写递归，如果他不懂他就不会觉得你正确，如果他不觉得你正确你就有可能拿不到 offer 。。。

当面写代码其实对面试官压力更大。。。

[imn1]

这帖应该是今日头条

[davinci]

@dogfeet 两个版本 都有问题

[Mirana]

这种递归栈太深了

[lyragosa]

我很少写递归的原因是，我写程序都会下意识的在脑子里面跑一遍。

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

所以我很少写，要写递归都是要下意识的告诉自己不要把这个程序放到脑子里面跑，不然就是炸裂一般的痛苦。

[davinci]

@Mirana 的确，最好还是要写循环迭代。当时觉得写循环更容易出错，所以选择写递归更简洁明了。

[dogfeet]

@davinci 不是 2 个版本哟，是一个。本意是， head == None 只需要第一次判断一次， head.nex = None 只需要最后递归完后原先的头节点执行一次。中间递归的过程中可以省略这 2 步。所以 reverse 调用的 reverseImpl 。

不过可能有问题吧，没装 py 环境没试 :(

[eamon666]

@zer 你这个出现了“幻读”了 我的 LS 才是你该回复的呀 233

[x86]

@coderluan 《震惊，某程序员手写递归排序，男的看了沉默，女的看了流泪》

[jmc891205]

说句题外话 我觉得出 Python 面试题的时候应该尽量不要涉及链表
Python 对于任何链表适合解决的问题 都有其他更方便的数据结构可以用

[jmc891205]

@x86 楼主写的不是排序啊哈哈 UC 震惊部拒绝了你

[leyle]

震惊！今日头条招人黑幕，技术面试官竟然做出如此事情。。。

[davinci]

@dogfeet 这样写代码量过大。有种简单问题复杂化的感觉。脑补了一下，应该是对的。

[hornets]

@airqj 今日头条面试官？

[timle1029]

@dogfeet
def reverse(head):
pre = None
while head is not None:
next = head.next
head.next = pre
pre = head
head = next
return pre

会不会这样更好一点..

[mringg]

如果只是实现功能，递归毫无问题吧。
ps.话说楼上怎么有的扯到排序了

[tiancaiamao]

@dbdd 不不不，当面写代码还是面试者压力大一些，心态不一样。

[davinci]

@tiancaiamao 完全同意。

[uuweZhou]

这种面试官...水平会不会太次

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

补充一个 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]

非程序员。。看了下这代码。。感觉跟那个解汉诺塔的算法一样~~

[lgh]

为什么一直没人说 == None 这个判断，不是应该用 is None 么？

[Anybfans]

@lgh #34 is None 感觉要快一点 其他两者没区别吧

[falcon05]

只有我觉得他出去是找个 case 运行了一下代码吗？

[000wangxinyu000]

这种做法是不是存在两个问题：
1 ）如上面某位说的，栈递归太深了。递归次数多了执行的时候会报错。
2 ）性能问题：你这种做法相当于，每次递归在函数栈上申请了一个临时变量，用这个临时变量指向当前递归的链表上的节点。等递归一个一个退栈的时候，通过索引这些临时变量把链表反向串起来。这种做法内存和时间的开销是不是比较大。

[linbiaye]

@000wangxinyu000 说得对，性能都是其次，主要问题是链表长了这个程序就得跪。

[linbiaye]

@davinci 楼主没有考虑输入规模。

[davinci]

@linbiaye
@000wangxinyu000 在那个问题背景下 链表长度最多只有几十个节点 如果从性能考虑 这种情况下 差距应该不大吧

[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 这样一改 我反倒觉得更不直观了。。。

[yuankui]

"把链表逆置"这种操作就跟"把汽车翻过来"一样
看起来好像很牛逼的样子,实际上没什么鸟用..

[irenicus]

没毛病

[a1310747]

@nagato 長門?

[yanchao7511461]

首先..我觉得链表逆序其实没啥好考的...其次我觉得 lz 写的是对的.... 虽然 head.next.next = head 这里不好理解。但理解了就很清晰了。面试官有点蠢..... 不过面试确实是运气的成分更大。

[CloudnuY]

大概是你的变量名没有叫 amazing ！！！、 shocking ！！！

[aihimmel]

@a1310747 应该是的

[diangdiang]

@davinci 螺旋稳

[guomiaoyou7784]

面试官没看懂，可以要求跑几个 test case 。或者手动模拟一遍。感觉楼主被面试官坑了

[hanbing135]

面试官不懂估计懵逼了

[sakurajiang]

楼主是校招内推吗？

[xiaoyao9933]

怎么觉得这种递归下去的调用栈，比直接复制个新链表的开销还要大。。哪位大神给我讲讲内存开销呗？

[danielmiao]

个人感觉用 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]

这个递归第一次看确实有点绕，但也不至于跑了 case 都看不懂。

[danielmiao]

不会贴代码。。。。。
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]

听说今日头条的面试是国内大厂里平均最难的…看了这个帖子我只是觉得这个面试官没连刷过 leetcode ，链表逆置用递归在面试题里是很常见的考法。

[mianju]

@CloudnuY 那变量名用 exciting 、 naive 、 simple 会不会更容易过？

[bhagavad]

大概三年前去面过一次头条，一面搞了两个小时，还是周六，能看出面试官还是挺不错的，因为下午直接接了前东家的 offer ，就没有再去二面。
两年前从前东家离职时直接又给原来的面试官发了简历，又去面了一次。笔试同样是链表翻转，我用 C++ 写的，结果新面试官直接说不会 C++，当时就有种“卧槽，这都行？”的感受，具体细节记不清了，但是只记得对面试官印象极差，一是把控不了整个面试过程，二是技术水平极差，就是一个个子不算高，稍微有点胖的哥们，年龄不大，应该工作没几年。还有最受不了的是二面的时间间隔，没有任何人告诉我需要等多长时间，我印象中去门口前台问了三四次需要多长时间，每次间隔应该都是半小时左右的，然后二面面试官才过来。上来就牛逼哄哄的说你原来做过阅读是吧，阅读排版具体是怎么做的？剩下的其他问题都忘了，唯一记得的就是没有问任何 Android 相关的东西。
应该是头条人太多了，所以也良莠不齐，自那以后再也没去面过头条，以后也不会再去了。

[smallSohoSolo]

中肯的说，你确定你挂在了这道题上？

[song4]

算法没毛病，给出归纳法证明更是加分项。

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

面试是一个偶然性相当大的事情，要看开啊。

[ssoftlns]

看来面试官是个不懂装懂的傻 x

[iceny]

大厂么

[mingyun]

今日头条算大厂，虽然我没用过

[wuyadong]

前段时间，我也面过今日头条。确实能感觉到面试官的水平没有那么好。

[dddddyyyy]

楼主最后去哪了？

[markx]

我正好想问个问题， 关于面试的题目， 大家通常会优先用递归还是迭代啊？ 我现在用递归总觉得心里有点障碍，总担心面试官会说空间上效率不够高，让我再用迭代写一次。