算法/数据结构设计面试问题
我们在候选人筛选过程中发现哪些与算法或者数据结构相关的"白板"问题有效？
我有一些简单的方法可以用来验证解决问题的能力，可以简单地表达出来，但也有一些应用启发式方法的机会。
我为初级开发人员使用的基本知识之一是：
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％的单词数。
我们用来面试候选人的白板有哪些问题，以及我们在答案中寻找的一些东西(不需要发布实际答案)。
解决方案
回答
- 编写一个接受字符串的方法，如果该字符串是一个数字，则返回true。(使用正则表达式作为面试最有效的答案)
- 请编写一个抽象工厂方法，该方法不包含开关，并且返回基本类型为" X"的类型。 (寻找图案，寻找反射，寻找不回避的步骤，并使用if if if)
- 请用标记" |; |"将字符串" every; thing |; | else |; || in |; | he; re"分开。((。net中至少不允许使用多字符标记，因此要寻找创造力，最好的解决方案是彻底破解)
回答
我喜欢经典的" LinkedList和ArrayList(或者链表和数组/向量)之间的区别是什么，为什么选择一个或者另一个？"
我希望这种答案包括以下方面的讨论：
- 插入性能
- 迭代性能
- 内存分配/重新分配影响
- 从开头/中间/结尾删除元素的影响
- 知道(或者不知道)列表的最大大小如何影响决策
回答
有一次，当我在大学为Microsoft进行面试时，那个家伙问我如何在链表中检测一个周期。
在前一周的课堂上讨论了该问题的最佳解决方案后，我开始告诉他。
他告诉我："不，不，每个人都给我那种解决方案。给我一个不同的解决方案。"
我认为我的解决方案是最佳的。他说："我知道这是最佳选择。给我一个次优选择。"
同时，这是一个很好的问题。
回答
我喜欢阅读该人实际编写的代码，并请他们向我解释。
回答
最近在面试时，经常有人要求我实现一个数据结构，通常是LinkedList或者HashMap。两者都很容易就可以在短时间内完成，并且很难消除无能为力的情况。
回答
跟进这样的问题："我们如何改进此代码，以便维护它的开发人员可以弄清楚它的工作原理？"
回答
图形之所以困难，是因为大多数非平凡的图形问题往往需要相当数量的实际代码来实现，如果需要的不只是一个算法的草图的话。很多原因都取决于候选人是否知道最短路径和图形遍历算法，是否熟悉循环类型和检测以及他们是否知道复杂性界限。我认为，关于这些问题的很多问题归结为琐事，而不是现场的创造性思维能力。
我认为与树相关的问题往往可以解决大多数图形问题，但是却没有那么多的代码复杂性。
我喜欢欧拉计画(Project Euler)问题，该问题要求找到一棵树上最昂贵的路径(16/67)；共同的祖先是一个很好的热身者，但很多人都看过它。要求某人设计一个树类，执行遍历，然后弄清楚他们可以从哪些遍历中重建树，这也使我们对数据结构和算法实现有了一定的了解。 Stern-Brocot编程挑战也很有趣，并且可以在板上快速开发(http://online-judge.uva.es/p/v100/10077.html)。
回答
一个琐碎的事情是要求他们从头开始编写对树的广度优先搜索。是的，如果我们知道自己在做什么，那是微不足道的。但是很多程序员都不知道如何解决它。
我发现仍然更有用的一种方法如下。我已经用多种语言给出了此信息，这是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;
}
}
}
然后我问他们以下问题。我慢慢地问他们，让人们有时间思考，并愿意给他们一些微调：
- 完成此代码后，@ int中的内容是什么？
- 该代码投入生产，并且存在性能问题，可以追溯到该代码。解释潜在的性能问题。 (如果他们苦苦挣扎，我会问，如果@a和@b分别具有100,000个元素，那么需要进行多少次比较。我不是在寻找特定的术语，只是信封估计的倒数。)
- 如果没有代码，建议加快速度。 (如果他们提出了易于编码的方向，我将请他们进行编码。如果他们想到了一种会导致@int以任何方式(例如，通常的顺序)更改的解决方案，那么我将着眼于他们是否意识到在检查是否重要之前不应该编写此修复程序。)
如果他们提出了一个(或者非常)错误的解决方案，那么以下愚蠢的数据集将发现我们遇到的大多数错误：
@a = qw( hello world hello goodbye earthlings ); @b = qw( earthlings say hello earthlings );
我猜大概有2/3的候选人未能通过这个问题。我还没有遇到一个有能力的程序员对此感到麻烦。我发现具有良好常识和很少编程背景的人员在这方面的经验要比具有几年经验的普通程序员要好。
我建议使用这些问题作为过滤器。不要雇用别人，因为他们会回答这些问题。但是，如果他们无法回答这些问题，那就不要雇用他们。
回答
要求他们为一个著名的迭代解决方案(例如Fibonacci等)编写一个递归算法，如果需要，我们给他们一个迭代函数，然后让他们计算运行时间。
很多时候，递归函数都涉及树数据结构。这个人未能认识到我的次数令我感到困惑。在我们看到它是树结构之前，计算运行时间变得有点困难。
我发现这个问题涉及很多领域。即，它们的代码读取能力(如果给了它们迭代功能)，代码编写能力(因为他们编写了递归函数)，算法，数据结构(用于运行时)...
回答
实现一个函数，给定一个可能是循环的链表，该函数交换前两个元素，将第三个元素交换为第四个元素，依此类推...
回答
这并不一定涉及OOP功能，但是在我们的最后一组采访中，我们使用了"本月漏洞"列表中的一系列错误代码。看着考生发现错误，表明他们的分析能力，表明如何解释别人的代码
