53

在候选人筛选过程中，您发现哪些简单的算法或数据结构相关的“白板”问题是有效的？

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

我用于初级开发人员的基础知识之一是：

编写一个 C# 方法，该方法接受一个包含一组单词（一个句子）的字符串，并将这些单词向右旋转 X 个位置。当句子最后位置的单词被旋转时，它应该出现在结果字符串的前面。

当候选人回答这个问题时，我希望看到他们可以使用 .NET 数据结构和方法（string.Join、string.Split、List 等）来解决问题。我还寻找他们来识别优化的特殊情况。就像单词需要旋转的次数并不是真正的 X，而是 X % 的单词数。

您在面试候选人时使用了哪些白板问题，以及您在答案中寻找哪些内容（不需要发布实际答案）。

4

11 回答 11

26

我喜欢经典的“LinkedList 和 ArrayList（或链表和数组/向量之间）有什么区别，为什么要选择其中一个？”

我希望得到的答案包括以下讨论：

  • 插入性能
  • 迭代性能
  • 内存分配/重新分配影响
  • 从开头/中间/结尾删除元素的影响
  • 知道（或不知道）列表的最大大小如何影响决策
于 2008-09-12T05:25:04.220 回答
26

有一次我在大学面试微软的时候，那个人问我如何检测链表中的循环。

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

他告诉我，“不，不，每个人都给我那个解决方案。给我一个不同的解决方案。”

我认为我的解决方案是最优的。他说：“我知道这是最优的。给我一个次优的。”

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

于 2008-09-12T05:35:17.080 回答
16

最近面试的时候，经常被要求实现一个数据结构，一般是LinkedList或者HashMap。这两者都很容易在短时间内完成，但很难消除无能的人。

于 2008-09-12T12:26:11.697 回答
11

这不一定涉及 OOP 功能，但在我们上一组采访中，我们使用了从本月错误列表中选择的错误代码。看着候选人发现错误显示了他们的分析能力，显示了如何解释别人的代码

于 2008-09-24T12:05:30.700 回答
9
  1. 编写一个接受字符串的方法，如果该字符串是数字，则返回 true。（任何使用正则表达式作为面试最有效答案的方法）
  2. 请编写一个不包含开关并返回基类型为“X”的类型的抽象工厂方法。（寻找模式，寻找反射，寻找它们不回避并使用 if else if）
  3. 请用标记“|;|”分割字符串“every;thing|;|else|;|in|;|he;re”。（至少在.net中不允许使用多字符标记，所以寻找创造力，最好的解决方案是彻底破解）
于 2008-09-12T05:22:26.130 回答
8

图很困难，因为如果需要的不仅仅是算法的草图，大多数非平凡的图问题往往需要大量的实际代码来实现。很多问题往往归结为候选人是否知道最短路径和图遍历算法，是否熟悉循环类型和检测，以及他们是否知道复杂性界限。我认为很多关于这些东西的问题都归结为琐事，而不是现场的创造性思维能力。

我认为与树相关的问题往往涵盖了图形问题的大部分困难，但没有那么多的代码复杂性。

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

于 2008-09-15T14:41:03.797 回答
5

用这样的任何问题跟进：“您如何改进此代码，以便维护它的开发人员可以轻松地弄清楚它是如何工作的？”

于 2008-09-12T13:39:29.850 回答
5

实现一个函数，给定一个可能是循环的链表，交换前两个元素，第三个元素和第四个元素，等等......

于 2008-09-24T11:46:19.997 回答
4

我喜欢查看这个人实际编写的代码，并让他们向我解释。

于 2008-09-12T06:21:33.680 回答
2

一个简单的方法是让他们从头开始编写对树的广度优先搜索。是的，如果你知道你在做什么，那是微不足道的。但是很多程序员不知道如何解决它。

我觉得更有用的一个如下。我已经用多种语言给出了这个，这是一个 Perl 版本。首先，我给他们以下代码示例：

# @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;
    }
  }
}

然后我问他们以下问题。我慢慢地问他们，给人们思考的时间，并愿意给他们轻推：

  1. 这段代码完成后，@int 中的内容是什么？
  2. 这段代码投入生产，有性能问题追溯到这段代码。解释潜在的性能问题。（如果他们在苦苦挣扎，我会问如果@a 和@b 各有 100,000 个元素，需要进行多少次比较。我不是在寻找具体的术语，只是粗略估计。）
  3. 没有代码，建议加快速度。（如果他们提出了一个易于编码的方向，我会要求他们编码。如果他们想到一个解决方案会导致@int 以任何方式（例如，通常的顺序）被更改，我会推动查看他们是否意识到他们不应该在检查是否重要之前编写修复代码。）

如果他们提出了一个稍微（或非常）错误的解决方案，以下愚蠢的数据集将发现您遇到的大多数错误：

@a = qw(
  hello
  world
  hello
  goodbye
  earthlings
);
@b = qw(
  earthlings
  say
  hello
  earthlings
);

我猜大约 2/3 的候选人没有通过这个问题。我还没有遇到过遇到问题的称职程序员。我发现具有良好常识和很少编程背景的人在这方面比具有几年经验的普通程序员做得更好。

我建议将这些问题用作过滤器。不要雇用某人，因为他们可以回答这些问题。但如果他们不能回答这些问题，那就不要雇用他们。

于 2008-09-18T04:35:16.880 回答
2

要求他们为众所周知的迭代解决方案（即斐波那契等——如果需要，我们给他们一个迭代函数）编写一个递归算法，然后让他们计算它的运行时间。

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

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

于 2008-09-18T04:40:32.373 回答