最糟糕的编程面试题

多年前,我写了一篇关于我所鄙视的某些类型的面试题。今天我想讨论一个更具体的问题,而不仅是类型。我从来没有问过自己这个问题,但我已经看有人在实际面试中提这个问题,我正式提名它为最糟糕的编程面试题。

在之前的公司里,有个同事经常问这个问题,那次是我第一次在面试时听到它。这家公司结对面试,两个工程师,一个候选人。有一天,我和他作为一对,去面试一些杯具的应聘者。我觉得应聘者其实表现不错,然后我的同事抛出了这个问题。应聘者结结巴巴地回答,很明显他囧了。在面试后的聚会,所有面试他的工程师都向他竖起了大拇指,只有我搭档反对雇用他,只因“任何称职的工程师都应该能够回答它”。他确凿地说不能跟那个人共存。值得一提的是,这个故事有个大团圆结局,我们不顾我搭档的抗议,还是招了那个人,并在几个月内炒了我搭档,而那个应聘者仍在那家公司,干得好好的。

无论如何,我认为有这个问题的面试都是“有问题”的,所以我想在这里说明为什么它几乎是恐怖的一个面试题:

写一个能检测链表是否存在环路的函数。

看来像是的基本算法问题,对吗?站起来,在白板上写函数。很正常,对吗?不是,这是不对的,别这么干。

1.这完全是不恰当的。

这是一个工作面试。你有一个实时的环境,跟你说话的人在面试着。紧张是很正常的。而那种带有“灵关一闪”的智力题是最坏的问题。你的大脑将致力于思考“该死,我正搞砸这个面试”而不是关注手边的问题。

人们喜欢“看到应聘者如何思考”,但智力题无助于此。正因为它是智力题。你只能希望智力题给你“恍然大悟”。有时我听到人们想知道应聘者如何处理压力,但你应该知道,面试中本来就是有压力的。

问人难题完全是浪费时间,这样做只是考察到应聘者以前有没看过这题。或者说考察了他们的演技(当他们听说过这问题并知道答案却假装没听说,然后装模作样逐步推导以得出答案)。

这条问题是最浪费时间的。你还问为什么?好,想象一下如果一个人真的是第一次听到这个问题,然后你期望他推出答案。

对于这条题,一般来说的“正确”的答案是龟兔算法,在链表头放两个指针,一个是一步走两个节点,另一个则一步一点;如果走着走着指针指向同一个节点,那就代表有环路了。

当然,还有更简单的答案,例如,将所有走过的节点标记为“走过”,或者从每个点出发,看能不能回答该点,又或者在遍历过程中做哈希,看有没有重复。但当你抛出这些答案时,面试官又会加条件,要求使用更少的内存或时间或不能改原本的数据结构。而最佳的答案就是龟兔。

是否一开始就该考虑到这么多?无论如何,看来你很觉得你能考虑周到。链表这种数据结构是1955年由Allen Newell,Cliff Shaw 和 Herbert A. Simon 发现的。而“正确”的链表环路检测算法,则叫做“Floyd 环查找算法”,以纪念发现者Robert W. Floyd,那是1967年的事。

1955至1967之间,这个问题是开放的,就是说,无数考数学或计算机博士的人都可能将它写进论文里。即使那么多人在钻研着,这个问题还是12年无解。

你真的觉得你行吗,用20分钟,仅凭超越所有学者的压力,搞定这个曾经12年无解的难题?看来是不行的,你觉得行,只不过是因为你看过答案,然后在面试中,你”似曾相识“、”灵关一闪“。

2.这完全是不切实际的

如果上面给的理由还不能让你耻笑那个烂问题,那你再想想,这个问题是否真的有用于日常工作。

我的意思是:你怎么会在实际中碰到有环的链表?

我并不是说叫你故意搞出一个有指回自身的链表,而是说,无端端会有这样的东西?

链表这种数据结构不是抽象的东西,栈或队列才是,你或者会在一些抽象的数据结构中用到链表这种实在的东西。例如栈,你就用来压入,弹出,查看,是吧?那怎么会造成环呢?没有人想把它搞成一团的吧?

即使你自己写个链表,你也不会想做出这种样子。看下java的LinkedList类,你是无法从外部去操控它的next和prev的,你只能取得第一个或最后一个,添加节点到某一位置,按位置或值删除节点。

看下java源码就知道,真的没有:

它是一个私有静态类,你无法从外部实例化它。你不能直接操控next和prev,因为它们俩代表了链表的状态,它们就该这样被封装起来。

如果你真的把链表搞成有环了,那说明你写错。写错的话,你最好重新写对它,而不是写个“检测环”的方法。

“检测环”的方法就该这样写:

如果你的链表写对的话,“龟兔算法”返回的结果也跟这个方法一样。

现实中你是很少有机会亲手写个链表的,即使有,你也别写个能造成环的方法。造成环的方法,只能是“留后门”,“元编程”,“反射”。既然是这样故意的话,那么绕过你的“检测环”也是轻而易举的。

结论

很多面试题,都中了以上其中一点,太过困难或者与工作无关。

而这个问题,两点都中了。

如果有人给到你满意的答案,就说明那个人死记硬背,无他。因回答不了而被你否决的人,说不定还比你更适合这份实务。

链表环路检测:别问了。

更新:有位评论者说如果问题问的是有向图,且每个节点的出度最多只有,即是问“检测这个有向图有没有环”。搞图的话,你确实可能会向API用户提供修改每点的指向的方法,这看上去符合实际。但是,还是那句话,你只是在考察应聘者把CS课程记住了多少,或者你只想随便问问,又或者你想听听他说除了龟兔算法以外的低效算法。

2 收藏 10 评论

关于作者:unblock

简介还没来得及写 :) 个人主页 · 我的文章 · 1

相关文章

可能感兴趣的话题



直接登录
最新评论
  • pluiefox   2014/07/15

    很有道理,可惜不是所有的面试官都是这么想的。

  • 被问过的飘过,原来用龟兔算法!

  • 链表这种数据结构是1955年由Allen Newell,Cliff Shaw 和 Herbert A. Simon 发现的。而“正确”的链表环路检测算法,则叫做“Floyd 环查找算法”,以纪念发现者Robert W. Floyd,那是1967年的事。

    1955至1967之间,这个问题是开放的,就是说,无数考数学或计算机博士的人都可能将它写进论文里。即使那么多人在钻研着,这个问题还是12年无解。

    你真的觉得你行吗,用20分钟,仅凭超越所有学者的压力,搞定这个曾经12年无解的难题?

  • 好的面试题不在于它有多难,而在于区分度。

  • hello   2014/07/16

    很多时候面试官自己也不懂,就知道个标准答案。。但是标准答案的水平和面试官自身的水平有一段空白区,如果你落在这个空白区了,面试官就无从判断。

  • Edward Shen   2014/07/17

    经常遇到这类面试官。 通过这样的面试的人,只是做更多准备的人而已。
    我喜欢面试时问一些知识,解决问题的思路,而不是具体的无错代码。
    毕竟,工作是开卷考试,而不是闭卷考试。

  •   2014/08/13

    能回答上来,固然能说明水平达到一定境界了,可是面试官应该意识到,自己是在面试能来公司上班的同事,不是在找“世界编程奥林匹克锦标赛”的冠军人选。找同事会有一堆人选,找冠军,只能找到一个,还不一定能不能找到。

  • lee   2014/09/02

    。。。我微软二面那个考官就问了我如何检测这个有向图有没有环。。。

  • 是的,深有体会

  • 遍历链表,死机了就说明是。

跳到底部
返回顶部