译者：Gergely Orosz
电脑之心校对
参予：竹筏、杜伟
计算机程序和此基础演算法做为软件工程的recommend专业课程，近
日常生活组织工作中，你时常采用演算法和数据结构吗？曾供职于 Uber 等信息技术子公司的技师 Gergely Orosz 明确提出了这种两个难题。除此之外，他也注意到，愈来愈多的人真的演算法是而已的，并指出它而已信息技术子公司明确提出的一类硬性举措而已。
责任编辑译者 Gergely Orosz。
除此以外，也有更多的人埋怨称演算法而已单纯的学术研究练。在 Homebrew 译者 Max Howell 刊登他的Google复试历经后，这种的设想被更进一步普及化。
虽然 Gergely Orosz 自己也从来不需要采用二叉树翻转（binary tree inversion），但是他在 Skype、Microsoft、Skyscanner 以及 Uber 组织工作时，每天都会遇到采用数据结构和演算法的情况。
除此之外，他有时也需要基于这些概念编写代码和做出决策。最后，Gergely Orosz 借助这些知识来理解有些事物如何和为何构建，以及如何采用或修改它。
由此可见，计算机程序和演算法并不是如人们所言用处不大。在责任编辑中，Gergely Orosz 列举了一系列现实世界的实例，包含生产中会用到的树、图等计算机程序和各种演算法。
值得肯定的，所有这些都出自他的第一手经验，借此希望表达他的观点，即通用计算机程序和演算法知识并不而已「为了复试」，而是你在快速成长的创新型信息技术子公司组织工作时，可能会时常遇到的东西。
Gergely Orosz 表示自己曾经用过非常小的演算法子集，但几乎包含了所有的计算机程序。毫不奇怪，他不喜欢繁琐的演算法以及包含红黑树或 AVL 树等不常见数据类型的不切实际的复试难题。
接下来具体来看译者列举出来的实例，以第一人称的口吻进行讲述。
树和树遍历：Skype、Uber 和 UI 框架
在Google时，当我们构建 Xbox One 游戏机（由Google发布）的 Skype 软件时，我们采用的是内置操作系统 Xbox OS，但缺少关键库。我们当时正在该平台上构建首个成熟的应用程序之一，所以需要两个能结合触摸手势和语音命令的导航解决方案。
我们在Google WinJS 库上构建了两个通用的导航框架。为了做到这一点，我们需要维护两个类似于 DOM（文档对象模型）的图来跟踪可操作的元素。为了找出这些元素，我们执行了 DOM 遍历，基本上是现有 DOM 上的 B – 树遍历（B-tree traversal）。这便是 BFS（广度优先搜索）或是 DFS（深度优先搜索）的经典示例。
在 Uber 时，团队构建了很多实现节点、依赖关系以及它之间连接可视化的工具。有两个例子就是 RIB 节点的可视化工具。该可视化工具需要维护一棵树，将它可视化为可缩放矢量图形（SVG），然后更新这棵树，同时移动设备上的 RIB 树也发生变化。RIB 自己也会为状态管理维护两个逻辑树结构（logical tree structure），但这个树结构与呈现对象不同，这就是他们设计背后的关键所在。
RIB 树可视化：两个采用树来表示数据并将其可视化的经典示例。
权重图和最短路径：Skyscanner
Skyscanner 会找到最佳机票。为此，它扫描了全球所有的航线，并将它汇聚在一起。由于航空子公司需要考虑中转站的选择，所以难题的本质更多地体现在爬虫，而不是缓存。多城市规划选项（multi-city planning option）成为了最短路径难题。
多城市是 Skyscanner 花费大量天数来构建的功能之一。公平地说，产品方面的困难是最多的。最佳的多城市航线选择就是采用 Dijkstra 或是 A * 这种的最短路径演算法计算的。
航线用一张有向图来表示，每条边都有两个表示票价的权重，算出两个城市之间票价最便宜的航线就是通过每条航线的改进版的 A * 搜索演算法实现的。
但是采用 Skyscanner，实际演算法就不那么重要了。缓存、爬虫和处理各种网站负载比解决难题本身要难得多。即便如此，最短路径难题的变体还是在许多基于组合优化价格的旅行子公司中采用。
排序：Skype
对于排序这种演算法，我很少需要自己实现或深入采用。理解不同类型的排序方法是件很有趣的事，包括冒泡排序、插入排序、归并排序、选择排序以及最复杂的快速排序。但是，我还是很少需要自己手动实现这些演算法，甚至从来没有把排序函数做为库的一部分来编写。
在Google Skype 时，我练了这方面的知识。另有一位技师决定为联系人列表实现插入排序演算法。2013 年，Skype 实现了联网，网络用户呈爆炸式增长，而且用户数还在持续增长。因此这位技师指出用插入排序按照用户姓名来构建联系人列表，性能会更佳。
关于为什么不单单采用默认排序演算法这一难题，我们也经过了反复讨论。最后结论是，采用默认排序演算法需要对实现进行适当的测试和相应基准测试，这可能需要更多的组织工作。我个人指出这种做没有多大意义，因此当时我们正处在项目阶段，有很多天数，所以采用了基于联系人列表的插入排序演算法。
在现实世界中，一定有一些情况，采用高效的排序演算法非常重要，因此基于数据选择采用的排序演算法会更加有效。在执行大规模实时数据流因此为这些数据源构建实时可视化时，插入排序很有用。
如果涉及到存储在不同节点上的大量数据，那么「分而治之」的归并排序演算法比较合适。我自己没有采用过这些演算法，因此了解这几种不同的演算法之外，我仍然会标记一些自己没有用过的排序演算法。
哈希表和哈希：随处常见
我最常用到的计算机程序就是哈希表以及哈希函数了。从计数、重复检测、缓存到分片（sharding）之类的分布式系统用例，都会用到这种很方便的工具。
除了数组之外，在很多情况下用哈希表和哈希函数都是非常合适的。几乎每种语言都会用到这种计算机程序，而且它的实现很简单。
栈和队列：偶尔用到
任何调试过具备堆栈追踪的语言的人都非常熟悉这种计算机程序。我在采用这种计算机程序时遇到了一些难题，但调试和性能分析让我慢慢熟悉了它。
我很少在自己的代码中采用队列这种计算机程序，但却在代码库、代码 pop 和 push 中遇到过很多次。对于分析和配置 builds 的安装瓶颈检测器工具而言，我会采用 Python 堆队列（heap queue）演算法来读优先队列优化后的代码。
加密演算法：Uber
Uber 很早就采用了几种语言和技术，因此加密（cryptography）并不能实现我们需要的稳定性。典型的示例就是 iOS 和安卓。来自客户端用户输入的敏感信息在通过网络发送之前需要加密，同时仅针对特定服务进行解密。
在某些情况下，我们必须自己构建加密 / 解密实现。但在缺少支持框架或没有可用审核库的情况下，我们需要对其进行正式的验证和审核。
构建加密演算法总是充满乐趣。在实现加密演算法上存在许多挑战：你想不出一类实现加密技术的新演算法。取而代之的是，你将采用适合案例的现有的已成文的标准，然后验证并一遍又一遍地审核它。
这种情况就是在实现 AES 标准。这是两个有趣的挑战。我们已经构建了一些移动端和网页端的加密实现，其中我自己深入学习了高级加密标准（AEP）、哈希消息身份验证码（HMAC）以及 RSA 公钥加密的详细知识。
研究攻击媒介（如消息篡改或拒绝服务的影响）是审核解决方案的一部分。验证一系列加密步骤是否可以证明是安全的，这
也是一件有趣的事。
只要证明 Encrypt-and-MAC（EaM）、MAC-then-Encrypt（MtE）和 Encrypt-then-MAC（Etm）三者有两个是安全的即可，但这并不意味着其他的是不安全的。
概率论与预测：Uber 的 SubmitQueue
2016 年，我加入了 Uber。移动端最大的痛点是构建以及合并更改需要花费的天数。从构建和所有测试（单元、集成和端到端）开始，构建两个完整的运行大约需要 40 两分钟。我们在开发中投入了大约 300 个开发者。所有的更改必须在落地之前搭建完成。
我旁边的开发者体验团队想解决以下难题，他们从两个角度做到了。首先，他们加快了构建和测试过程，耗时不超过 30 两分钟；其次，他们的目标是每个人的变更应该花费 30 两分钟，现有天数的 95%。
但是合并冲突呢？让我们对其进行预测，并相应地建立队列。这就是他们通过创建冲突和推测图所做的事情。
带有层次化索引的六边形网格：Uber
这是我没有参予的最后两个项目，但是我发现并采用了基于它的工具。在这里，我了解了一类新的计算机程序：带有层次化索引的六边形网格。
Uber 要解决的最困难和最有趣的难题之一就是优化行程价格以及合作伙伴的调度。价格是动态的，驱动程序也在不断变化。H3 是 Uber 技师构建的网格系统，旨在以愈来愈细化的水平可视化和分析整个城市的数据。数据可视化结构就是带有层次化索引的六边形网格。
总结
这些是我多年来在多家子公司中实际采用的演算法和计算机程序的重点。
要在一家高信息技术子公司组织工作，你不需要了解流行演算法或是外来计算机程序的组织工作原理。你应该了解演算法是什么，因此能自己明确提出一些简单的演算法，例如贪婪演算法。你还应该了解更多常见的基本计算机程序，例如哈希表、队列、栈等等。但是你不需要记住 Dijkstra 或是 A* 这种特殊的演算法。
你可以将它做为参考，就像我实现加密演算法时一样。对待红黑树或 AVL 树等一些不常见的计算机程序也应如此。我从未用过这些计算机程序。即使我用过，也不会反复查看它。我也从来没有问过需要采用这些知识才能解决的难题，将来也不会。
我一直在寻求一些实际的编码例子，因为实际的例子中会有很多好的解决方案，比如暴力枚举、贪心演算法或其他一些更复杂的演算法。比如，有些难题，你只需要两个数组和一些 if/else 语句就可以解决难题，而无需任何复杂的计算机程序。
现实情况是，许多团队和子公司都面临演算法的挑战。应该看到，演算法难题具备非常大的诱惑力，它能在 45 两分钟或是更短的天数内得出讯号，因此随心所欲地切换难题。因此难题泄漏带来的影响并不会很严重。
招聘也比较容易。因为你可以拥有 100 多个难题的难题库，任何复试官都可以评估其中的任何两个。特别是在硅谷，听到动态编程和特殊计算机程序难题的情况愈来愈多。这些难题将有助于聘请强大的技师，但同时也会导致将那些本不需了解一些复杂演算法但却非常优秀的人拒之门外。
原文链接：https://blog.pragmaticengineer.com/data-structures-and-algorithms-i-actually-used-day-to-day/
