一个编程难题让我最终在谷歌找到了一份工作。
2011年，我对当时的工作感到厌倦，开始寻找新的发展机会。在寻找的过程中，我的朋友丹尼尔（几年前我们一起开发了Novlet和Bitlet）转发给我一个链接，指向他当时就职的公司ITA Software的招聘页面。
在谷歌收购ITA Software期间，ITA仍有一些职位空缺需要招聘。但与谷歌不同的是，ITA要求应聘者在申请工程师职位之前先解决一个编程难题。
需要解决的问题种类繁多，从纯粹的算法挑战到范围更广但仍需深厚技术洞察力的问题，应有尽有。浏览所有选项后，我最终选定了一个令我感兴趣的问题，因为我觉得它类似于我将来在现实世界中可能遇到的问题，而且似乎既考察了我的知识广度（它需要扎实的全栈技能），也考察了我对深层技术细节的理解。
我对当时研究这个问题并找到解决方案的那段时间记忆犹新。完成后，我不仅学习了一种新的数据结构（后缀树），还对Java的内部机制有了更深入的了解。一年后，我获得了一份工作机会，这在一定程度上要归功于我解决的这个难题。
问题陈述
本次挑战的简要说明如下：
即时搜索
编写一个 Java Web 应用程序，提供对国家史迹名录中列出的房产进行“即时搜索”的功能。该应用程序无需等待用户点击提交按钮，而是会在用户输入内容时动态更新搜索结果。我们提供了一个文件
nrhp.xml.gz，其中包含从名录数据库中选取的部分信息。数据库：服务器端应用程序的关键组件是一个高效的内存数据结构，用于查找属性（纯 Java 编写）。一个好的解决方案可能需要几分钟才能加载完成，但在现代 PC 上，查询响应时间可以远低于 0.1 毫秒。（请注意，顺序搜索所有属性可能太慢！）如果输入的内容出现在属性名称、地址或城市+州/省的任何位置，则该输入与该属性匹配。匹配不区分大小写，并且只考虑字符 AZ 和 0-9，例如，输入“mainst”匹配“200 S Main St”，“red”匹配“Lakeshore Dr”。请注意，服务器的 JVM 将配置为最大 1024M 堆空间。
nrhp.jar创建数据库时，请遵循指定的接口。Servlet：您的 Servlet 应接受一个输入字符串作为 GET 请求的请求参数。结果应包含预设数量（例如 10 个）的属性信息、数据库中匹配项的总数以及搜索算法所花费的时间。您的 Servlet 应该是无状态的，即不依赖于任何用户会话信息。此外，还可以对结果进行分页显示！
客户：您的网页应使用 JavaScript 的 XMLHttpRequest 对象访问 servlet。当用户输入内容时，您的界面应不断更新搜索结果列表，而无需刷新页面。您的图形用户界面 (GUI) 无需复杂，但应简洁美观。
请提交 WAR 文件、配置说明、源代码以及您对方案的任何意见。您的应用程序将在 Sun 的 64 位 J2SE 平台上的 Tomcat 和最新版本的 Firefox 浏览器中进行测试。
客户
我是从用户界面开始逐步构建的。
谜题简介中提到要使用[此处XMLHttpRequest应填写具体库名称]，所以我避免使用任何客户端库（毕竟，我被要求在客户端实现的功能非常简单）。
谜题简介中附带的截图只包含一个用于输入搜索查询的文本框和一个搜索结果列表。
我编写了一个函数来监听按键事件，向服务器发起异步调用，并在收到响应后立即渲染结果。到 2011 年，我已经从事 Web 应用程序开发一段时间了，因此我只用了不到一个小时就实现了这个功能。
Web应用程序和Servlet代码
Servlet 层也很简单，因为它只需要处理传入的 XML 请求并将其分发到简报中提到的数据库。同样，这部分工作不到一个小时就能完成。
在这个阶段，我还编写了代码，用于解析包含国家史迹名录数据的 XML 文件，并将解析后的字符串数据库建立索引。Tomcat 服务器会在加载我的 Web 应用程序时运行这段代码，并使用解析后的数据构建一个数据结构，作为索引，以支持我需要的快速搜索功能。接下来我需要解决这个问题。
寻找合适的数据结构
不出所料，这是整个难题中最具挑战性的部分，也是我投入最多精力的地方。正如题目描述中所述，按顺序遍历地标列表是行不通的（耗时远超0.1毫秒的目标阈值）。我需要找到一种在查找操作方面具有良好运行时间复杂度的数据结构。
我花了一些时间思考如何实现一种数据结构，以满足此场景下所需的快速查找速度。我最熟悉的快速查找方案——哈希表——并不能直接解决这个问题，因为它要求搜索操作必须使用完整的键字符串。
然而，在这个问题中，我希望即使给定的子字符串不完整，也能在索引中查找条目，这就需要我将所有可能的子字符串都作为键存储在表中。
在纸上画了一些草图后，我们认为使用三角形会更有效。
后缀树
在研究能够根据部分字符串提供快速查找操作的数据结构时，我偶然发现了一些引用后缀树的论文，后缀树常用于计算生物学和文本处理，它提供的查找操作的运行时间与要查找的字符串的长度呈线性关系（而不是与要搜索的字符串的长度呈线性关系）。
然而，普通的后缀树旨在在单个较长的字符串中查找给定候选字符串序列的匹配项，而这个谜题的用例略有不同：我需要在多个字符串中查找匹配项，而不是在单个长字符串中查找。幸运的是，我查阅了一些资料，找到了许多论文，其中介绍了一种名为广义后缀树的数据结构，它正好可以实现这个功能。
根据我目前所了解的情况，我确信这种树能够满足我的需求，但我可能面临两个挑战：
- 后缀树往往比它们索引的字符串占用更多的空间，并且根据问题陈述，“服务器的 JVM 将配置为 1024M 最大堆空间”，这需要容纳 Tomcat 服务器、我的整个 Web 应用程序以及我想要构建的树。
- 使用后缀树的难点很大程度上在于构建树本身。虽然题目要求明确指出我的解决方案可能需要“几分钟才能加载”，但我并不想让审阅者等待几个小时才能测试我的提交内容。
Ukkonen 的线性运行时间树构建算法
幸好，我找到了一种流行的算法，可以在线性时间内生成后缀树（与要索引的字符串的总长度呈线性关系），该算法由 Ukkonen 在 1995 年发表的一篇论文中描述（在线构建后缀树）。
我断断续续地花了几天时间（记住：我是在晚上和周末做的——那时我还有另一份白天的工作）才让我的后缀树按预期工作。
有趣的是，这一阶段的一些挑战围绕着一个完全出乎意料的主题展开：Ukkonen 的论文包含了用伪代码编写的完整算法，以及详细描述核心步骤的精彩文字。然而，这些伪代码的抽象程度太高，以至于需要花费一些精力才能将其转化为快速高效的 Java 代码。
此外，伪代码算法的编写假设我们正在处理一个表示为字符数组的单个字符串，因此其中概述的许多操作都与该大数组中的索引有关（例如上面过程中的k和i ）。
String相反，在我的 Java 实现中，我希望尽可能多地使用对象。这主要出于以下几个原因：
- Java 默认实现了字符串驻留——通过手动操作表示包含字符串的字符数组中的索引来表示子字符串并不会节省内存：JVM已经为我们透明地完成了这项工作。
- 使用
String参考资料编写的代码对我来说更容易阅读。 - 我知道下一步是将算法推广到能够处理在多个字符串上建立索引，如果我必须处理关于哪个字符数组代表哪个输入字符串的底层细节，那将会困难得多。
广义后缀树
最后一点至关重要：将我之前构建的后缀树推广到可以处理多个输入字符串的操作相当简单。我只需要确保树中的节点能够携带一些有效载荷，指示索引中的哪些字符串与给定的查询字符串匹配。这一阶段的工作量大约花了几个小时，但这完全是因为我编写了完善的单元测试。
这时，一切进展顺利。我花了大概两天时间阅读关于后缀树的论文，又花了两天时间编写了目前为止的所有代码。我准备用谜题简报中提供的输入数据来运行我的应用程序：整个国家史迹名录，一个总计几百兆的 XML 数据流。
经受烈火的考验：OutOfMemoryError
我的应用程序首次运行令人失望。我启动了 Tomcat 并部署了我的 Web 应用程序归档文件，这触发了对作为输入提供的 XML 数据库的解析，并开始构建通用后缀树，以用作快速搜索的索引。后缀树构建不到两分钟，服务器就崩溃了OutOfMemoryError。
我拥有的1024兆字节空间不够用。
幸好几年前我曾与一位客户合作，他们在节假日购物高峰期遇到了电商网站宕机的难题。他们的服务器频繁崩溃，原因是内存不足。这件事促使我学习如何读取和分析JVM内存转储文件。
我从没想过会在自己的项目中用到这项技能，但这个谜题让我改变了看法。我启动了VisualVM，开始寻找内存消耗最大的部分。
很快我们就发现，有一些内存分配模式效率低下。对于一般应用程序来说，其中许多问题几乎无关紧要，但由于构建的树状数据结构规模庞大，这些问题最终都产生了影响。
内存微优化
分析一些堆转储文件后，我发现了一系列可以节省内存的可能更改，但通常会增加复杂性，或者从通用数据结构实现（例如映射）切换到针对此用例及其约束条件量身定制的专用等效实现。
我根据预期投资回报率对可能的优化方案进行了排名（即比较节省内存的价值与额外的实现复杂性、较慢的运行时间和其他因素），并实现了列表中排名前列的一些方案。
最具影响力的改变涉及优化后缀树节点的内存占用：考虑到我的应用程序需要构建一个非常大的图（包含数万个节点），任何来自更高效的节点表示的微小节省最终都会产生有意义的影响。
后缀树节点的一个特性是，任何出边都不能使用前缀相同的字符串进行标记。实际上，这意味着实现节点的数据结构必须保存一个指向一组出边的引用，这些出边以标签的第一个字符作为键。
我的第一个解决方案是用一个数组HashMap<Character,Edge>来表示这个数组。但当我查看堆转储文件后，我发现这种表示方法对于我的用例来说效率极低。
Java 中的哈希映射初始化时加载因子为 0.75（这意味着它们通常会为比任何给定点实际拥有的键/值对多至少 25% 的内存预留空间），更重要的是，初始容量足以容纳 16 个元素。
后一项尤其不适合我的使用场景：因为我使用英文字母（26 个不同的字符）对字符串进行索引，所以大小为 16 的映射表足以容纳超过一半的可能字符，这通常会造成浪费。
我可以通过调整大小和负载因子参数来缓解这个问题，但我认为切换到专门的集合类型可以节省更多内存。
标准库中包含的默认映射实现要求键和值类型是引用类型而不是原生类型（即映射的键是 `<key>`Character而不是 `<value> char`），而引用类型往往内存效率低得多（因为它们的表示更复杂）。
我编写了一个专用的地图实现，名为EdgeBag，其中包含一些调整：
- 存储了键和值以及两个并行数组，
- 阵列会从小规模开始，如果需要更多空间，则会逐渐扩大。
- 如果袋子中元素数量较少，则采用线性扫描进行查找操作；如果袋子中元素数量较多，则改用对已排序键集进行二分查找。
- 用于表示键中字符的 Java 16 位类型
byte[]（而不是）占用的空间是 的两倍。我知道我的所有键都是 ASCII 字符，因此我可以放弃对 Unicode 的支持，并通过强制转换为更窄的值范围来进一步节省空间。char[]charbyte
关于此更改以及其他减少我的后缀树实现内存占用的更改的更多具体细节，请参阅后缀树项目页面的“特定问题优化”部分。
结论
在进行内存优化后，我测试了我的程序，很高兴地发现它满足了问题要求：查找速度非常快，在我当时的机器上（基于 Intel Q6600 2.4GHz CPU）远低于 0.1 毫秒，而且我编写的单元测试也让我确信该程序按要求运行。
我将解决方案打包成 WAR 归档文件，编写了一个简短的 README 文件，概述了设计考虑因素和运行说明（只需部署在裸机 Tomcat 6 服务器上），然后通过电子邮件发送出去。将近一年后，我收拾行囊前往阿姆斯特丹，加入谷歌（当时谷歌已经收购了 ITA Software）。
这很大程度上要归功于我在解这个编程谜题时获得的乐趣。
回想起开发 Instant Search 的那段时光，我非常享受，我想这一定是因为它既需要广博的知识（设计一个完整的全栈应用程序，尽管它很简单），也需要深入的知识（研究最适合这项工作的数据结构，并根据需要进行优化）。它让我能够将我的通才背景与我对计算机科学理论基础的兴趣结合起来。
精心设定内存和运行时限制作为问题要求的一部分，让挑战变得更有趣。当我编写的第一个版本无法正常运行时，我能够运用之前使用内存分析工具的经验，确定需要进行哪些优化。与此同时，我对 Java 的内部机制有了更深入的理解，并学习到了许多之前习以为常的实现细节。
当ITA停止开发即时搜索（以及其他编程谜题¹）时，我决定将Java通用后缀树开源，供其他人使用。尽管我最终针对特定问题进行了许多优化，但它仍然足够通用，自开发以来已被其他一些应用程序使用，这让我又多了一份值得庆幸的事情。
我撰写有关编程、软件工程和技术领导力的文章。您可以在 Twitter 上关注我，获取更多类似文章。
本文最初发表于abahgat.com，日期为 2019 年 9 月 30 日。
文章来源：https://dev.to/abahgat/the-programming-puzzle-that-landed-me-a-job-at-google-1pc0