吐槽一下今日头条的面试

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2851 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

2017-03-08 11:19:53 +08:00

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

nagato

2017-03-08 11:27:07 +08:00

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

nbndco

2017-03-08 11:28:46 +08:00

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

jacsice

2017-03-08 11:30:35 +08:00

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

coderluan

2017-03-08 11:31:50 +08:00

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

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

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

Shura

2017-03-08 11:33:50 +08:00 via Android

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

jackisnotspirate

2017-03-08 11:35:05 +08:00

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

server

2017-03-08 11:37:16 +08:00

坐等面试官

airqj

2017-03-08 11:39:57 +08:00

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

eamon666

2017-03-08 11:41:10 +08:00

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

zer

2017-03-08 11:41:20 +08:00

楼上是当事人现身说法？

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

2017-03-08 11:43:05 +08:00

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

dbdd

2017-03-08 11:47:18 +08:00

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

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

imn1

2017-03-08 11:49:04 +08:00

这帖应该是今日头条

davinci

2017-03-08 11:51:07 +08:00

@dogfeet 两个版本都有问题

Mirana

2017-03-08 11:54:56 +08:00

这种递归栈太深了

lyragosa

2017-03-08 11:58:54 +08:00

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

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

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

davinci

2017-03-08 11:59:22 +08:00

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

dogfeet

2017-03-08 12:04:17 +08:00

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

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

eamon666

2017-03-08 12:08:48 +08:00

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

x86

2017-03-08 12:12:07 +08:00

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

jmc891205

2017-03-08 12:12:13 +08:00

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

jmc891205

2017-03-08 12:12:44 +08:00

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

leyle

2017-03-08 12:13:38 +08:00

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

davinci

2017-03-08 12:14:46 +08:00

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

hornets

2017-03-08 12:15:01 +08:00

@airqj 今日头条面试官？

timle1029

2017-03-08 12:29:50 +08:00

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

会不会这样更好一点..

mringg

2017-03-08 12:47:35 +08:00 via iPhone

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

tiancaiamao

2017-03-08 12:51:35 +08:00

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

davinci

2017-03-08 12:52:29 +08:00

@tiancaiamao 完全同意。

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

2017-03-08 13:05:21 +08:00

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

lgh

2017-03-08 13:06:44 +08:00 via iPhone

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

Anybfans

2017-03-08 13:09:44 +08:00

@lgh #34 is None 感觉要快一点

其他两者没区别吧

falcon05

2017-03-08 13:10:25 +08:00 via iPhone

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

000wangxinyu000

2017-03-08 13:46:29 +08:00

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

linbiaye

2017-03-08 13:56:24 +08:00

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

linbiaye

2017-03-08 13:57:29 +08:00

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

davinci

2017-03-08 14:01:03 +08:00 via iPhone

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

wshcdr

2017-03-08 14:03:48 +08:00

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

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

linbiaye

2017-03-08 14:04:23 +08:00

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

wshcdr

2017-03-08 14:10:37 +08:00

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

davinci

2017-03-08 14:12:14 +08:00 via iPhone

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

Em5O7B1JGfjQnBry

2017-03-08 14:13:15 +08:00 via Android

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

Felldeadbird

2017-03-08 14:20:07 +08:00

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

dfguo

2017-03-08 14:21:09 +08:00

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

pwcong

2017-03-08 14:24:02 +08:00

特意画图研究了下

1->2

1->2
↑---↓

1 2
↑---↓

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

davinci

2017-03-08 14:27:06 +08:00 via iPhone

@pwcong 哈哈楼主也是菜鸟

MRJ

2017-03-08 15:05:59 +08:00

@Shura 666

dubaiwan

2017-03-08 15:19:41 +08:00

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

diangdiang

2017-03-08 15:28:30 +08:00

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

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

superleexpert

2017-03-08 15:29:20 +08:00

楼上说对啦~~

davinci

2017-03-08 15:37:46 +08:00 via iPhone

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

luckymore0520

2017-03-08 15:41:45 +08:00

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

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

superleexpert

2017-03-08 15:47:51 +08:00

@davinci 楼上的楼上

davinci

2017-03-08 15:49:44 +08:00 via iPhone

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

lytofb

2017-03-08 15:50:42 +08:00

head.next.next = head

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

nexthead = head.next
nexthead.next = head

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

ibufu

2017-03-08 15:51:13 +08:00

这不就是 leetcode 上的题目么

davinci

2017-03-08 15:53:41 +08:00 via iPhone

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

yuankui

2017-03-08 16:38:22 +08:00

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

irenicus

2017-03-08 16:49:43 +08:00

没毛病

a1310747

2017-03-08 16:50:27 +08:00

@nagato 長門?

yanchao7511461

2017-03-08 16:54:25 +08:00

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

CloudnuY

2017-03-08 17:06:38 +08:00

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

aihimmel

2017-03-08 17:11:20 +08:00 via Android

@a1310747 应该是的

diangdiang

2017-03-08 17:33:33 +08:00

@davinci 螺旋稳

guomiaoyou7784

2017-03-08 17:35:15 +08:00

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

hanbing135

2017-03-08 17:57:14 +08:00 via Android

面试官不懂估计懵逼了

sakurajiang

2017-03-08 19:17:07 +08:00

楼主是校招内推吗？

xiaoyao9933

2017-03-08 19:52:39 +08:00

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

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

2017-03-08 20:14:13 +08:00 via Android

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

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

2017-03-08 22:23:40 +08:00 via Android

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

mianju

2017-03-08 22:29:31 +08:00

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

bhagavad

2017-03-08 22:53:37 +08:00

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