面试大厂的必考题 - 刷题的必经之路 - LRU

https://www.1point3acres.com/bbs/thread-1100664-1-1.html
上次的文章大家反响很好，今天就和同学们讨论一个具体的例子吧。


LRU可以说是我在LC上最喜爱的一题。虽然我自己面试从来没有碰到过，但是身边朋友已经有三个碰到过。一个挂了。


这题是难得的，能和实际运用的技术紧密结合，并帮助程序猿理解后台的一道标准化考试题。如果说，大部分LC题是数学题，这题就是最好的一道应用题。


对新手来说，碰到这题可以说是残忍的，因为答案看了都很长，强行记忆是不现实的。记住需要一个HashMap，一个doubly linked list，剩下的，就要靠基本功和理解了。而对于有了几年工作经验，使用过redis等工具的同学，这题就相当于一个最好的学习工具。因为我本人早期一直做service，刷到这题，当时我惊为天人，原来后台就是这么写的。


而面试官可以问出许多问题，尤其是看到程序猿很快速开始码代码，没有先介绍清楚自己的design，往往就容易得出结论这家伙是背的。其实因为大家都知道这题字数多，多多少少都准备过，一听这个题往往就容易想着赶紧码字，唯恐时间不够了。这样容易落入错误的境地。20分钟包括讨论其实够了，就算没有写完，拖了十分钟，如果讲的清楚，面试官应该跳过下一题，足够得出好的结论了。


我觉得，这里不如讲两个朋友的实战经验，更容易讲清楚此题怎么面。


故事一：
面试官是同胞经理，面试人不是同胞。位子是senior。
面试官：你们平时用不用cache?
面试人：yeah,we use redis. not only for caching the data, I also use it for rate limiters, blah, blah...


面试官：如果哪天, for whatever reason, 不让大家用redis了，你咋办?
面试人：(这是啥意思？）we can use other products, like memcache, it's light weight, less built-in functions, but also a popular key-value store.....


面试官：(打断）no, no third party products
面试人：（他想说啥？）then we use in memory cache classes, there are also other libraries that we can use...


面试官：（打断）no, no libraries
面试人：（不会吧，不会是要我写个LRU吧，刚才不是system design interview吗）Java has built-in key value store, HashMap, that we can use and expand, we can just wrap it up and enhance it.


面试官：不行，我们app自己的memory都不够用了。
面试人：（哦，那还是system design）I get it. In that case, we should design our own caching service, and consider future reuse. Let's draw it on the whiteboard.


下面，面试人在board上画了简单的一个caching service长方形，client可以是不同的services，后台可以有optional的db，做persistence，但只是提一下。重要的是几个API定义好，get, put, create, delete 等。这里提到了LRU，LFU的不同功能，都应该可以选，是create API的parameter里面让client决定。而且这里cache value应该是class，而不是string或者Integer。几个API的expected time complexity都是接近O(1）。key可以选number或者string。需要capacity来控制size以免overflow，还需要定义TTL，并决定哪一步清理过期的data。这里可以解释每次清理expired data会导致time complexity大于O(1)，可以讨论是否写个batch来清理。这个design是不需要DB的，用户发现cache miss后，应该由client端决定DB call。如果想用write thru就复杂了，用户需要提供DB callback。


面试官：（开始点头，终于上路子了）行，让我们选个简单的写写，就LRU吧
面试人：（我靠，又改成coding了，图穷匕见啊，你耍我吧，时间还来得及吗，大哥你早讲啊）no problem, since we are running short on time, can we simplify a little and just assume the key is string, and value is generic type, and skip TTL and capacity control?


面试官：ok ok
面试人：（这里就开始手搓代码了，先写API的框架，然后解释说现成的KV store是HashMap，但是为了sort by usage时间，及时挪动，需要加一个doubly linked list，这个一定要别写边讲，或者先停下来，讲清楚为什么用了两个data structure再开始写。如果等面试官问出这个问题，就有点晚了。）


面试官：你还有几分钟，你觉得哪里不够好的可以改进？
面试人：we still have a few mins, we can add capacity control, expiration control, both are critical part. capacity control is easy to implement. how about we design a system to clean up expired data?


面试官：(有两下子啊，这里写capacity容易，就是LC上有的，这家伙宁愿选难点的）
面试人：（其实我题目背的不熟，但clean up batch job最近工作里刚写过）Overall, we have two strategies, proactive cleanup and reactive cleanup. Let's only design a batch job which is a proactive clean up here. blah blah.....


以上由真实故事改编，最后朋友拿到了offer。


希望同学们能注意到，LC里面的原题为了简单化，key value都是integer，但是现实生活里，不可能这样简单。所以这位面试人故意用了string做key，object做value，coding工作量一样，但是能成功地展示一下自己不是背诵的答案。如果时间充分，应该利用这个机会讨论一下怎么在create的时候，加一个parameter，让用户来定义key type。


类似的讨论点，还有get的时候，如果cache miss了，就是key not exist的情况，LC是让我们return -1，这个在现实生活中也是不合理的，（为什么不合理？同学们可以思考一下，这里面试官往往会challenge你）好的面试官看你这么写，肯定要问一下为什么写成这样，所以要主动解释一下，如果是面亚麻或买它，因为不需要compile，这里应该throw KeyNotFoundEexception。


还有许多讨论点，比如capacity应该是create的时候的一个optional parameter。用户不给，就用一个default的。caching service怎么做monitor等等。batch cleanup是不是可以在monitor发现快要out of memory了，再触发。怎么处理multi thread。


好，最后讲一个朋友挂的例子：
面试官：Let's design a cache
面试人：（哈？今天不是coding 面试吗？怎么改system design了）。。。。。。
. 1point 3acres

事后朋友说他当时大脑一片空白。天竺面试官这是刁难我吗？叫我design一个cache，这个是啥啊。我说那不就是LRU LFU吗，你不是很熟的吗？我们不是还讨论过吗。他才恍然大悟，根本没有把这道LC题和design a cache联系起来。


上面那位同胞面试官是一个很优秀的面试官，如果你开始面试，面试官copy到左边LC LRU的description和examples，那么恭喜你，这个面试官几乎就是在放水了。只需要按照LC的答案稍微改改就能过，当然，写之前，还是要clarify一下，我们key就是int啊，好啊好啊，为了简单化，value也是int啊，好啊好啊，in reality应该可以是blah blah。cache miss就return -1？好啊好啊，太好了，我们如果value是object，应该return null或者throw exception。


也曾经面过小厂，面试官往往就是把LC上选好的题目的description原封不动直接copy一下，这种就是他们自己都没有完全理解，没有能力改动题目，改了自己可能就看不懂code了。但是必须承认，大厂面试官确实让人impress，问的问题一听就是自己都里里外外明白了，全在点子上，而且往往会对题目改动一些，这样靠记忆是过不了的。所以如果我们能预判他们的预判，提前就边写边解释清楚，这里为什么这么写，那里是为了简化才这样，就能省下时间来讨论更加重要的东西了。比如LRU写完了，还有时间，就可以自己提出来，这个cache还能怎么改进, data encryption? segregation by company id? 不一定要写出来能测试，但是能提出解决方法。


洋洋洒洒，唠唠叨叨。一派胡言，博君一笑。


都看到这儿了，请动动你发财的小手，送个大米吧。：-）


以后可能还会接着写写，欢迎收藏，回复，一键三连。哈哈哈。

bspcsquad 发表于 2024-12-6 13:53
这个题思想不难，白板编程难点在于要把面试所用语言的 linked list API 记清——毕竟做业务开发的都很少用 ...

. 软厂。

System Design面试时要求写code还是正常的，我面Uber时碰到过。当时design一个top K，应面试官要求，写了一段基本款用priority queue的code。

当年面大厂第一道就是LRU、菜鸟不懂LRU的高频…挂了 现在可以说闭着眼睛写了

有一个很帅的人 发表于 2024-12-06 12:32:12
哈哈。有可能。

如果有LC学到的东西，拿到实际运用，放到prod里面跑起来，我想，程序猿应该是很开心的。

我们service处理的请求量巨大 每个请求一个process就得跑完 有些config之类的东西隔一段时间去azure取没问题 但如果每个请求都这样去取直接bottleneck整个latency，为什么会这样呢？没错我们的service本身不在azure上😫这就是office陈年💩山

多写！爱看！已加米！已关注！已收藏！

还有一道今年的高频题Account Balance，最优解是leetcode 465。不过，Stripe, Pinterest, Remitly等公司都只追求较好的解（较少的交易次数，不要求最少的交易次数），用Greedy方法解决（排序后双指针，或者两个堆）。

这个题思想不难，白板编程难点在于要把面试所用语言的 linked list API 记清——毕竟做业务开发的都很少用链表，很难达到肌肉记忆。
但 LZ 举的例子怎么不明确到底是 coding 还是 design，想知道是哪个公司会这样考？难道是亚麻的 low-level design？

柑橘不错啊哈哈

有一个很帅的人 发表于 2024-12-06 11:22:32
软厂。

System Design面试时要求写code还是正常的，我面Uber时碰到过。当时design一个top K，应面试官要求，写了一段基本款用pr

你这一说我都怀疑是我们组的面试了 我们会问这题而且组里确实有一个一毛一样手写的cache带ttl和capacity control在service里运行

匿名用户 发表于 2024-12-6 14:58
你这一说我都怀疑是我们组的面试了 我们会问这题而且组里确实有一个一毛一样手写的cache带ttl和capacity c ...

哈哈。有可能。
. ----
如果有LC学到的东西，拿到实际运用，放到prod里面跑起来，我想，程序猿应该是很开心的。

不过，如果你是软厂的，不应该用Azure里面的Redis吗？毕竟把failover，metrics啥的都做好了。自己手写，这种功能都很难写得好啊。

写的挺好的，但是miss掉一些。如果是java这地方讨论的地方很多
- 这题可以展开讨论 hashmap vs treemap, 八股味来了。如果没有capacity限制的话，是应该考虑实际应用。
- 假设放到production environment报错，让你debug，会是什么问题？揭秘multithreading。你虽然是提了一下，但是这里深挖的东西更多，最近两次被问到这个。
- 可以用concurrenthashmap，或者自己写locking。两个相比哪个快，为什么，
- 如果不可以使用concurrenthashmap，也不可以使用synchronized/lock，怎么做？
- 其他勾UC八股问题