一个关于亚马逊cache miss的疑问

lz收到了video，然后cache miss 用了一个linkedlist做完。看到地理貌似说有什么linkedhashmap版本，求问这个题有必要用这个么？如果用的话是什么思路，这个算是比一个linkedlist有提升么？
感谢地理小伙伴！

那是LRU cache 吧，Leetcode 原题那道，这里只是算个miss，不需要那么复杂的结构，帅哥加油面！

我觉得这个题linkedlist就很好了，请问楼主video时候对于这个题面试官提了什么问题呢？十分感谢！

我也是这道题 刚面完~
用hashmap+linked list可以把time complexity优化到O(m) m is the length of input array.
这里的hashmap以requested integer 为 value， 对应的linked list node pointer为value。这样在我们扫input array时，可以O(1) time check每一个integer是否在cache里。如果只有linked list那我们只能去遍历list确认了。这样总体的time complexity就变成了 O(m*n) n is cache size.

lxr 发表于 2016-2-18 07:32
我也是这道题 刚面完~
用hashmap+linked list可以把time complexity优化到O(m) m is the length of input  ...

十分感谢回复！很详细。这样说的时候要不要提一下空间换时间什么的？然后请问层主面试官是怎么问的呢？直接问优化方法？

fezfeng 发表于 2016-2-18 07:43
十分感谢回复！很详细。这样说的时候要不要提一下空间换时间什么的？然后请问层主面试官是怎么问的呢？直 ...

不用谢哈~
面试官木有问我这一道题= = 这是我当时准备video时想的
我的面经贴：http://www.1point3acres.com/bbs/thread-171898-1-1.html