Google：我们90％的工程师都使用您编写的程序（Homebrew），无法反转板上的二叉树，所以再见。
尽管我从来不需要反转二叉树，但是当我在Skype / Microsoft，Skyscanner和Uber工作时，在日常工作中遇到了实际使用数据结构和算法的示例。这包括根据数据结构和算法的细节进行编码和决策。但是我大部分时间都使用了相关知识，以便了解如何创建某些系统以及为什么要以这种方式创建它们。相关概念的知识使您更容易理解使用这些概念的系统的体系结构和实现。
在本文中，我介绍了有关在实际项目中使用诸如树和图形之类的数据结构以及各种算法的情况的故事。在这里，我希望向读者表明，数据结构和算法的基础知识并不是仅用于面试的无用理论，而是在快速成长的创新技术公司工作的人很可能真正需要的东西。
在这里，我们将讨论非常少的算法，但是就数据结构而言，我可以注意到，我将在这里讨论几乎所有算法。对于任何人，我都不喜欢那种过分强调与实践脱节的算法并针对诸如红黑树或AVL树之类的奇异数据结构的采访问题，我不应该感到惊讶。我从未在面试中问过这样的问题，也不会问他们。在本文的结尾，我将分享对此类采访的看法。但是尽管如此，了解底层数据结构还是非常有价值的。这些知识使您可以准确选择解决某些实际问题所需的内容。
现在，让我们继续在现实生活中使用数据结构和算法的示例。
树木和树木遍历：Skype，Uber和UI框架
当我们为Xbox One开发Skype时，必须为没有所需库的纯Xbox OS编写代码。我们为此平台开发了首批成熟的应用程序之一。我们需要一个可以同时使用触摸屏和向应用程序发出语音命令来操作的应用程序导航系统。
我们已经创建了一个基于WinJS的基本导航框架。为此，我们需要维护一个类似于DOM的图，这对于组织观察用户可以与之交互的元素是必需的。为了找到此类元素，我们执行了DOM遍历，该遍历可归结为树遍历，即DOM元素的现有结构。这是BFS或DFS（宽度优先搜索或深度优先搜索-宽度优先搜索或深度优先搜索）的经典示例。
如果要进行Web开发，则意味着您已经在使用树结构，即DOM。所有DOM节点都可以有子节点。浏览器在遍历DOM树后在屏幕上显示节点。如果需要查找特定元素，则可以使用内置的DOM方法来解决此问题。例如，getElementById方法。另一种选择是开发自己的BFS或DFS解决方案以遍历节点并找到所需的内容。例如，这里做了类似的事情。
许多呈现UI元素的框架在其深度中使用树结构。因此，React支持虚拟DOM并使用智能协调算法（比较）。由于仅重新渲染界面的更改部分，因此您可以实现高性能。在此可以找到该过程的可视化。
在移动架构Uber中，RIB，也使用树木。这使该体系结构与大多数其他显示元素的层次结构的UI框架相似。 RIBs体系结构维护用于状态管理目的的RIB树。将RIB附加到其上或从中分离出来可控制其渲染。在与RIB一起工作时，我们有时会进行素描，试图了解RIB是否适合现有的层次结构，并讨论所考虑的RIB是否应具有可见元素。也就是说，他们讨论了此结构是将参与接口的可视表示形式的形成，还是仅用于状态管理。
使用RIB时的状态转换。您可以在此处找到有关RIB的更多详细信息，
如果您需要渲染层次结构元素，请注意，通常使用树结构来遍历它们并渲染访问的元素。我遇到了许多采用这种方法的内部工具。Uber移动平台团队创建的RIB渲染器就是此类工具的一个示例。这里是关于这个话题的演讲。
加权图和最短路径查找器：Skyscanner
Skyscanner是一个旨在寻找最优惠机票的项目。通过查看和分析世界上现有的所有路线并将它们组合起来，可以搜索此类报价。这项任务的实质与搜索机器人自动收集数据有关，而不是与缓存所有这些数据有关，因为航空公司会独立计算下一次航班的等待时间。但是，计划游览多个城市进行旅行的可能性归结为寻找最短路径的任务。
多城市旅行计划是Skyscanner花费很长时间实施的可能性之一。同时，困难主要与系统本身的开发有关。使用最短路径算法（例如Dijkstra或A *）可以找到此类最佳交易。飞行路线以有向图的形式表示。它的每个边缘都以门票价格的形式分配权重。当搜索最佳路线时，使用改进的A *算法的实现来查找两个城市之间的最便宜路线。如果您对选择机票和查找最短路线的主题感兴趣，那么这里是一篇有关使用BFS解决此类问题的好文章。
但是，对于Skyscanner，使用哪种算法解决该问题并不是特别重要。使用搜索机器人进行缓存，组织各个站点的工作-这比选择算法要困难得多。但是同时，在许多不同的旅行计划公司中，寻找最短路径的问题也出现了不同的变体，并优化了此类旅行的费用。毫不奇怪，这个主题也是Skyscanner幕后演讲的主题。
排序：Skype（或类似的东西）
我很少有理由自己实施排序算法或深入研究其设计的复杂性。尽管如此，了解这样的算法是如何工作的还是很有趣的-从冒泡排序，插入排序，合并排序和选择排序到最复杂的算法-快速排序。我发现很少需要实现这样的算法，尤其是如果您不需要编写作为库一部分的排序函数时。
但是，在Skype中，我不得不求助于我对排序算法知识的实际使用。我们的一位程序员决定实现插入排序以显示联系人。 2013年，当Skype联机时，批量下载了联系人。全部下载都花了一些时间。结果，该程序员认为最好使用插入排序来建立按姓名排序的联系人列表。我们讨论了很多这种算法，并思考为什么不仅仅使用已经实现的算法。结果，我们花费了最多的时间来正确测试算法的实现并检查其性能。就个人而言，在创建自己的算法实现方面并没有多大意义。但是当时项目还处于这样的阶段我们有时间去做这些事情。
当然，在现实世界中，有效排序在项目中起着非常重要的作用。如果开发人员可以根据数据的特征独立选择最适合的算法，则可以显着提高解决方案的性能。当您处理实时传输到某处的大型数据集并立即可视化此数据时，插入排序可能非常有用。当处理存储在不同节点中的大量数据时，合并排序可以很好地用于分而治之的方法。我从来没有使用过这样的系统，所以现在我继续考虑将排序算法视为在日常工作中使用受限的东西。这是真的，这与了解不同排序算法的工作原理无关紧要。
哈希表和哈希：无处不在
我经常使用的数据结构是哈希表。这也包括哈希函数。这是一个非常有用的工具，可用于解决各种任务-从计算某些实体的数量，检测重复项，缓存到分布式系统中使用的分片之类的场景。在数组之后，哈希表是编程中最常见的数据结构。我已经在无数情况下使用过它。它几乎存在于所有编程语言中，如果需要，您可以自己实现。
堆栈和队列：不时
堆栈是调试使用支持堆栈跟踪的语言编写的代码的任何人都熟悉的数据结构。如果我们将堆栈作为数据结构来讨论，那么在工作过程中，我遇到了一些需要解决的问题。但是应该注意的是，在调试和分析代码性能时，我必须正确了解堆栈。堆栈也是执行DFS时要使用的数据结构的自然选择。
我很少不得不使用队列，但是我经常在各种项目的代码库中遇到它们。假设有一些放入队列中，并且从中检索出一些东西。通常，队列用于实现广度优先的树遍历，它们是此任务的理想选择。队列也可以在许多其他情况下使用。当我遇到一些作业调度代码时，在其中找到了优先使用优先队列的示例，该示例由最先执行最短的作业的Python模块heapq实现。
加密算法：Uber
用户输入到移动或Web应用程序中的重要数据必须经过加密，然后才能通过网络传输。并且它们仅在需要的地方解密它们。为了组织这样的工作方案，必须在应用程序的客户端和服务器部分上提供加密算法的实现。
了解密码算法非常有趣。同时，您不应提供自己的算法来解决某些问题。这是程序员可能想到的最糟糕的想法之一。取而代之的是，它采用了现有的，文档完善的标准，并使用了各个框架的本机原语。通常，AES是实施加密解决方案时选择的标准。...使用它来加密美国的机密信息足够安全。该协议没有已知的有效攻击。 AES-192和AES-256对于大多数实际任务通常非常可靠。
当我来到Uber时，已经基于上述机制实现了移动加密系统和Web应用程序的加密系统，因此我有一个借口来研究有关AES（高级加密标准），有关HMAC（哈希消息验证码）的细节。 ，有关RSA算法和其他类似内容。了解如何证明加密中使用的动作序列的加密强度也很有趣。例如，如果我们讨论带有附加数据的经过身份验证的加密，结果表明，分析“先加密后加密”，“先加密后加密”和“先加密后加密”模式，可以证明仅其中一种的加密强度，但这并不意味着其余都不是加密安全的。
除非您要实现一个全新的加密框架，否则您几乎不需要自己实现加密原语。但是您很可能需要做出决定，以决定要使用哪些原语以及如何将它们组合在一起。您可能还需要密码算法领域的知识，以了解为什么某个系统使用某种方法进行数据加密。
决策树：Uber
在处理其中一个项目时，我们必须在移动应用程序中实现复杂的业务逻辑。即，基于六个规则，必须显示几个屏幕之一。这些规则非常复杂，因为必须考虑测试顺序的结果和用户的偏好。
开始解决此问题的程序员首先尝试以if-else语句的形式表达所有这些规则。这导致代码极其混乱。结果，决定使用决策树。在他的帮助下，容易进行所有必要的检查。它相对容易实现。另外，如果有必要，可以毫无问题地对其进行更改。我们需要创建自己的决策树实现，以便条件检查可以在其边缘执行。这就是我们从这棵树中所需要的。尽管我们可以通过采用其他方法来节省实施树的时间，但该团队认为，特定的树将更易于维护并开始工作。这棵树看起来像这样：边缘象征着条件检查的结果（这些是二进制结果，或由值范围表示的结果），树的叶子节点描述了您需要导航至的屏幕。
, , .
Uber的移动应用程序的构建系统称为SubmitQueue，也使用了决策树，但它是动态生成的。开发人员体验团队必须解决每天执行数百个源分支与目标分支的合并这一难题。同时，每个组装约需30分钟才能完成。这包括编译，运行单元和集成测试以及接口测试。并行程序集并不是一个很好的解决方案，因为不同程序集中经常有重叠的更改，这会导致合并冲突。实际上，这意味着有时程序员不得不等待2-3个小时，求助于变基，然后再次重新启动合并过程，希望这次他们不会遇到冲突。
开发人员体验团队采用了一种创新方法来预测合并冲突并相应地对程序集进行排队。这是使用特殊的二进制决策树（推测树）完成的。
SubmitQueue使用二进制决策树，其边缘带有预测概率。这种方法使您可以确定可以并行运行的程序集集。这样做是为了减少接收和执行任务之间的时间，并增加系统的吞吐量。在这种情况下，只有经过充分测试和可行的代码才可以进入master分支
，创建此系统的Developer Experience团队为此编写了出色的材料。但是这里-关于相同主题的另一篇文章，有充分的说明。引入该系统的结果是创建了一个比以前更快的项目组装系统。它使我们能够优化项目的构建时间，并帮助简化数百名移动程序员的生活。
六角网格，层次索引：Uber
这是我在这里要谈的最后一个项目。它完全基于一种特定的数据结构。通过这样做，我了解了这种数据结构。我们正在谈论具有分层索引的六边形网格。
Uber最具挑战性和最有趣的问题之一是旅行成本的优化和合作伙伴之间的订单分配。出行费率可以动态变化，驾驶员不断前进。 Uber工程师创建了H3网格系统。它旨在可视化和分析不同规模城市的数据。用于解决上述问题的数据结构是具有分层索引的六边形网格。几个专门的内部工具用于可视化数据。
将地图分为六边形单元格
此数据结构具有自己的索引系统，遍历，自己的网格各个区域定义，自己的功能。所有这些的详细说明可以在相应API的文档中找到。在此处阅读有关H3的更多信息。这是源代码。在这里，您可以找到有关如何以及为何创建此系统的故事。
使用该系统的经验使我对以下事实感到满意：创建自己的专用数据结构在解决非常具体的问题时很有意义。如果不考虑将地图片段划分为每个不同级别的结果数据片段进行比较，则解决方案中可以应用六边形网格的问题很少。但是和其他情况一样，如果您熟悉其他数据结构，这将更容易理解。对于处理了六边形网格的人来说，创建一个新的数据结构来解决与使用这种网格所解决的问题类似的问题将变得更加容易。
访谈中的数据结构和算法
上面，我谈到了在多家公司工作了很长时间后遇到的数据结构和算法。我现在建议回到Max Howell的那条推文，我在本文的开头就提到过。在那里，马克斯抱怨说，在一次Google采访中，他被要求倒置板上的二叉树。他没有。他被指示出门。在这种情况下，我站在马克斯的身边。
我相信，了解流行算法的工作方式或奇异数据结构的工作方式，并不是您为一家高科技公司工作所需的知识。您需要知道什么是算法，还需要能够独立提出简单的算法，例如，按照“贪婪”原则工作。您还需要了解最常见的数据结构，例如哈希表，队列和堆栈。但是，诸如Dijkstra的算法或A *之类的非常具体的东西，甚至更复杂的东西，都不需要被内心学习。如果您确实需要这些算法，则可以轻松地在它们上找到参考资料。例如，如果我们谈论与排序算法无关的算法，我通常会尝试从广义上理解它们并理解其本质。异类数据结构（如红黑树和AVL树）也是如此。我从来不需要使用它们。而且，如果我需要它们，我总是可以借助适当的出版物来刷新对它们的了解。正如我所说，在面试时，我从不问这样的问题，也不打算问这些问题。
我赞成与编程相关的实际问题，在解决这些问题时，您可以应用多种方法：从算法的“强力”和“贪婪”方法到更高级的算法思想。举例来说，我认为这是完全没问题，有一个像文本对齐任务此。例如，创建用于在Windows Phone上呈现文本的组件时，我必须解决此问题。您只需使用数组和一些if-else语句即可解决此问题，而无需求助于一些棘手的数据结构。
实际上，许多团队和公司都夸大了算法问题的重要性。我了解算法问题的吸引力。它们使您可以在短时间内评估申请人，这些问题易于重做，这意味着，如果向某人提出的问题公开，则不会造成任何特殊问题。算法问题对于组织大量申请人的试验非常有用。例如，您可以创建一个包含一百多个问题的库，并将它们随机分发给申请人。有关动态编程和奇异数据结构的问题越来越普遍。特别是在硅谷。这些问题可以帮助公司聘请强大的程序员。但是，这些相同的问题可以为那些成功开展业务的人关闭公司的道路，不需要深入了解算法的地方。
如果您来自一家公司，而该公司仅雇用几乎从一开始就对复杂算法有深入了解的人员，那么我建议您仔细考虑一下这些人是否是您需要的人员。例如，我在Skyscanner（伦敦）和Uber（阿姆斯特丹）雇用了优秀的团队，却没有提出棘手的算法问题。我将自己局限于最常见的数据结构，并测试与问题解决相关的受访者的能力。也就是说，他们需要了解常见的数据结构，并能够提出简单的算法来解决他们面临的问题。数据结构和算法只是工具。
底线：数据结构和算法是工具
如果您在一家充满活力的创新技术公司工作，那么您可能会在该公司产品的代码中遇到各种数据结构和算法的实现。如果您正在开发全新的产品，则通常必须寻找能够更轻松地解决所面临问题的数据结构。在这种情况下，您需要对算法和数据结构以及它们的优缺点有一个全面的了解，才能做出正确的选择。
数据结构和算法是编写程序时应放心使用的工具。当您知道这些工具后，您将在使用它们的代码库中看到很多已经知道的内容。此外，这些知识将使您更有信心地解决复杂的问题。您将了解算法的理论局限性以及如何对其进行优化。这将帮助您最终找到一个解决方案，该方案经过所有必要的折衷，最终证明是尽可能好的。
如果您想更好地理解数据结构和算法，请参考以下技巧和资源：
- -, , , , , , . , , . , . — , .
- « ». , , , . — , , . , , , .
- 这里还有几本书：“算法。开发指南“和Java中的算法，第4版”。我用它们来刷新我的大学算法知识。是的，我还没有读完它们。在我看来，它们似乎很干燥，不适用于我的日常工作。
您在实践中遇到了什么数据结构和算法？
