吐槽一下 今日头条的面试

[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

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

[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