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