lru-cache:编程求职面试设计问题-最近最少使用的缓存

每日编码问题：问题＃848 [困难] 谷歌询问了这个问题。 实现一个LRU（最近最少使用）缓存。 它应该能够使用缓存大小n进行初始化，并包含以下方法： set(key, value) ：将key设置为value。 如果缓存中已经有n个项目，并且我们要添加一个新项目，那么它还应该删除最近最少使用的项目。 get(key) ：获取键的值。 如果不存在这样的密钥，则返回null。 每个操作应在O（1）时间中运行。 分析 这是一个设计问题，包括数据结构和算法元素。 著名的是，哈希表为O（1），至少在许多查找中均摊销。 问题陈述似乎是一个很大的提示。 set()方法的语义意味着应使用固定大小的循环缓冲区来跟踪高速缓存中n个项目的使用时间或使用顺序。 每次调用get()时，请将其移至循环缓冲区的头部。 该程序何时调用set()呢？ 这会将项目放在LRU状态缓冲区的开头还是结尾？ 资料设计