Algorithm/Data Structure Design Interview Questions在候选人筛选过程中发现哪些与算法或数据结构相关的"白板"问题有效? 我有一些简单的方法可以用来验证解决问题的能力,可以简单地表达出来,但也有一些应用启发式方法的机会。 我为初级开发人员使用的基础知识之一是:
当候选人回答这个问题时,我希望看到他们可以使用.NET数据结构和方法(string.Join,string.Split,List等)来解决问题。 我还寻找它们来识别特殊情况以进行优化。 就像单词需要轮换的次数不是X一样,它是X%的单词数。 您用来面试应聘者的白板有哪些问题,以及您在答案中寻找的一些东西(不需要发布实际答案)。 一次,当我在大学为Microsoft进行面试时,那个家伙问我如何在链接列表中检测周期。 前一周在课堂上讨论了解决问题的最佳方法后,我开始告诉他。 他告诉我:"不,不,每个人都给我那种解决方案。给我一个不同的解决方案。" 我认为我的解决方案是最佳的。他说:"我知道这是最佳选择。给我一个次优选择。" 同时,这是一个很好的问题。 我喜欢经典的" LinkedList和ArrayList(或链接列表和数组/向量)之间的区别是什么,为什么选择一个或另一个?" 我希望得到的答案包括以下内容:
最近在采访时,经常有人要求我实现一个数据结构,通常是LinkedList或HashMap。两者都很容易就可以在短时间内完成,并且很难消除无能为力的情况。 这并不一定涉及OOP功能,但在我们的最后一组采访中,我们使用了"本月漏洞"列表中的一系列错误代码。看着考生发现错误,表明他们的分析能力,表明如何解释别人的代码 图形之所以困难,是因为大多数非平凡的图形问题往往需要相当数量的实际代码来实现,如果需要的不只是算法草图的话。许多原因往往取决于候选人是否知道最短路径和图形遍历算法,熟悉周期类型和检测以及他们是否知道复杂性界限。我认为有关此问题的许多问题归结为琐事,而不是现场的创造性思维能力。 我认为与树相关的问题往往可以解决大多数图形问题,但是却没有那么多的代码复杂性。 我喜欢Project Euler问题,该问题要求找到沿着树的最昂贵路径(16/67);共同的祖先是一个很好的热身者,但很多人都看到了。让某人设计一个树类,执行遍历,然后弄清楚他们可以从哪些遍历中重建一棵树,这也使我们对数据结构和算法实现有了一定的了解。 Stern-Brocot编程挑战也很有趣,并且可以在板上快速开发(http://online-judge.uva.es/p/v100/10077.html)。 实现一个函数,给定一个可能是循环的链表,该函数交换前两个元素,第三个与第四个元素交换,依此类推... 跟踪类似的问题:"如何改进此代码,以便维护它的开发人员可以弄清楚它的工作原理?" 我喜欢阅读该人实际编写的代码,然后让他们向我解释。 让他们为一个众所周知的迭代解决方案(即Fibonacci等)编写一个递归算法,如果需要的话,我们给他们一个迭代函数,然后让他们计算它的运行时间。 递归函数很多时候都涉及树数据结构。这个人未能认识到我的次数令我感到困惑。在您看到它是树结构之前,计算运行时间变得有点困难... 我发现这个问题涉及很多领域。即,它们的代码读取能力(如果给了它们迭代功能),代码编写能力(因为他们编写了递归函数),算法,数据结构(用于运行时)... 一个琐碎的事情是让他们从头开始编写对树的广度优先搜索。是的,如果您知道自己在做什么,那是微不足道的。但是很多程序员都不知道如何解决它。 我发现仍然更有用的一种方法如下。我已经用多种语言给出了此信息,这是Perl版本。首先,我给他们以下代码示例:
然后我问他们以下问题。我慢慢地问他们,给人们时间思考,并愿意给他们一些微调: 如果他们提出了一个(或非常)错误的解决方案,那么以下愚蠢的数据集将发现您遇到的大多数错误:
我猜大概有2/3的候选人未能通过这个问题。我还没有遇到一个有能力的程序员对此感到麻烦。我发现具有良好常识和很少编程背景的人在这方面的经验要比具有几年经验的普通程序员要好。 我建议使用这些问题作为过滤器。不要雇用别人,因为他们会回答这些问题。但是,如果他们不能回答这些,那就不要雇用他们。 |