我在科技公司工作时使用的数据结构和算法

你在日常工作中真的使用算法和数据结构吗？我注意到，越来越多的人认为算法是毫无意义的问题，这些问题纯粹是科技公司提出的一种武断的衡量标准，这一趋势越来越大。我听到更多的人抱怨说，所有这些都是纯粹的学术活动。在“自制酒”(Homebrew)的作者马克斯·豪厄尔(Max Howell)发布了他在谷歌上的采访经历后，这个概念肯定得到了普及：

谷歌：我们90%的工程师都在使用你写的软件(Homebrew)，但是你不能在白板上倒置二叉树，所以他妈的去他妈的。

-Max Howell(@mxcl)2015年6月10日。

虽然我也从来不需要使用二叉树倒置，但我在Skype/Microsoft、Skyscanner和Uber工作时遇到过数据结构和算法的日常用例。这包括编写代码和基于这些概念做出决策。更重要的是，我利用这些知识了解了一些东西是如何构建的以及为什么要构建，以及我可以如何使用或修改它们。

本文是一组真实世界的示例，其中在生产中使用了树、图和各种算法等数据结构。所有这些都是我的亲身经历。我希望说明，通用的数据结构和算法知识不只是为了面试--而是你在快速增长的创新科技公司工作时可能会接触到的东西。

我使用了非常小的算法子集，但几乎使用了所有的数据结构。不足为奇的是，我不喜欢像红黑树或AVL树这样具有奇异数据类型的算法繁重且不切实际的面试问题。从来没有问过这些，将来也不会。你可以在这篇文章的末尾读到我对这些采访的看法。尽管如此，我发现了解他们可以选择哪些基本数据类型选项来解决某些问题是很有价值的。有了这一点，让我们跳到例子中去。

当我们构建Xbox One的Skype时，我们开发的是一个基本的Xbox操作系统，缺少密钥库。我们正在构建该平台上首批成熟的应用程序之一。我们需要一种导航解决方案，既可以连接到触摸手势，也可以连接到语音命令。

我们在WinJS之上构建了一个通用导航框架。为此，我们需要维护一个类似DOM的图来跟踪可操作的元素。为了找到这些元素，我们进行了DOM遍历-基本上是B树遍历-遍历现有的DOM。这是BFS或DFS(广度优先搜索或深度优先搜索)的典型案例。

在Uber，团队构建了许多工具来可视化节点、依赖关系和它们的连接。一个例子是肋骨节点的可视化工具。在这种情况下，方法是相同的。该工具需要维护一棵树，将其可视化为SVG，然后在移动设备上的肋骨树更改时更新该树。此外，RIB本身维护与呈现对象不同的状态管理的逻辑树结构：这是其设计背后的关键思想之一。

Skyscanner找到最划算的机票。它通过扫描世界各地的所有路线，然后将它们组合在一起来做到这一点。虽然问题的本质更多地是爬行，而不是缓存-随着航空公司计算中转选项-多城市规划选项成为最短路径问题。

多城市是Skyscanner花了相当多时间构建的功能之一-公平地说，困难更多的是在产品方面，而不是任何事情。最佳的多城市交易是通过使用Dijkstra或A*等最短路径算法来计算的。飞行路线用有向图表示，每条边都有机票成本的权重。通过对每条路线实施改进的A*搜索算法，计算两个城市之间的最便宜价格选项。如果你对航班和最短路径感兴趣，萨钦·马尔霍特拉(Sachin Malhotra)撰写的关于使用BFS实现最短航班搜索路径的文章是一本不错的读物。

不过，使用Skyscanner，实际的算法就不那么重要了。缓存、爬行和处理不同的网站负载是更难破解的事情。尽管如此，最短路径问题的另一种变体出现了许多几家旅游公司，它们根据组合进行价格优化。不出所料，这个话题也是这里走廊讨论的一个来源。

排序是我很少有借口实现或需要深入使用的算法家族。了解不同类型的排序方式是很有趣的，从冒泡排序、插入排序、合并排序、选择排序，还有--最复杂的一种--快速排序。尽管如此，我还是发现我几乎没有理由必须实现这些功能，特别是因为我从来不需要将排序函数作为库的一部分来编写。

不过，在Skype，我对这方面的知识进行了一些练习。另一位工程师决定实现列出联系人的插入排序。2013年，当Skype连接到网络时，联系人会成群结队地到达，所有联系人都需要一段时间才能到达。因此，这位工程师认为，使用插入排序按姓名组织的联系人列表性能更好。我们对此进行了反复讨论，为什么不直接使用默认排序算法。最后，更多的工作是对实现进行适当的测试，并对其进行基准测试。我个人认为这样做没有多大意义：但我们正处于项目的阶段，我们有时间。

在一些真实的用例中，有效的排序非常重要，并且根据数据控制您使用的排序类型可以起到很大的作用。当以大块流式传输实时数据并为这些数据源构建实时可视化时，插入排序非常有用。如果涉及到存储在不同节点上的大量数据，合并排序可以很好地使用分而治之的方法。我没有使用过这些方法，所以除了欣赏不同的方法之外，我仍然会标记我几乎用不到的排序。

我经常使用的最频繁的数据结构是哈希表和哈希函数。它是一个非常方便的工具，从计数，到检测重复，再到缓存，一直到像分片这样的分布式系统用例。在数组之后，它很容易成为我在无数场合使用过的最常用的数据结构。几乎所有的语言都带有这种数据结构，如果您需要它，它很容易实现。

任何调试过具有堆栈跟踪的语言的人都会非常熟悉堆栈数据结构。作为一种数据结构，我在使用它时遇到了一些问题，但是调试和性能分析让我错综复杂地熟悉了它。

我很少选择队列作为代码的数据结构，但我在代码库、代码弹出或推送中遇到过它很多次。对于分析和分析构建的构建瓶颈检测器工具，我读取了使用Python堆队列算法巧妙地使用优先级队列进行优化的代码。

优步很早就采用了几种语言和技术，而密码学的实现并没有达到我们所需的稳定性。iOS和Android就是一个很好的例子。来自客户端的用户输入的敏感信息在通过网络发送之前需要加密，只需在特定服务上解密。

有些情况下，我们必须构建我们自己的加密/解密实现，在没有支持它的框架或可用的经审计的库的情况下，对它们进行正式的验证和审计。

构建密码总是很有趣的。这更像是一个实现挑战：你不需要想出一个新的算法--对于加密来说，这可能是你从事工程工作时最糟糕的想法之一。取而代之的是，采用符合要求的现有的、文档齐全的标准，然后对其进行编码、验证、审计，然后再次进行审计。在本例中，这是实现AES标准。这是一项有趣的智力挑战。我们构建了一些移动和网络加密实现，深入了解了高级加密标准(AEP)、散列消息验证码(HMAC)或RSA公钥加密的细节。

作为审核解决方案的一部分，调查消息篡改或拒绝服务影响等攻击载体。验证一系列加密步骤是否可证明是安全的是另一件需要理解的有趣事情。正如深入了解加密和MAC、MAC然后加密和加密然后MAC之间，它们中只有一个是可证明的安全的，但这并不意味着其他的不是安全的。(#39；#**$${##**$$}。

当我在2016年加入优步时，移动领域最大的痛点是构建需要多长时间，以及合并您的更改需要多长时间。一个完整的构建大约需要40分钟，从构建到所有测试-单元、集成、E2E。我们有大约300名开发人员正在推动生产，所有的更改都必须经过构建才能落地。师父需要始终保持绿色。

当构建被并行化时，60%的情况下，在构建通过后，合并将失败。其他人会更改类似的代码路径，并且他们的更改已经在repo中。因此，通过多次重试，合并您的更改平均需要2-3个小时。

坐在我旁边的开发者体验团队想要解决这个问题，他们从两个角度来做。首先，他们加快了构建和测试的速度，使其花费的时间不超过30分钟。其次，他们的目标是每个人换衣服的时间应该是30分钟，95%的时间。但是合并冲突怎么办呢？让我们预测它们，并相应地建立队列。这就是他们所做的，通过创建冲突和投机图表。在这份白皮书中有更多的细节，但结果是一个更快的队列-称为SubmitQueue-优化了构建时间，并使现在的400名移动工程师的生活变得更加愉快。在幕后使用了一些算法。

最后一个项目是我没有参与的，但我观察到并使用了建立在它之上的工具。在这里，我了解了一种新的数据结构：具有分层索引的六边形网格。

优步需要解决的最困难和最有趣的问题之一是如何优化出行定价和合作伙伴的派遣。价格可以是动态的，司机们也在不断地移动。H3是优步的网格系统工程师，其构建目的是在越来越细粒度的水平上跨城市可视化和分析数据。它的数据结构和可视化结构是一个具有分层索引的六边形网格。

该数据结构具有特定的索引、遍历、分层网格、区域和单向边函数，详见API参考。有关更详细的深入研究，请参阅关于H3库的文章、源代码或关于如何以及为什么构建此工具的演示文稿。

我真正喜欢这个经历的地方是，我了解到如何在特定领域创建您自己的专用数据结构是有意义的。除了将映射与每个单元格中的各种数据级别相结合之外，使用分层索引的六边形网格的用例并不多。不过，如果您熟悉一些数据结构，理解这种新的数据结构就容易得多--因为它可以为特殊需要设计另一个数据结构。

这些都是我多年来在多家公司之间专业使用的实际数据结构和算法的亮点。因此，让我们回到最初的推特上，那条推文抱怨问问题，比如在白板上颠倒二叉树。在这件事上，我是站在马特这边的。

要在一家科技公司工作，了解流行的算法或奇异的数据结构是如何工作的，并不是你应该知道的事情。您应该知道什么是算法，并且应该能够自己想出简单的算法，比如贪婪的算法。您还应该了解非常常见的基本数据结构，如哈希表、队列或堆栈。但是像Dijkstra或A*这样的特定算法不是你需要记住的：你会有这方面的参考，就像我在实现Crypto时一样。异类数据结构(如红黑树或AVL树)也是如此。我从来没有使用过这些数据结构，即使我使用了，我也会再次查找它们。我从来没有问过需要这种知识才能解决的问题，将来也不会。

我完全赞成要求实际的编码练习，那里有许多好的解决方案，从蛮力或贪婪的方法到潜在的更复杂的方法。例如，像这样要求实现一个对齐文本函数是一个公平的问题：这是我在Windows Phone上构建一个简单的文本渲染器时做的事情。您只需使用一个数组和几个if/Else语句就可以解决这个问题，而不需要任何花哨的数据结构。

现实情况是，许多团队和公司都在算法挑战上走得太远。我可以看到算法问题的吸引力：它们在45分钟或更短的时间内给出信号，并且问题可以很容易地交换；因此，问题泄露几乎没有什么坏处。它们在招聘时也很容易扩展，因为你可以有一个包含100多个问题的问题库，任何面试官都可以对其中的任何一个进行评估。特别是在硅谷，听到针对动态编程或外来数据结构的问题越来越常见。这些问题将有助于雇佣优秀的工程师，但也会导致那些本可以在不需要高级算法知识的工作中表现出色的人被拒之门外。

任何读者，如果你所在的公司有招聘熟记一些高级算法的人的权利：如果这是你所需要的，请三思而后行。我已经在伦敦Skyscanner和优步阿姆斯特丹雇佣了非常棒的团队，没有任何棘手的算法问题，只涉及数据结构和问题解决。你不应该把算法背得一清二楚。您需要的是了解最常见的数据结构，并能够提出简单的算法来解决手头的问题，作为一个工具集。

如果你在一家快速发展的创新科技公司工作，你几乎肯定会在代码库中遇到各种各样的数据结构和不同的算法实现。当您构建新的创新解决方案时，您通常会发现自己达到了正确的数据结构。这就是你想要了解可供选择的选项及其权衡的时候。

数据结构和算法是您在构建软件时应该自信地使用的工具。了解这些工具，您就会熟悉使用它们的代码库导航。你也会对如何实施难题的解决方案更有信心。您将了解理论上的限制，您可以进行的优化，并且您将提出尽可能好的解决方案-所有折衷都要考虑在内。

阅读哈希表、链表、树、图、堆、队列和堆栈数据结构。玩弄一下如何在你的语言中使用它们。作为一个概述，GeeksforGeek有一个很好的概述。对于编码实践，我推荐使用HackerRank数据结构集合。

研习算法Aditya Bhargava是从初学者到有经验的工程师关于算法的最佳指南。这是一本非常平易近人的视觉指南，涵盖了大多数人-包括我自己-在这个主题上需要知道的所有内容。我相信你不需要比本书封面更了解算法。

《算法设计手册》和《算法：第四版》都是我当年拿来复习大学里学过的一些东西的书。我中途放弃了，发现它们相当干燥，不适用于我所做的工作。

喜欢这篇文章吗？订阅我的时事通讯，并在您的收件箱中获取未来的帖子。这是一本相当不错的书，拥有超过3500名订阅者。

订阅我的时事通讯，了解实用的软件开发和工程职业发展的最新情况。