10.28 Google面经回馈（附个人解法）

qiuxuxing007 发表于 2016-11-3 19:27
楼主运气不好， 碰到烙印。。

都是命

第一问 lc 379, lru cache是不是就是lc 里面lru cache的题目一模一样?

qiuxuxing007 发表于 2016-11-4 08:03
第一问 lc 379, lru cache是不是就是lc 里面lru cache的题目一模一样?

第一问不是LC 379，那题是看下一个可以使用的号码，而这题是名字检索。第二问就是经典LRU。

请问iz 第一次是找到以输入子串为前缀的所有名字吗？如果只是包含该子串的话，如何利用trie呢？followup是什么样的呢？

chaosMonkey 发表于 2016-12-11 17:52
请问iz 第一次是找到以输入子串为前缀的所有名字吗？如果只是包含该子串的话，如何利用trie呢？followup是 ...

是以输入串为子串的所有名字。可以利用后缀数组来找 :)

nevets 发表于 2016-12-13 00:24
是以输入串为子串的所有名字。可以利用后缀数组来找 :)

非常感谢lz的回复，请问你在题中提到的trie的作用是不是仅仅用作存储电话簿的数据结构呢？电话簿中的数据是什么样的形式的呢？怎么把姓名和号码结合在一起的呢？
这样的话，trie和后面的用后缀数组查找子串是不是没什么关系？

chaosMonkey 发表于 2016-12-13 00:55
非常感谢lz的回复，请问你在题中提到的trie的作用是不是仅仅用作存储电话簿的数据结构呢？电话簿中的数据 ...

Trie和suffix array只是作为索引，能更好的执行 “查找包含某一子串” 这一任务而已。具体电话mapping可以非常直接的用hashmap做。

楼主，第二面第二问可否讲的详细一点，没想出来怎么解