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

您在候选筛选过程中发现哪些简单的算法或数据结构相关的"白板"问题？

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

我用于初级开发人员的基础之一是:

编写一个C#方法,它接受一个包含一组单词(一个句子)的字符串,并将这些单词X向右旋转.当句子的最后位置中的单词被旋转时,它应该显示在结果字符串的前面.

当候选人回答这个问题时,我会看到他们可以使用.NET数据结构和方法(string.Join,string.Split,List等)来解决问题.我也寻找他们来确定优化的特殊情况.就像需要旋转的单词实际上不是X的次数一样,它是X%的单词数.

您用来采访候选人的白板问题是什么？您在答案中寻找的是什么(不需要发布实际答案).

1> David Citron..：

---

我喜欢经典的"LinkedList和ArrayList之间的区别(或链接列表和数组/向量之间的差异),为什么你会选择其中一个？"

我希望的答案包括以下讨论:

插入性能

迭代性能

内存分配/重新分配影响

从开头/中间/结尾删除元素的影响

如何知道(或不知道)列表的最大大小会影响决策

---

@AksharPrabhuDesai - 我不建议阅读该链接博客条目作为了解LinkedList与ArrayList的好方法.作者做了一些误导性的陈述(特别是关于ArrayList调整大小的行为)并省略了一些关键点(其中一些关键点由Stephen Colebourne在博客评论中公认).

---

@DavidCitron你能指出一些博客/文章,其中包括你在下面的答案中讨论的所有要点.

2> Jim Puls..：

---

有一次,当我在大学面试微软时,那家伙问我如何检测链表中的循环.

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

他告诉我,"不,不,每个人都给我解决方案.给我一个不同的解决方案."

我认为我的解决方案是最佳的.他说,"我知道这是最优的.给我一个次优的."

与此同时,这是一个非常好的问题.

---

我会说,哈希节点的地址,并将它们放在地图中.如果遇到已映射的节点.答对了!.

---

+1这是什么教训!我认为他们更关心你如何得出答案,而不是答案本身,最佳与否.

---

是的,但这需要额外的O(N)内存.

---

另一种方法是简单地保持一个开始和一个当前指针.当前电流从(从开始到结束)移动并开始在开始和当前之间移动.对于每次电流迭代,检查start和current之间的所有节点.如果next遇到null,则没有循环,如果next等于start,那么我们有一个循环

---

如果您知道链接列表的大小n,只需按照链接递增计数器即可.如果计数器转到n + 1而不是列表大小,那么有一个循环,你可以停止.否则你将停在n.

3> Bill the Liz..：

---

在最近的采访中,我经常被要求实现一个数据结构,通常是LinkedList或HashMap.这两个都很容易在短时间内完成,并且足以消除无能为力.

4> 小智..：

---

这并不一定涉及OOP功能,但在我们的最后一组访谈中,我们使用了Bug of the Month列表中的一些错误代码.观察候选人发现错误显示他们的分析能力,显示知道如何解释别人的代码

5> DevelopingCh..：

---

编写一个接受字符串的方法,如果该字符串是一个数字,则返回true.(任何正则表达式作为面试最有效的答案)

请编写一个抽象的工厂方法,它不包含开关并返回基类型为"X"的类型.(寻找模式,寻找反射,寻找它们不要侧面步骤并使用if else if)

请通过标记"|; |"拆分字符串"every; thing |; | else |; | in |; | he; re".(至少在.net中不允许使用多字符标记,因此寻找创造力,最好的解决方案是完全破解)

---

"编写一个接受字符串的方法,如果该字符串是一个数字,则返回true.(任何正则表达式作为最有效的答案)." 我确信这对你的工作是理想的,但是如果你用一个被认为非常糟糕的正则表达式解决方案回答了这个问题我会在哪里工作.在程序员时间方面有效,但不是运行时间.即使对于这样简单的问题,上下文也很重要.

---

3号的黑客攻击是什么？替换|; | 与字符串中没有出现的其他字符？

---

@AksharPrabhuDesai是的,通常使用类似pi或theta的东西,这样它就不会出现典型的输入,对于这种情况

6> Aaron N. Tub..：

---

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

我认为与树有关的问题往往会涵盖图问题的大部分困难,但没有那么多的代码复杂性.

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

7> Jon Dewees..：

---

跟进这样的问题:"你怎么能改进这个代码,以便维护它的开发人员可以弄清楚它是如何工作的？"

8> Xavier Nodet..：

---

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