上周去今日头条面试。其中一道算法题的预处理步骤需要用到链表逆置。我写了一个递归函数。
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
结果面试官看了几分钟，没看懂觉得有问题。然后我用数学归纳法简要地证明了一下这个算法的正确性，他想了几分钟还是觉得有问题，然后我又举了一两个简单例子展示该算法的运行过程，他看了一会儿想了一会儿还是觉得不对劲。末了，他叫我在这等一会，便抱着电脑出去了。我在屋子里等了半天也不见人影，大概过了有半小时，我走出面试房间，看到他，他说今天就面到这了。想想也是有些无语。
 |
valuedluteMar 8, 2017
1
确实是对的。
看起来面试官希望的是非递归的实现。估计当时没看懂。 |
 |
nagatoMar 8, 2017
2
对的吧，面试官说哪不对了？
|
 |
nbndcoMar 8, 2017
3
其实这种应用用递归不是很合适。
当然这个面试官自己都弄不明白我觉得…… |
 |
4
为什么我看到今日头条就想黑一下呢
|
 |
5
《震惊，面试官居然看不懂递归排序，全世界的程序员都哭了》
你不起个这种标题，过的了技术面，也过不了 HR 面。 PS ：我感觉面试官当时脑子里有别的事，一时懵逼了，之后也是去干别的事了。 |
 |
6
面试官说你不按常理出牌，我只背了迭代实现，你写个递归，我。。。
|
 |
jackisnotspirateMar 8, 2017
7
呵呵，当年面试小米我也写了个二分查找的递归，然后也面试官说不对。。。
|
 |
serverMar 8, 2017
8
坐等面试官
|
 |
airqjMar 8, 2017
9
靠!
不就是工作久了忘了吗？ 你小子至于拿到这来让我丢人现眼吗 ：） |
 |
eamon666Mar 8, 2017
10
面试的时候切忌和面试官争论 毕竟你的目的是拿到 OFFER 你对了有什么用？
高风亮节的人真的已经不多了 |
 |
zerMar 8, 2017
11
楼上是当事人现身说法？
|
 |
dogfeetMar 8, 2017
12
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 ，写成这样是不是对的呀？ |
 |
dbddMar 8, 2017
14
面试为啥要写递归，如果他不懂他就不会觉得你正确，如果他不觉得你正确你就有可能拿不到 offer 。。。
当面写代码其实对面试官压力更大。。。 |
 |
imn1Mar 8, 2017
15
这帖应该是今日头条
|
 |
MiranaMar 8, 2017
17
这种递归栈太深了
|
 |
18
我很少写递归的原因是，我写程序都会下意识的在脑子里面跑一遍。
如果写递归，我感觉我脑子就如同 stackoverflow 了一样难受。 所以我很少写，要写递归都是要下意识的告诉自己不要把这个程序放到脑子里面跑，不然就是炸裂一般的痛苦。 |
|
dogfeetMar 8, 2017
20
@davinci 不是 2 个版本哟，是一个。本意是， head == None 只需要第一次判断一次， head.nex = None 只需要最后递归完后原先的头节点执行一次。中间递归的过程中可以省略这 2 步。所以 reverse 调用的 reverseImpl 。
不过可能有问题吧，没装 py 环境没试 :( |
 |
jmc891205Mar 8, 2017
23
说句题外话 我觉得出 Python 面试题的时候应该尽量不要涉及链表
Python 对于任何链表适合解决的问题 都有其他更方便的数据结构可以用 |
 |
25
震惊！今日头条招人黑幕，技术面试官竟然做出如此事情。。。
|
 |
28
@dogfeet
def reverse(head): pre = None while head is not None: next = head.next head.next = pre pre = head head = next return pre 会不会这样更好一点.. |
 |
ming2050Mar 8, 2017 via iPhone
29
如果只是实现功能，递归毫无问题吧。
ps.话说楼上怎么有的扯到排序了 |
 |
tiancaiamaoMar 8, 2017
30
@dbdd 不不不，当面写代码还是面试者压力大一些，心态不一样。
|
 |
31
@tiancaiamao 完全同意。
|
 |
uuweZhouMar 8, 2017
32
这种面试官...水平会不会太次
单链表逆序的递归实现这种比较基础的题都... 补充一个 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; } ``` |
 |
lekai63Mar 8, 2017
33
非程序员。。看了下这代码。。感觉跟那个解汉诺塔的算法一样~~
|
 |
lghMar 8, 2017 via iPhone
34
为什么一直没人说 == None 这个判断，不是应该用 is None 么？
|
 |
GG668v26Fd55CP5WMar 8, 2017 via iPhone
36
只有我觉得他出去是找个 case 运行了一下代码吗？
|
 |
37
这种做法是不是存在两个问题：
1 ）如上面某位说的，栈递归太深了。递归次数多了执行的时候会报错。 2 ）性能问题：你这种做法相当于，每次递归在函数栈上申请了一个临时变量，用这个临时变量指向当前递归的链表上的节点。等递归一个一个退栈的时候，通过索引这些临时变量把链表反向串起来。这种做法内存和时间的开销是不是比较大。 |
 |
linbiayeMar 8, 2017
38
@000wangxinyu000 说得对，性能都是其次，主要问题是链表长了这个程序就得跪。
|
|
40
|
 |
wshcdrMar 8, 2017
41
然后我用数学归纳法简要地证明了一下这个算法的正确性
我比较好奇，帖主是如何用数学归纳法来证明算法的正确性的。算法没问题， |
|
wshcdrMar 8, 2017
43
@000wangxinyu000 时间复杂度 O(n)空间复杂度 O （ n ），算法本身没啥问题
|
|
44
@wshcdr 假设链表长度为 k 时，算法正确。根据该算法易证长度为 k+1 时算法依然正确。
当长度为 1 时，算法显然正确。所以为 2 时也正确，为 3 时也正确。。。为 n 时也正确 n 为任意正整数 |
 |
Em5O7B1JGfjQnBryMar 8, 2017 via Android
45
震惊 。。。居然有人用 Python 写递归， scheme 看了会沉默， haskell 看了会流泪。。。
|
 |
FelldeadbirdMar 8, 2017
46
坐等：《我就是面试楼主的面试官，当时有事……》
|
 |
dfguoMar 8, 2017
47
个人认为公司不应该随便派人面试。面试官需要的技能比面试者高很多。一不小心就会这样了。。。
|
 |
pwcongMar 8, 2017
48
特意画图研究了下
1->2 1->2 ↑---↓ 1 2 ↑---↓ 666 ，感谢楼主让我这个菜鸟学到了逆置列表的新姿势ε=ε=ε=┏(゜ロ゜;)┛ |
 |
dubaiwanMar 8, 2017
51
没看上你呗，招人除了技术能力过硬，最主要的还是喜欢对方
|
 |
diangdiangMar 8, 2017
52
弱弱问一句，是不是只要
if (head.next == null) return head; 就可以了? 感觉 head.next == null 会在 head == null 前出现， head == null 没用到啊？ |
 |
superleexpertMar 8, 2017
53
楼上说对啦~~
|
|
54
|
 |
luckymore0520Mar 8, 2017
55
表示上周末刚去头条面试，前后聊了 4 个人 8 个多小时，体验很不错。。。
再看楼主，怎么感觉 =.= 我感觉这个面试官要被查水表了。。。 |
|
superleexpertMar 8, 2017
56
@davinci 楼上的楼上
|
|
57
@luckymore0520 面试官被查水表不大可能吧。这也不是我的本意。我已经有其它公司的 offer 了，就是纯粹吐槽一下。感觉那天表现也不大好，即使面试官秒懂了我的思路，也不是稳拿 offer 。另外聊了 8 个多小时这么久感觉好夸张。。。
|
 |
lytofbMar 8, 2017
58
head.next.next = head
这块改一下就好了，改成下面这样。 nexthead = head.next nexthead.next = head 不过招人就是这样，包括很多事情都是这样的，做了正确的事，其实不一定会得到正确的结果 |
 |
ibufuMar 8, 2017
59
这不就是 leetcode 上的题目么
|
 |
yuankuiMar 8, 2017
61
"把链表逆置"这种操作就跟"把汽车翻过来"一样
看起来好像很牛逼的样子,实际上没什么鸟用.. |
 |
irenicusMar 8, 2017
62
没毛病
|
 |
yanchao7511461Mar 8, 2017
64
首先..我觉得链表逆序其实没啥好考的...其次我觉得 lz 写的是对的.... 虽然 head.next.next = head 这里不好理解。但理解了就很清晰了。面试官有点蠢..... 不过面试确实是运气的成分更大。
|
 |
CloudnuYMar 8, 2017
65
大概是你的变量名没有叫 amazing ！！！、 shocking ！！！
|
|
diangdiangMar 8, 2017
67
@davinci 螺旋稳
|
 |
guomiaoyou7784Mar 8, 2017
68
面试官没看懂，可以要求跑几个 test case 。或者手动模拟一遍。感觉楼主被面试官坑了
|
 |
hanbing135Mar 8, 2017 via Android
69
面试官不懂估计懵逼了
|
 |
sakurajiangMar 8, 2017
70
楼主是校招内推吗？
|
 |
xiaoyao9933Mar 8, 2017
71
怎么觉得这种递归下去的调用栈，比直接复制个新链表的开销还要大。。哪位大神给我讲讲内存开销呗？
|
 |
danielmiaoMar 8, 2017
72
个人感觉用 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 ，我猜是对的 |
 |
lsmgeb89Mar 8, 2017 via Android
73
这个递归第一次看确实有点绕，但也不至于跑了 case 都看不懂。
|
|
danielmiaoMar 8, 2017
74
不会贴代码。。。。。
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 |
 |
JimrussellMar 8, 2017 via Android
75
听说今日头条的面试是国内大厂里平均最难的…看了这个帖子我只是觉得这个面试官没连刷过 leetcode ，链表逆置用递归在面试题里是很常见的考法。
|
 |
bhagavadMar 8, 2017
77
大概三年前去面过一次头条，一面搞了两个小时，还是周六，能看出面试官还是挺不错的，因为下午直接接了前东家的 offer ，就没有再去二面。
两年前从前东家离职时直接又给原来的面试官发了简历，又去面了一次。笔试同样是链表翻转，我用 C++ 写的，结果新面试官直接说不会 C++，当时就有种“卧槽，这都行？”的感受，具体细节记不清了，但是只记得对面试官印象极差，一是把控不了整个面试过程，二是技术水平极差，就是一个个子不算高，稍微有点胖的哥们，年龄不大，应该工作没几年。还有最受不了的是二面的时间间隔，没有任何人告诉我需要等多长时间，我印象中去门口前台问了三四次需要多长时间，每次间隔应该都是半小时左右的，然后二面面试官才过来。上来就牛逼哄哄的说你原来做过阅读是吧，阅读排版具体是怎么做的？剩下的其他问题都忘了，唯一记得的就是没有问任何 Android 相关的东西。 应该是头条人太多了，所以也良莠不齐，自那以后再也没去面过头条，以后也不会再去了。 |
 |
smallSohoSoloMar 8, 2017 via Android
78
中肯的说，你确定你挂在了这道题上？
|
 |
song4Mar 8, 2017
79
算法没毛病，给出归纳法证明更是加分项。
很多面试官心里想得不是面试你这个人，而是百般刁难你并以此展示自己的牛逼。如果遇到这种面试官，而你又让他吃相太难看，那你肯定挂了。 面试是一个偶然性相当大的事情，要看开啊。 |
 |
ssoftlnsMar 9, 2017
80
看来面试官是个不懂装懂的傻 x
|
 |
icenyMar 9, 2017
81
大厂么
|
 |
mingyunMar 9, 2017
82
今日头条算大厂，虽然我没用过
|
 |
wuyadongMar 9, 2017
83
前段时间，我也面过今日头条。确实能感觉到面试官的水平没有那么好。
|
 |
dddddyyyySep 28, 2017
84
楼主最后去哪了？
|
 |
markxFeb 5, 2018
86
我正好想问个问题， 关于面试的题目， 大家通常会优先用递归还是迭代啊？ 我现在用递归总觉得心里有点障碍，总担心面试官会说空间上效率不够高，让我再用迭代写一次。
|
2
其他两者没区别吧
Select Language