微软采访| 14

我叫拉维·钱德拉。今天我参加了微软在班加罗尔的采访。我被一位顾问介绍。对海得拉巴发展中心各个团队的不同职位进行了采访。

我没能通过第一轮。但让我向极客的读者们分享我面临的问题。

问题: 所有手机都以某种方式存储联系人。原始手机的内存和处理能力更少。因此，设计一个存储联系人的数据结构。这应该使用尽可能少的内存，并支持算法高效运行。这个数据结构的基本操作是给定一个数字，如何查找联系人姓名，反之亦然。

最初我给出了一个hashmap解决方案。但他说，由于冲突等原因，hashmap操作的成本很高，并要求我提供更好的解决方案。我建议进行线性搜索。但他想要一个更好的搜索算法。

不幸的是，当我走出面试室时，我突然想到了更好的答案。

这个解决方案是这样的。假设每个联系人记录都有唯一的索引值。让我们维护两个排序的索引数组，一个基于电话号码，另一个基于姓名。因此使用的空间更少，搜索以O（logn）运行。

以下是主持人的一些想法：

由于手机功能有限，联系人数量也有限，通常为500到1000个联系人。联系人长度将受到限制，假设为64个字符。

手机至少包含两种类型的存储器：闪存和RAM。闪存存储软件和持久数据。RAM用于处理。

有各种各样的数据结构来实现高效的搜索。从数量上来说，根据我们假设的1000个联系人的功能手机，每个联系人的长度为64个字符，我们需要[1000*64*Nodesize]作为trie（近似值）。它的大小约为几千字节。我们通常有几兆字节的RAM。

如果trie对计划的RAM来说成本很高，我们可以使用三值trie或压缩trie。甚至我们也可以像某人指出的那样使用基于基数的搜索。

由于RAM成本高昂，我们可以在闪存中分配固定大小（比如1000）的连续块来存储这些联系人。我们只需要一个动态搜索功能就可以访问这些联系人。 崔 可以在用户启动搜索功能时内置在RAM中。甚至，由于数据是恒定的，trie可以静态地存储在闪存本身中。在联系人更新过程中，调用搜索功能时，将trie带到RAM。

请注意，联系人指的是一组数据，而不仅仅是电话号码。它还包括人名、联系人号码（一个或多个）、组、指定的快速拨号号码、图片等。在设计数据结构时，以数据为中心。在目前的情况下，搜索是包裹在这个数据结构上的简单功能。在我们的trie数据结构中，成功搜索的每一端都会指向存储在闪存中的匹配触点结构。

这纯粹是假想。根据所需的功能，实际实现将更加复杂。我希望这足够面试讨论了。在开始回答之前，从面试官那里获得足够的问题细节。如果你的思路正确，面试官会给你一些提示。

本文由拉维·钱德拉编辑。如果你喜欢Geeksforgek，并想贡献自己的力量，你也可以写一篇文章，然后把你的文章发到contribute@geeksforgeeks.org.出现在主页上的帮助和其他极客