算法/数据结构设计面试题

算法/数据结构设计面试题

Algorithm/Data Structure Design Interview Questions

在候选人筛选过程中发现哪些与算法或数据结构相关的"白板"问题有效?

我有一些简单的方法可以用来验证解决问题的能力,可以简单地表达出来,但也有一些应用启发式方法的机会。

我为初级开发人员使用的基础知识之一是:

Write a C# method that takes a string which contains a set of words (a sentence) and rotates those words X number of places to the right. When a word in the last position of the sentence is rotated it should show up at the front of the resulting string.

当候选人回答这个问题时,我希望看到他们可以使用.NET数据结构和方法(string.Join,string.Split,List等)来解决问题。 我还寻找它们来识别特殊情况以进行优化。 就像单词需要轮换的次数不是X一样,它是X%的单词数。

您用来面试应聘者的白板有哪些问题,以及您在答案中寻找的一些东西(不需要发布实际答案)。


一次,当我在大学为Microsoft进行面试时,那个家伙问我如何在链接列表中检测周期。

前一周在课堂上讨论了解决问题的最佳方法后,我开始告诉他。

他告诉我:"不,不,每个人都给我那种解决方案。给我一个不同的解决方案。"

我认为我的解决方案是最佳的。他说:"我知道这是最佳选择。给我一个次优选择。"

同时,这是一个很好的问题。


我喜欢经典的" LinkedList和ArrayList(或链接列表和数组/向量)之间的区别是什么,为什么选择一个或另一个?"

我希望得到的答案包括以下内容:

  • 插入性能
  • 迭代性能
  • 内存分配/重新分配影响
  • 从开头/中间/结尾删除元素的影响
  • 知道(或不知道)列表的最大大小如何影响决策


最近在采访时,经常有人要求我实现一个数据结构,通常是LinkedList或HashMap。两者都很容易就可以在短时间内完成,并且很难消除无能为力的情况。


这并不一定涉及OOP功能,但在我们的最后一组采访中,我们使用了"本月漏洞"列表中的一系列错误代码。看着考生发现错误,表明他们的分析能力,表明如何解释别人的代码


  • 编写一个接受字符串的方法,如果该字符串是一个数字,则返回true。(使用正则表达式作为面试最有效的答案)
  • 请编写一个抽象工厂方法,该方法不包含开关,并且返回基本类型为" X"的类型。 (寻找模式,寻找反射,寻找它们不退一步,并使用if if if)
  • 请用符号" |; |"将字符串" every; thing |; | else |; || in |; | he; re"分开。((。net中至少不允许使用多字符令牌,因此,寻找创造力,最好的解决方案是彻底破解

  • 图形之所以困难,是因为大多数非平凡的图形问题往往需要相当数量的实际代码来实现,如果需要的不只是算法草图的话。许多原因往往取决于候选人是否知道最短路径和图形遍历算法,熟悉周期类型和检测以及他们是否知道复杂性界限。我认为有关此问题的许多问题归结为琐事,而不是现场的创造性思维能力。

    我认为与树相关的问题往往可以解决大多数图形问题,但是却没有那么多的代码复杂性。

    我喜欢Project Euler问题,该问题要求找到沿着树的最昂贵路径(16/67);共同的祖先是一个很好的热身者,但很多人都看到了。让某人设计一个树类,执行遍历,然后弄清楚他们可以从哪些遍历中重建一棵树,这也使我们对数据结构和算法实现有了一定的了解。 Stern-Brocot编程挑战也很有趣,并且可以在板上快速开发(http://online-judge.uva.es/p/v100/10077.html)。


    实现一个函数,给定一个可能是循环的链表,该函数交换前两个元素,第三个与第四个元素交换,依此类推...


    跟踪类似的问题:"如何改进此代码,以便维护它的开发人员可以弄清楚它的工作原理?"


    我喜欢阅读该人实际编写的代码,然后让他们向我解释。


    让他们为一个众所周知的迭代解决方案(即Fibonacci等)编写一个递归算法,如果需要的话,我们给他们一个迭代函数,然后让他们计算它的运行时间。

    递归函数很多时候都涉及树数据结构。这个人未能认识到我的次数令我感到困惑。在您看到它是树结构之前,计算运行时间变得有点困难...

    我发现这个问题涉及很多领域。即,它们的代码读取能力(如果给了它们迭代功能),代码编写能力(因为他们编写了递归函数),算法,数据结构(用于运行时)...


    一个琐碎的事情是让他们从头开始编写对树的广度优先搜索。是的,如果您知道自己在做什么,那是微不足道的。但是很多程序员都不知道如何解决它。

    我发现仍然更有用的一种方法如下。我已经用多种语言给出了此信息,这是Perl版本。首先,我给他们以下代码示例:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    # @a and @b are two arrays which are already populated.
    my @int;
    OUTER: for my $x (@a) {
      for my $y (@b) {
        if ($x eq $y) {
          push @int, $x;
          next OUTER;
        }
      }
    }

    然后我问他们以下问题。我慢慢地问他们,给人们时间思考,并愿意给他们一些微调:

  • 完成此代码后,@ int中有什么?
  • 该代码投入生产,并且性能问题可以追溯到该代码。解释潜在的性能问题。 (如果他们苦苦挣扎,我会问如果@a和@b分别具有100,000个元素,那么需要进行多少次比较。我不是在寻找特定的术语,只是信封估计的倒数。)
  • 如果没有代码,建议加快速度。 (如果他们提出了一个易于编码的方向,我将请他们进行编码。如果他们想到了一种解决方案,该解决方案将导致@int以任何方式(例如,通常的顺序)发生变化,我将努力了解他们是否意识到在检查是否重要之前不应该编写此修复程序。)
  • 如果他们提出了一个(或非常)错误的解决方案,那么以下愚蠢的数据集将发现您遇到的大多数错误:

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    @a = qw(
      hello
      world
      hello
      goodbye
      earthlings
    );
    @b = qw(
      earthlings
      say
      hello
      earthlings
    );

    我猜大概有2/3的候选人未能通过这个问题。我还没有遇到一个有能力的程序员对此感到麻烦。我发现具有良好常识和很少编程背景的人在这方面的经验要比具有几年经验的普通程序员要好。

    我建议使用这些问题作为过滤器。不要雇用别人,因为他们会回答这些问题。但是,如果他们不能回答这些,那就不要雇用他们。


    推荐阅读