最糟糕的编程面试题

  1. 云栖社区>
  2. seven的测试人生>
  3. 博客>
  4. 正文

最糟糕的编程面试题

青衫无名 2017-07-03 16:10:00 浏览2389
展开阅读全文
多年前,我写了一篇关于我所鄙视的某些类型的面试题。今天我想讨论一个更具体的问题,而不仅是类型。我从来没有问过自己这个问题,但我已经看有人在实际面试中提这个问题,我正式提名它为最糟糕的编程面试题。
  在之前的公司里,有个同事经常问这个问题,那次是我第一次在面试时听到它。这家公司结对面试,两个工程师,一个候选人。有一天,我和他作为一对,去面试一些杯具的应聘者。我觉得应聘者其实表现不错,然后我的同事抛出了这个问题。应聘者结结巴巴地回答,很明显他囧了。在面试后的聚会,所有面试他的工程师都向他竖起了大拇指,只有我搭档反对雇用他,只因“任何称职的工程师都应该能够回答它”。他确凿地说不能跟那个人共存。值得一提的是,这个故事有个大团圆结局,我们不顾我搭档的抗议,还是招了那个人,并在几个月内炒了我搭档,而那个应聘者仍在那家公司,干得好好的。
  无论如何,我认为有这个问题的面试都是“有问题”的,所以我想在这里说明为什么它几乎是恐怖的一个面试题:
  写一个能检测链表是否存在环路的函数。
  看来像是的基本算法问题,对吗?站起来,在白板上写函数。很正常,对吗?不是,这是不对的,别这么干。
  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源码就知道,真的没有:
private static class Entry <E> {
E element;
java.util.LinkedList.Entry<E> next;
java.util.LinkedList.Entry<E> previous;
Entry(E e, java.util.LinkedList.Entry<E> entry, java.util.LinkedList.Entry<E> entry1) {
/* compiled code */
}
}
  它是一个私有静态类,你无法从外部实例化它。你不能直接操控next和prev,因为它们俩代表了链表的状态,它们就该这样被封装起来。
  如果你真的把链表搞成有环了,那说明你写错。写错的话,你最好重新写对它,而不是写个“检测环”的方法。
  “检测环”的方法就该这样写:
public class LinkedList {
public boolean containsCycle() {
return false;
}
}
  如果你的链表写对的话,“龟兔算法”返回的结果也跟这个方法一样。
  现实中你是很少有机会亲手写个链表的,即使有,你也别写个能造成环的方法。造成环的方法,只能是“留后门”,“元编程”,“反射”。既然是这样故意的话,那么绕过你的“检测环”也是轻而易举的。
  结论
  很多面试题,都中了以上其中一点,太过困难或者与工作无关。
  而这个问题,两点都中了。
  如果有人给到你满意的答案,就说明那个人死记硬背,无他。因回答不了而被你否决的人,说不定还比你更适合这份实务。
  链表环路检测:别问了。
  更新:有位评论者说如果问题问的是有向图,且每个节点的出度最多只有,即是问“检测这个有向图有没有环”。搞图的话,你确实可能会向API用户提供修改每点的指向的方法,这看上去符合实际。但是,还是那句话,你只是在考察应聘者把CS课程记住了多少,或者你只想随便问问,又或者你想听听他说除了龟兔算法以外的低效算法。


最新内容请见作者的GitHub页:http://qaseven.github.io/

网友评论

登录后评论
0/500
评论
青衫无名
+ 关注
所属团队号: seven的测试人生