我在技术公司实际使用的数据结构和算法

您实际上在日常工作中使用算法和数据结构吗?我注意到人们越来越多地认为算法是毫无意义的问题,而这些问题纯粹是技术公司提出的一种任意措施。我听到更多的人抱怨这一切都是纯粹的学术活动。在Homebrew的作者Max Howell发布他的Google采访经历之后,这个概念肯定得到了普及:

maxhowell

尽管我也从来不需要使用二叉树反转,但是在Skype / Microsoft,Skyscanner和Uber工作时,我遇到了数据结构和算法的日常用例。这包括编写代码并根据这些概念做出决策。但是在大多数情况下,我使用这些知识来了解如何以及为何构建某些东西。了解了这些概念后,就很容易理解引用这些概念的设计和实现。

本文是一组实际示例,其中在生产中使用了诸如树,图和各种算法之类的数据结构。我希望说明一下,通用的数据结构和算法知识并非“仅仅适合面试”,而是在快速发展的创新型技术公司工作时可能会发现的东西。

我使用了非常小的算法子集,但几乎使用了所有数据结构。毫不奇怪,我不喜欢算法繁琐且不切实际的面试问题,这些问题涉及诸如红黑树或AVL树之类的奇异数据类型。从来没有问过这些,也永远不会。您可以在本文结尾处了解我对这些采访的看法。仍然有很多价值,知道他们可以选择基本数据类型的哪些选项来解决某些问题。这样,让我们跳入示例。

树木和树木遍历:Skype,Uber和UI框架

当我们构建Xbox One的Skype时,我们使用的是准系统Xbox OS,但缺少关键库。我们正在该平台上构建首批成熟的应用程序之一。我们需要一个导航解决方案,我们可以将其连接到触摸手势和语音命令。

我们在WinJS之上构建了一个通用的导航框架。为此,我们需要维护一个类似DOM的来跟踪可操作的元素。为了找到这些元素,我们对现有DOM进行了DOM遍历-基本上是遍历。这是BFSDFS(宽度优先搜索或深度优先搜索)的经典情况。

如果要进行Web开发,则已经使用树结构:DOM。所有DOM节点都可以有子节点,并且浏览器在遍历DOM树后在屏幕上呈现节点。如果要搜索特定元素,则可以使用内置的DOM方法找到它(例如getElementById),也可以实现BFS或DFS搜索以遍历所有节点,类似于本示例中的操作

许多呈现UI元素的框架在后台使用树结构。React维护一个虚拟DOM,并使用智能对帐(一种“差异”算法)通过仅重新渲染已更改的屏幕部分来提供出色的性能。Ryan Bas 在关于React对帐的文章中将这一过程可视化。

在Uber的移动架构中,RIB也使用树-与大多数呈现层次结构中的元素的UI框架相似。RIB维护用于状态管理,附加和分离需要呈现的RIB 的RIB树。在使用RIB时,有时我们会勾勒出新RIB在层次结构中适合的位置,并讨论所讨论的RIB是否应具有视图(使其成为视图层次结构的一部分)或仅管理状态。

img示例RIB用例中的状态转换。请参阅此处的 RIB文档和代码。

如果您发现自己需要构建层次结构元素的可视化,一种常见的方法是使用树状结构,遍历树并渲染您访问的元素。我遇到了许多使用这种方法的内部工具。Uber移动平台团队构建的RIBs可视化工具就是一个例子,您可以在此视频的演示看到该工具

权重图和最短路径:Skyscanner

Skyscanner找到最优惠的机票。为此,它会扫描全球所有路线,然后将它们放在一起。虽然问题的本质更多地是在爬网上,而在缓存上却很少(当航空公司计算中转选项时),但多城市规划选项却成为最短路径问题

多城市是Skyscanner花费大量时间来构建的功能之一-公平地说,在产品方面,困难比什么都重要。最好的多城市交易是通过使用最短路径算法(例如Dijkstra或A )来计算的。飞行路线以有向图表示,每个边均具有机票成本的权重。通过在每条路线上实施经过修改的[**A \搜索算法](https://en.wikipedia.org/wiki/A*_search_algorithm) ,可以计算出两个城市之间的最便宜价格。如果您对航班和最短路径感兴趣,那么Sachin Malhotra撰写的有关使用BFS** 实现最短航班搜索路径的文章是不错的阅读。

但是,使用Skyscanner,实际算法就不那么重要了。缓存,爬网和处理各种网站负载是要破解的困难得多。尽管如此,最短路径问题的变化还是出现在许多旅行社基于组合进行价格优化的情况下。毫不奇怪,此主题也是此处进行走廊讨论的来源。

排序:Skype(种类)

排序是一个算法系列,我很少有借口实现或需要深入使用。了解气泡排序,插入排序,合并排序,选择排序以及-最复杂的一种-快速排序的不同类型的排序方式很有趣。不过,我发现很少有理由要实现这些功能,尤其是当您不需要将排序函数编写为库的一部分时。

不过,在Skype上,我必须对此知识进行一些练习。另一位工程师决定实施插入排序以列出联系人。在2013年,当Skype连接到网络时,联系人会突然到达,并且所有联系人都需要花费一些时间。因此,这位工程师认为使用插入排序来建立按姓名组织的联系人列表更加有效。关于为什么不只使用默认排序算法,我们进行了反复讨论。最后,适当地测试实现并进行基准测试是更多的工作。我个人认为这样做没有多大意义:但是我们正处在项目阶段,我们有时间。

在现实世界中肯定有一些用例,其中有效的排序很重要,并且根据数据控制使用的排序类型可以有所作为。当以大块流传输实时数据并为这些数据源建立实时可视化时,插入排序会很有用。如果涉及到存储在不同节点上的大量数据,则合并排序可以很好地与分而治之方法一起使用。我没有使用这些算法,因此除了对各种方法的欣赏之外,我仍将排序算法标记为日常使用很少的事物。

加入邮件列表

订阅我的时事通讯,并及时了解实用的软件开发和工程职业发展。

哈希表和哈希:无处不在

我经常使用的最常见的数据结构是哈希表哈希函数。从计数,检测重复,到缓存,再到分片之类的分布式系统用例,它都是一个便捷的工具。在数组之后,它很容易成为我在无数场合使用的最常见的数据结构。几乎所有语言都带有此数据结构,如果需要,可以轻松实现。

堆栈和队列:时不时地

堆栈的数据结构将是人谁调试具有堆栈跟踪的语言非常熟悉。作为数据结构,我在使用它时遇到了一些问题,但是调试和性能分析使我变得非常熟悉。在深度优先遍历树时,这也是一个显而易见的选择。

我很少需要选择队列作为代码的数据结构,但是我在代码库,代码弹出或向其中推送值时遇到了很多次。一个常见的用例是实现树的BFS遍历,其中队列数据结构适合自己。您还可以将队列用于其他各种用例。我曾经读过一些代码调度作业,这些作业充分利用了优先级队列,首先使用Python堆队列算法运行最短的作业。

加密货币:Uber

来自客户端的用户输入的敏感信息在通过网络发送之前需要进行加密,仅在特定服务上进行解密。为此,您需要在客户端和后端选择一种加密方法。

了解加密是一个有趣的话题。您不会想出一种新算法-使用加密技术可能是最糟糕的想法之一。取而代之的是,您采用现有的,有据可查的标准以及框架内置的原语,通常将其作为AES标准的一部分。如果可以安全地加密美国机密信息,并且对该协议没有已知的有效攻击,那么对于大多数使用情况,AES192或AES256可能是足够安全的选择。

当我加入Uber时,已经在这些原语的基础上实现了移动和网络加密,这为我提供了借口查找高级加密标准(AES),哈希消息身份验证码(HMAC)或RSA公钥加密的详细信息和别的。

验证一系列加密步骤是否可证明是安全的是另外一件有趣的事情。就像在“加密与MAC”,“ MAC然后加密”和“加密然后MAC”之间的方式一样,其中只有一个是可证明的安全性 -即使这并不意味着其他都不安全。

借助加密技术,除非构建一个全新的核心框架,否则很少需要实现原语。但是,决定要使用哪些原语,如何组合原语以及解决方案是否足够安全是很有趣的事情。

决策树:Uber

在其中一个项目中,我们必须在移动应用程序中实现复杂的业务逻辑。基于六条规则,我们必须显示几个不同的屏幕之一。由于需要进行一系列合规性检查和用户选择,因此规则异常复杂。

构建此功能的工程师首先尝试使用一系列if-else语句对规则进行编码,这太复杂了。最后,他们决定采用决策树,因为它很容易通过产品和合规性进行验证,合理实施且易于更改(如果需要)。我们需要为边缘构建一个实现来执行规则,但这仅此而已。尽管我们可以用另一种方法来节省实施此树的时间,但该团队发现,此解决方案易于维护,可以继续。决策树如下所示:边缘是执行规则的结果(二进制结果或值范围),叶节点标记要过渡到的屏幕。

img我们构建了一个决策树的结构,以遵循一组复杂的规则来决定显示哪个屏幕。

Uber的移动构建系统称为SubmitQueue,也利用动态决策树。开发人员体验团队必须解决每天发生数百个移动合并的难题,每个构建大约需要30分钟才能运行-构建,单元测试,集成和UI测试。并行化构建还不够好,因为两个构建通常会有重叠的更改,并且会发生合并冲突。在实践中,这意味着有时工程师将不得不等待2-3个小时,重新评估并盯着合并过程,并希望不会有冲突。

开发者体验团队采用了一种创新的方法,即通过推测图来预测合并冲突并相应地对构建进行排队。投机图非常类似于二进制决策树。

imgSubmitQueue使用一个推测树-一个二进制决策树-用每个边缘的预测概率进行注释。这种方法确定了要并行运行的构建集,以改善周转时间和吞吐量,同时保持主控绿色。在这里阅读全文

由开发者团队的工程师撰写的这份白皮书中有很多细节,这些白皮书构建了该解决方案-这篇白皮书非常有用。阿德里安·科耶尔(Adrian Colyer)也对该方法进行了很好的视觉分析。结果是建立了更快的构建系统,优化了构建时间,并使数百名移动工程师的生活更加愉悦。

六角形网格,层次索引:Uber

最后一个项目是我纯粹基于绊脚而来的。我了解了一种新的数据结构:具有层次结构索引的六边形网格。

在优步要解决的最困难和最有趣的问题之一是如何优化旅行的定价以及合作伙伴的派遣。价格可能是动态的,驱动程序也在不断变化。H3是一个网格系统工程师,旨在以越来越细化的水平可视化和分析整个城市的数据。数据和可视化结构是具有层次结构索引的六边形网格,并且在其之上构建了两个内部可视化工具。

img用六边形细分区域。在这里阅读详尽的文章。

数据结构具有特定的索引,遍历,分层网格,区域和单向边缘功能,详细信息请参见API参考。有关更深入的了解,请参见H3库上文章源代码或有关如何以及为何构建此工具的演示

我真的很喜欢这种经验,是在学习发现自己创建专门的数据结构在特定领域很有意义。在没有很多用例的情况下,具有层次结构索引的六边形网格比将映射与每个单元中的各种数据级别组合起来更有意义。不过,如果您熟悉某些数据结构,则了解此新数据结构要容易得多-因为您将可以为满足类似的特殊需求而设计另一个数据结构。

访谈,算法和数据结构

这些是我多年来在多家公司之间专业遇到的实际数据结构和算法的亮点。因此,让我们回到最初的推文中,该推文抱怨询问诸如反转白板上的二叉树之类的问题。我站在Max的这一边。

在一家科技公司工作,您不需要了解流行算法或外来数据结构的工作原理。 您应该知道什么是算法,并且应该能够自己提出一些简单的算法,例如贪婪的算法。您还应该了解非常常见的基本数据结构,例如哈希表,队列或堆栈。但是您不需要记住诸如Dijkstra,A *和更高级的算法之类的特定算法:您将为此提供参考。除了排序以外,我对算法所做的最大工作就是查找它们并自己理解它们。与奇异的数据结构(如红黑树或AVL树)相同。我从来没有使用过这些数据结构。即使我这样做,我也会再次查找它们。我从未问过需要这种知识来解决这些问题的问题,也永远不会问。

我全都想问一些实用的编码练习,那里有许多不错的解决方案,从蛮力或贪婪的方法到可能更复杂的方法。例如,要求实现一个像这样的问题的证明文本功能是一个很公平的问题:这是我在Windows Phone上构建文本呈现组件时所做的事情。您只需使用一个数组和一些if / else语句即可解决此问题,而无需任何复杂的数据结构。

现实情况是,许多团队和公司都面临算法挑战。我可以看到算法问题的吸引力:它们在45分钟或更短的时间内给您信号,问题可以轻松交换。因此,如果问题泄漏,危害不大。在招聘时,它们也很容易扩展,因为您可以拥有100多个问题的问题库,任何面试官都可以评估其中的任何一个。特别是在硅谷,听到针对动态编程或奇异数据结构的问题越来越普遍。这些问题将有助于聘请强大的工程师-但同时也会导致那些本可以在不需要高级算法知识的工作上表现出色的人拒之门外。

对于那些阅读其公司的酒吧的人,他们会招募那些精通一些高级算法的人:请再考虑一下这是否是您所需要的。我在伦敦Skyscanner和Uber Amsterdam雇用了出色的团队,没有任何棘手的算法问题,仅涉及数据结构和问题解决。您不需要完全了解算法。您需要做的是作为工具集了解最常见的数据结构,并提出简单的算法来解决当前问题的能力。

数据结构和算法是一个工具集

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

数据结构和算法是构建软件时应放心使用的工具。了解这些工具,您将熟悉使用它们的代码库。您还将对如何实施难题的解决方案充满信心。您将了解理论上的极限,可以进行的优化,并且会提出尽可能好的解决方案-考虑了所有权衡因素。

首先,我建议以下资源:

  • 阅读哈希表,链接列表,树,图,堆,队列和堆栈数据结构。尝试如何以您的语言使用它们。GeeksforGeeks 对这些内容有很好的概述。对于编码实践,我建议使用HackerRank数据结构集合
  • 所著的Grokking算法 通过阿迪亚巴尔加瓦是倒手在算法上最好的指南从初学者到经验丰富的工程师。这是一个非常平易近人且直观的指南,涵盖了大多数人在该主题上需要了解的所有内容。我坚信,您不需要了解更多关于本书的内容。
  • 《算法设计手册》和《算法:第四版》都是我当天拿起的书,以刷新我大学算法课程的一些学习内容。我中途放弃了,发现它们很干,不适用于我的日常工作。

在Hacker NewsRedditLobsters 阅读有关本文的评论。

来了,老弟
-------------    本文结束  感谢您的阅读    -------------
0%