数据结构实现

Question

存在诸如数组，链表，队列，堆栈，二叉树等数据结构。像Java或C ++这样的语言已经在很大程度上实现了它们，并且存在可以在任何程序或应用程序中使用的API。根据需要，可以选择特定的数据结构。我的问题是需要了解实施细节。仅仅知道例如，如果搜索是程序的重复任务，就可以使用数组代替链表，这还不够吗？我是新手，即使问这样的问题也可能很幼稚。甚至采访也非常关注它们的实施方式。请帮助我理解。

Answer 1

由于大多数程序为了有用，需要存储和处理某种数据，因此具有良好的数据结构来表示该数据至关重要，在某些情况下，甚至对于程序的性能至关重要。

话虽这么说，数组，链接列表，二进制树等都是可用的基本数据结构，并且它们在许多库中都可用的事实证明了它们的有用性。对它们的深入了解使您可以为任务选择最佳的数据结构。

了解此类数据结构的实现是了解它们如何工作，其缺点和优点的好方法。当然，您可以从理论上阅读它们，并且可以对它们有足够的了解，以便能够有效地使用库中提供的实现。问题在于，这还不是故事的结局。

作为程序员，您经常处于处理可能不太适合标准数据结构之一的各种数据的位置。您通常会编写自己的数据结构，以针对特定任务进行定制。并且了解如何实现一些基本数据结构不仅是一个很好的练习，而且在某些情况下还可以作为启发的来源。

至于面试，其范围是评估您作为程序员的能力。实施基本数据结构显示：

• 候选人对基本数据结构的熟悉程度

• 候选人编写代码的方式/为围绕代码的辩论提供了一些起点（例如，代码质量，性能技巧）

• 与特定问题无关，也就是说，您不会在面试中浪费宝贵的时间来解释问题

• 它们通常很简单，因此可以在面试所需的时间内完成

此外，作为初学者程序员，他们是一种良好的实践练习，以介绍可以应用于其他情况的一些常见模式和技术。

Answer 2

这些问题在访谈中的目的是要让受访者证明他们掌握语言，并且以计算机科学家的方式抽象地思考。

像Java和C ++这样的面向对象的语言尤其如此。编程经常尝试对现实世界进行建模。如果您正在谈论排序算法，则可以轻松地将该算法应用于一堆带编号的便笺，最后得到一个便笺的排序集合。或查看数据结构，您可以将类似的模型应用于餐厅订单（优先级队列，链接列表，希望不是堆栈？）。

由于大多数软件工程职位同样会要求申请人编写对现实世界进行建模的软件（例如，也许是通过Internet而不是通过信鸽进行对话），因此算法/数据结构类型的问题向访问者显示申请人有能力以故意方式对软件进行编码，以执行或建模实际任务。

从更实际的角度来看，必须设计Java和C ++中的预建数据结构，以使用多种输入。构建一个可以处理Object：Object存储的任何组合的映射比实现仅处理Integer：String解析的映射需要更多的开销。

如果您最终扮演的角色是毫秒/字节，那么可能需要手动构造/调整为特定目的而设计的数据结构。一个典型的例子是Java缺少内置的基数排序。其背后的逻辑是，基数排序的优化仅在非常特殊的情况下才起作用（当您仅需要基于它们的二进制值Fast！对基元进行排序时；因此，将实现留给开发人员是更有意义的如果他们的具体情况实际上需要使用基数排序。

总而言之，这些问题很难解决！尽管经验丰富的程序员会说什么，但是第一次有人要求您在白板上编写图形遍历算法，或者在工作中从头开始构建优化的搜索算法时，无论您是否学过，这都会变得很困难。