一面出 LRU 算法题算难吗

[yuanyao]

面了几个三年经验 bat 大厂的候选人都没做出来，是不是难度高了

[iminto]

很低，基本功了

[vanpeisi7]

薪资范围多少，我能做出来哈哈哈

[iintothewind]

应该没刷题吧, 没刷题我也写不出来

[nomagick]

你那不叫算法题，叫背诵题

不是人家没没做出来，是人家没背诵出来

[cherbium]

可能没背这个吧，

[leegradyllljjjj]

装 B 为难别人谁不会啊，我随便从软考找几道题你能说清楚？

[lqw3030]

能写出来代表该候选人有什么素质，这个素质如果是岗位需要的就合理

[yoiteshaw]

我当面面试 amazon 实习岗位就这一道题，过了就拿 offer 了

[musi]

你现在实际项目中用到 LRU Cache 的地方你是纯手搓一个还是用有测试用例的成熟的三方库？

[yuanyao]

@musi 算法题基本在工作中都没用到过

[akakidz]

个人认为能讲出来思路就没问题，不过现在就业那么卷，要求给出最优解并且测试通过 也没问题。。。

[123zouwen]

面试出什么题目 问什么问题 是要看你们的产品/团队需要什么样的人才

脱离需求的面试问题,也招不来适合团队的人才

[iintothewind]

其实现在亚麻的面试也是差不多, 除了 BQ 题, 还会有 45 分钟面算法题, 就是从 leetcode 题库里面出 medium, hard 类似的题目, 要你写出 optimal solution, 而且不能出错.
说真的, 在如此短的时间, 能无错误的写出 optimal solution 代码的, 只能是你预先练习过, 背出来的, 但是没办法, 现实就是你不刷题, 这么考你就过不了.

所以, 我直接 GG 了, 无所谓.

老子就是不刷题, 不想浪费时间.

[Plutooo]

啥公司，发出来让大家避雷一下

[Ynna]

我记得还有一个常见的接雨水吧

[zy445566]

你要把逻辑一并放在题目中，只看是否实现感觉不难

[somebody1]

考算法题就是八股文，因为这玩意工作中很难用到，久而久之就忘掉了，只能说他面经有没有做到这块，做到这块就有跟你成为同事的缘分了，没做到没缘分。
说白了就是看运气。

一般来说，要问项目，项目问的细一点。算法的话就问那种肯定能做出来，但是不同的人做出来的效果不太一样的算法，边界条件略微复杂的算法，看看边界条件考虑的怎么样，来看工作中的细心程度。

[tyrantZhao]

这不算法高频题么？这没做出来的话，说明没准备呗。

[voidmnwzp]

五年经验 也做不出来 倒是应届生有可能写出来

[tigerstudent]

面试确实能体现一个公司的作风

[superchijinpeng]

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

[rolinbutterfly2]

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

[zdw189803631]

看不懂啊

[inhzus]

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

[SeaTac]

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

[iintothewind]

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

[reoah2]

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

[chesha1]

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

[hidemyself]

一眼 LinkedHashMap 。

[emSaVya]

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

[matrix1010]

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

[knva]

我写 LinkedHashMap 能过吗

[ghostwind]

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

[qwertyzzz]

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

[iOCZS]

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

请你设计并实现一个满足 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

[wxm]

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

[gejigeji]

确实是经典八股

[ho121]

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

[SeaTac]

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

[shawnsh]

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

[SeaTac]

@iintothewind
my bad 我记错了
lfu 不需要 linkedhashmap
至于 lru 看面你的人怎么想 可以先写出来再讨论怎么优化 或者直接问你有没有更好的办法 再去讨论

[iintothewind]

@SeaTac #39 你可能记错了, LinkedHashMap 才是 LRU 实现啊, 这是这个类的文档:

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries. This linked list defines the encounter order (the order of iteration), which is normally the order in which keys were inserted into the map (insertion-order). The least recently inserted entry (the eldest) is first, and the youngest entry is last.

不够 LFU 确实麻烦点, 适合口述实现思路, 自己写我没把握一次写对.

[Actrace]

其实就是公司不需要招人。

[iintothewind]

@SeaTac #41 唉, 无所谓了, 反正我不想刷题.
所以大厂要面白板算法, 我不会就 GG, 无所谓啦.

[Jerry23333]

是字节吗，实习秋招面了几次字节，都是各种 lru 及其变体打头哈哈

[xz410236056]

@inhzus 我目前算在大厂吧，实际工作中还不是 CURD ，就算需要缓存的地方，系统的 API 是优化过的算法，不是简单的 LRU ，比自己写的垃圾 LRU 性能更好更稳定。这玩意没背过很正常啊

[xz410236056]

@Plutooo 我知道微软是会问的

[mmdsun]

之前面微软做过。如果公司不是大厂的话，或者一开始没告诉要面算法别人没准备就通过率不高的，毕竟不是刚刚毕业都忘记了

[RadishWind]

之前是个还不错难度一般的题目 不过按照去年年底~今年年初面试的观感 话能说直溜带个脑子来面试已经谢天谢地了 完全不敢面算法 况且这个算法其实如果对面有递条子或者开狗屁通的话 其实不足以考察面试者水平

[yhxx]

我现在也写不出来
但是我去面试之前应该会背一下这些常见的
只能说还是太卷了，我也觉得这玩意没啥用

[whp1473]

不刷题我也做不出来，主要平时不需要从头实现，大致知道

[KingHL]

让我想起了在近十年前，我刚毕业找工作的时候，面试遇到 LRU 题目，从来没有见过，面试官给了足够的耐心和提示，一步步的从数据结构设计、接口设计到最终编码实现，整整花了一个多小时完成编码运行成功，我觉得这才是真正的编码考察，当时的面试官面试风格也深深的影响了我。可惜到后面大家刷题越来越多，面试节奏越来越快，编程面试成了刷题检验，没了解决问题的考察，所以我现在面试时只出数据结构题目，不出算法题目。

[pkoukk]

LRU 很简单啊，属于那种初见就能过的题了
我 TM 面字节的时候给我出 LFU ，还限制 20-30 分钟，我至今耿耿于怀

[otakustay]

不追求性能啥的，搓个普通的 LRU 是个程序员都应该会吧，再不济你搞个数组然后 swap 来 swap 去都行啊

[shylockhg]

这种只能筛选两种人，一种确实厉害算法精通，一种就是刷子

[incu]

LRU ，已经不仅仅是算法题了吧，不涉及计算，感觉更像一个设计思路，是常见的业务解决方案，开发过程中挺常用的。

楼上有痛骂这个 LRU 算法题的，能力是不是有点欠缺。。。

[meilicat]

不算 经典题了

[loveour]

@inhzus 确实挺标准的题目，而且上学学过算法的话应该也都学过。不过，刚毕业那会儿基本都会，等工作个几年一下子很可能想不起来。我早年刚毕业那会儿，还没有这个要考很多算法的风气，创业失败出来找工作，一下子面了好几个都喜欢问算法题，感觉就很不适应。
所以，我感觉，如果是大厂，好招人，不缺人，就是要筛，靠算法题无可厚非。但是说实在的，没必要把算法题看很重，毕竟就是刷题的问题。如果是缺人，就想找干活的，就真没要来这套了。

[ererrrr]

@KingHL 我草, 你让我想起我之前刚毕业面一个类似国企还是学校, 每道门都得指纹解锁, 0 经验面 C 语言, 其实我不会写 C, 但是我大概写了写, 那个人好有耐心帮我解答, 他应该是让我过的, 随后叫来他的上级, 他上级就比较"正常", 随后他上级就把我刷掉了, 他还送我出去, 大概意思是觉得我还不错. 确实想想, 现在都是起手八股, 跟以前不太一样.

[SeaTac]

@iintothewind
我觉得北美面试 system design 才是真正的八股文
再叠加现在的 bar

[qiuhang]

这个没啥难度吧，都不需要刷题，正经写了 3 年代码的应该都能写出来吧？顶多是实现不够优雅或者考虑不够完善？

[barathrum]

几年前的我会一堆数据结构和算法.

但是工作几年后因为日常工作一是用的太少了, 几乎不用自己写, 二是库提供的比我自己写的健壮且高效确实也没必要自己写, 现在我已经写不出来了.

[eedwinhei]

这稍微思考一下也不难吧？还需要背诵嘛？业务代码不比这复杂多了。。

[watzds]

很难，这种题目，我一上来就会想怎么做到高性能，怎么无锁实现，和已有产品比有什么优势

工作过的人考虑的多

[lazydao]

如果是工作中会用到的，该问就得问；如果不是，那真没必要。

[yuanyao]

@SeaTac 如果候选人没思路会一点点给提示

[inhzus]

@xz410236056 #46 大家都知道这玩意儿就是八股文嘛，和其它 leetcode 题目常见 100 题是并列的位置。工作中没人会用，但面试如果好好准备肯定会覆盖到。只能鉴定为楼主面试的候选人都没好好准备

[Akiya]

@lazydao 现在写 curd 的可以说是个人都会，但是你不整点门槛怎么选人

[ldyisbest]

这样会算过吗？我觉得不会算过


import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> {
private final int capacity;
private final Map<K, V> cache;

public LRUCache(int capacity) {
this.capacity = capacity;
// 使用 LinkedHashMap 并设置访问顺序为 true ，以便按访问顺序存储
this.cache = new LinkedHashMap<>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > LRUCache.this.capacity;
}
};
}

// 获取缓存中的数据
public V get(K key) {
return cache.getOrDefault(key, null);
}

// 向缓存中添加数据
public void put(K key, V value) {
cache.put(key, value);
}

public void printCache() {
System.out.println(cache);
}

public static void main(String[] args) {
LRUCache<Integer, String> lruCache = new LRUCache<>(3);

lruCache.put(1, "A");
lruCache.put(2, "B");
lruCache.put(3, "C");

lruCache.printCache(); // {1=A, 2=B, 3=C}

System.out.println("Get 1: " + lruCache.get(1)); // A
lruCache.printCache(); // {2=B, 3=C, 1=A}

lruCache.put(4, "D");
lruCache.printCache(); // {3=C, 1=A, 4=D}
}
}

[fregie]

只能说这个面试官不合格

[Rickkkkkkk]

如果不是线下面试，你出这种题只能招到用 AI 作弊的候选人。

[sagaxu]

口述算法不难，调用 lib 写出来也不难，不让调就太难了，半个小时还不够搓一个勉强可用的 hashmap

[20015jjw]

lru 不是有手就能写吗…

leetcode medium 实在不行给个 hint 能写出来
是基本要求吧

[sigma65535]

没做出来，把人面试给挂了吗

[snake2004]

@pkoukk 这种纯粹为了筛人，减少后续面试工作量～

[FabricPath]

不是，楼上一堆人说 LRU 是难、装逼？这不就一个 HashMap+双向链表，就算全手撸 hashmap 和链表，这也叫难吗？
还有说工作中用不到的，那你不如说“反正遇到不会的问 AI 就行了”。

面试是考察你思维方式，给你描述 LRU 的需求，你按照需求去实现，这和你工作中接一个需求有什么区别？
意思是 LRU 这个需求你做不出来，但是除了这个需求你其他的都能做得出来？

[wnpllrzodiac]

@nomagick 刷题，不用管为什么，背出来就好

[magggia]

哎，以前一面都只让人写个快排，二分查找，然后延展一下，我还是太仁慈了

[lyer5]

@magggia 没刷过题 硬想的话我觉得 LRU 比快排好写😂

[Erroad]

写是能写的，但非让我写我觉得是刁难。写个链表二叉树排序二分查找 dfs bfs 这种十来分钟稳定能考出来的不好吗

[ufan0]

不算难，说难的怕是忘了被 [手写红黑树] 支配的恐惧了。

说说我自己面别人的态度：
比如问 AQS 相关，候选人回答忘了或者记不清，我会直接让他打开 IDEA 本地查看源码，这时候能记起来或者分析清楚，对我来说更是加分项。

谁都会被八股文，但是真正理解和看过源码的，相当少数。

[CaptainTimo]

我刚刚去试了一下，这题之前肯定是刷过几遍的，但是对解题方法完全没有印象了。我没看题解重新做了一下，一次就写出来了，但肯定不是最优解，写成这样你给我过吗？


```
class LRUCache:
def __init__(self, capacity: int):
self.record = {}
self.capacity = capacity
self.r_list = []

def get(self, key: int) -> int:
if key in self.record:
self.r_list = [self.r_list.pop(self.r_list.index(key))] + self.r_list
return self.record[key]
return -1

def put(self, key: int, value: int) -> None:
if key in self.record:
self.get(key)
self.record[key] = value
else:
self.r_list = [key] + self.r_list
if len(self.r_list) > self.capacity:
self.delete()
self.record[key] = value

def delete(self):
del self.record[self.r_list[-1]]
del self.r_list[-1]
```

[bravecarrot]

工作十年， 全在大厂。 不刷题 临时写不出来。

[yuanyao]

@CaptainTimo 没问题，超过容量先删除再添加更符合题目描述

[yuanyao]

@magggia 快排比这个难吧

[yuanyao]

@ldyisbest 过不了吧，这直接用写好的三方库了

[yuanyao]

@yuanyao 说错了，系统库

[7gugu]

LRU 工作中极少机会用到吧，大多数都不需要手写缓存逻辑，写不出来感觉也很正常。

[yuanyao]

@123zouwen 需要会写代码、有系统设计能力，根据需求设计或改造系统技术方案并拆解实施的人才，这个我一上来把公司的需求文档给他们让他们给方案合理吗

[maxmax4max]

先说薪资多少，再说合不合理。

[sagaxu]

@FabricPath 你纸上撸一个 hashmap 试试，插入、查找、删除、遍历 4 种操作，带扩容/缩容，同槽高冲突优化，不用考虑并发访问，看看半个小时能不能写对

[otakustay]

这么说吧，LRU 根本不是算法题，它是个逻辑题，只要知道 LRU 代表什么意思，但凡有点逻辑的都应该搓的出来，剩下的无非性能好点坏点，能不能并发读写之类的

[Betsy]

我一般会要求候选人写个 链表节点的定义，这道题都放翻不少人了。OP 这道题估计放翻的更多 🤣🤣

[FabricPath]

@sagaxu 谁让你做优化了？你把 LRU 实现了先，用现成 HashMap 和 List 都写不出来 LRU 的人，还不配写 HashMap

[cabing]

我估计是写了，写的不太好，说明他们都没有准备的情况去面试。

这个已经很基本了

[mynameislihua]

不难吧，还是好理解的，提前准备一下也没啥

[specita]

天天泡业务代码里，这种算法突然让手写，一般也写不出来，最多给个思路，但是没办法，僧多粥少，是这样的。

[Donaldo]

@KingHL #50 人越来越多了，也就变成高考了。

[Donaldo]

这比什么图论平衡树 dp 的算法题简单多了

[AmazingEveryDay]

不难啊 是没有准备