一面出 LRU 算法题算难吗

@yuanyao 你的团队真的需要会 LRU 算法的人才，还是需要一个可以熟练使用的？

我在工作中的代码写过，但是过了两年基本又忘记了

看不懂啊

标准题啊，我都怀疑楼上觉得难的有没有在大厂工作过或者就压根不在这个行业。LRUCache 、共享指针、归并链表，就那么几道常见题，又不是 leetcode 几百题号甚至一千以后的

lru 没啥算法吧 又不是 lfu
一个 hashmap 一个 double linked list 这都是挺基础的结构
但是你是怎么面的呢 是一边讨论一边写还是啥都不说直接问呢

@SeaTac #25 我要说直接用 java 的 LinkedHashMap,估计也会挂吧.
所以工作写的代码, 跟面试做题, 真的不一样.

面三年的可能写不出来，但是你去面实习生和校招生，绝对给你背下来

不难，在 HOT100 的范围内，正常准备准备是应该做出来的，但是出这种题基本可以认为是前面没聊好，对候选人没兴趣了

一眼 LinkedHashMap 。

lru 写不出来可以说根本就没把面试当回事 这种题正常情况下应该都刷烂了。

像 LRU 这种问题，无论你刷没刷过题，刚毕业还是工作了 10 年，只要还在做程序员就应该能写出来。 从直觉上就应该知道用 doubly linked list + hashmap

我写 LinkedHashMap 能过吗

冷知识，BAT 面试是反转链表

@matrix1010 直觉上我只知道是个什么最近最啥的算法，处理什么不常用的数据的？完全没印象了。

不要考察概念，应该把算法的过程描述出来。像下面这样描述我觉得，题目难度还行。

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
————————————————

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接： https://blog.csdn.net/qq_33919114/article/details/137032977

lru lfu 经典算法八股，估计是对方没准备好

确实是经典八股

我记得算法导论中 LRU 是用 HEAP 来做的，综合性能是最优的

@iintothewind
lfu 才用得到 linkedhashmap ，不过 lfu 主要的麻烦点不是这些数据结构，而是 code 太多，一个小时很难写完
lru 还行，这种题目拿来边讨论边写 code 挺好的

其实没啥意思，你可以出一个没见过的算法让人做，毕竟 LRU 有人会背题目