LRU Cache Round: Which Follow-Ups Does Big Tech Add?

As of 2026-11-02, TrueInterview's bank holds 35 LRU and LFU cache questions reported at 17 big-tech companies, and 28 of them are object-oriented design while only 4 are coding (algorithm) problems. Our reading: the O(1) hash map plus doubly linked list is the entry ticket, and the follow-up your target company tends to add is the part worth rehearsing. Each rung of that ladder has a named, recent report, from LinkedIn's thread-safe follow-up in a phone screen to Anthropic's debug-an-existing-implementation onsite.

Disclosure: TrueInterview is an interview-preparation product and publishes this article. Facts about other products come from their public pages on the dates listed under Sources.

Is it a coding drill or an object-oriented design round?

Mostly a design round, and in both stages of the loop. Candidates reported these questions in onsites 24 times and in phone screens 18 times, since one question can sit in more than one round. Object-oriented design is the top subtype in both: 10 of the 15 phone-screen questions and 18 of the 22 onsite questions outside the algorithm format.

The reports are also current, with 30 of the 35 questions last reported in the 12 months before 2026-11-02. Final Round AI's guide calls LRU Cache (LeetCode 146) "one of the most frequently asked data structures problems in software engineering interviews at Google, Meta, Amazon, and Microsoft". In the bank, most are filed as object-oriented design rather than as algorithm problems. These are candidate-reported questions reconstructed for practice, not any company's official list.

Our take: stop optimising for the shortest LeetCode 146 submission. Write a cache class with a small public surface (get, put, capacity) and one private eviction method, because every follow-up in the next sections changes the eviction rule or the locking while leaving the interface alone. If adding a lock or a TTL forces you to rewrite get and put, the time goes to re-deriving pointer code instead of to the trade-off the follow-up is about.

What does the base solution need, and where do candidates slip?

The base is two structures and two invariants. Final Round AI's guide says both get and put must run in O(1) average time. The standard answer pairs a hash map from key to node with a doubly linked list ordered by recency, so lookup and reordering are both constant time. Using only one structure, the same guide says, yields "a correct but O(n) solution, which fails the time complexity requirement".

The same guide anchors the list with a dummy head and a dummy tail, which removes every null check at the ends. The guide names two bugs worth memorising: a node that omits its key leaves eviction unable to find the hash map entry to delete, and in insert-at-head the head.next.prev assignment must come before head.next, or the current first node is lost.

Our take: say the invariants out loud before you type. The map and the list hold the same set of keys, the node after the head is the most recent, the node before the tail is the next victim, and the size never exceeds capacity once put returns. Saying them out loud gives a senior interviewer signal beyond the pointer code, and the same sentences are also the checklist you will need when the round turns into debugging someone else's version.

Which follow-ups get added, and what does each one test?

Thread safety, LFU, expiry, weighted eviction and durability, each with a named report in the bank. The table lists the reported question for each rung, the latest dated report and how many candidate write-ups link to it. Link counts measure what candidates wrote up, not how often a company asks.

Thread safety has its own section below because the language shortcuts fail there, and debugging gets one because it changes how you practise. The two weighted rows are separate questions with separate write-ups, so do not add their counts together.

Expiry: decide when an entry dies and what clock says so

Wikipedia's article on replacement policies describes time-aware LRU (TLRU) as a variant for caches whose contents have a valid lifetime. In an interview the mechanics are simple: store an expiry time on each node and treat an expired entry as a miss on get. The interviewer's questions sit in two decisions. Does an expired entry that nobody reads still count against capacity? If it does, put should drop expired entries before it evicts a live one. Which clock do you read? Use a monotonic clock, and inject it so you can test expiry without sleeping.

Our take: lead with lazy expiry on read plus a sweep from the least recent end during put, then offer a min-heap ordered by expiry time if the interviewer cares about memory held by dead entries. For context, Redis's eviction documentation lists a volatile-ttl policy that evicts keys with "the shortest remaining TTL value", which is a useful contrast: expiry and capacity eviction are two separate rules that you will have to order.

LFU: the tie-break is the question

The O(1) LFU design keeps a map from key to node, a map from frequency to a doubly linked list of nodes at that frequency, and a pointer to the lowest frequency in use. A hit moves the node to the next frequency's list and advances the lowest-frequency pointer only if it emptied that list; a new key resets the pointer to one. The interviewer will push on ties: among keys with the lowest frequency, evict the least recently used one, which is why each frequency bucket is itself an LRU list.

Redis's eviction documentation offers both an allkeys-lru and an allkeys-lfu policy. Wikipedia's article notes that LRU in particular lets streaming data fill the cache and push out entries that will soon be used again, which it calls cache pollution. Our take: use that pair as your trade-off answer. LFU resists a one-off scan, but a key that was hot last week keeps its high count and never leaves, so mention frequency decay or a cap on counts before the interviewer has to ask.

Weighted eviction: capacity becomes a budget

The reports give only the titles, so this is our reading: one plausible interpretation of a weighted cache is a capacity budget measured by total weight rather than by entry count, and your first question to the interviewer should be whether weight sets size or eviction priority. Under the budget reading, a single put can evict several entries, from the least recent end, until the total fits. The decisions to state up front are what weight means (bytes, cost or a caller-supplied number), what happens when one item is heavier than the whole capacity (reject it rather than empty the cache), and how an update to an existing key changes the running total.

Our take: this is the follow-up where silent assumptions cost the most, because each of those three choices changes the code. Ask the interviewer to pick, write the choice as a comment at the top of the class, and keep the total-weight counter next to the size invariant you stated for the base.

Durability: ask why a cache needs to survive a restart

Anthropic's In-Memory Cache: Bug-Fix + Durability question is linked from 9 write-ups. Redis's eviction documentation explains that cache entries are copies of data stored persistently elsewhere, which is why evicting them is usually safe. Our take: open by asking why this cache must survive a restart, because the answer sets the design. The usual shape is an append-only log of puts and deletes replayed on startup, plus periodic snapshots so the log can be truncated. The two decisions an interviewer will push on are when you flush to disk (every write or in batches) and how recovery treats a half-written last record, where a length prefix and checksum let you discard it cleanly.

Can you use LinkedHashMap or OrderedDict?

Yes for the base, if you can explain what the shortcut hides, and only with a lock around it once thread safety enters. Final Round AI's guide describes the Java version as LinkedHashMap with accessOrder=true and an overridden removeEldestEntry, and the Python version as an OrderedDict that calls move_to_end on every hit. The same guide says interviewers at Amazon and Microsoft frequently follow up by asking how LinkedHashMap implements access order internally.

The thread-safety rung is where the shortcut stops being enough on its own. LRU Cache + Thread-Safe Follow-up is filed under 6 companies in the bank, including Oracle and Snapchat alongside the four whose write-ups link it. Java's documentation says plainly that LinkedHashMap is not synchronized and shows wrapping it with Collections.synchronizedMap. Java's documentation also says that in an access-ordered map, "merely querying the map with get is a structural modification."

That sentence is the senior-level answer. In an LRU cache every get reorders the list, so a read-write lock buys nothing: there are no pure reads. Start with one mutex around get and put; wrapping the access-ordered map with Collections.synchronizedMap gives you exactly that, and it is correct and easy to defend. Finer locking is where you need your own node-based version. Offer sharding, where each shard is its own LRU with its own lock, and say what it costs: eviction becomes least recent per shard rather than globally. Redis's eviction documentation says its own LRU algorithm is an approximation rather than an exact computation, which shows that production systems also give up exact recency to keep eviction cheap.

Python adds a trap of a different kind. Python's documentation says the functools cache decorator is threadsafe for use across threads but does not guarantee call-once behaviour, because locks are not held during the call. That applies to the decorator only: a cache class you write on OrderedDict has no locking of its own, and move_to_end plus eviction is a compound operation that needs your lock around get and put. Our take: if you open with LinkedHashMap or OrderedDict, have the node-based version ready to write when the interviewer asks for locking or internals, since both questions lead back to the doubly linked list.

Why should you practise debugging an existing cache?

Because debugging has named reports linked from candidates at several companies. Implement an LRU Cache (HashMap + Doubly Linked List) and Debug an Existing Implementation is linked from 14 write-ups by candidates at 6 companies and is filed under 8. Anthropic's version was last reported in an onsite in 2026-10, and its durability question pairs a bug-fix with persistence.

Separately, the format mix is moving away from pure object-oriented design. Object-oriented design took 70% of write-up links in 2025-Q4 and 45% in 2026-Q3. Multi-file repo questions rose from 30% to 37% and coding (algorithm) questions from 0% to 18% over the same quarters. Compare shares rather than raw totals, because the totals mostly reflect how many write-ups were collected each quarter. Even Apple's LRU Cache appears as a multi-file repo question in a phone screen last reported in 2026-10. These shares track format, not debugging: Anthropic's debug question above is filed as object-oriented design, so read the two signals separately.

Our take: both signals reward the same habit, reading code you did not write, so practise reading before you practise writing. Take an LRU implementation you did not write and hunt, under a timer, for the bugs that recur: the missing key on the node and the pointer order from the base section, a get that returns the value without moving the node, a put on an existing key that inserts a duplicate node, eviction that runs before checking whether the key already exists, a capacity check off by one, and an evicted node left in the map. Narrate each fix with the invariant it restores, because that is what separates a debugging round from a guessing game.

Which follow-up should you rehearse for your target company?

Thread safety, weighted eviction, expiry and debugging each trace to a different set of companies in the reports, so pick your target's rung before you practise. The table shows how many LRU and LFU questions are filed under each company, their format split, and the follow-up that company's reports point to. Counts are candidate reports, not how often the company asks.

The rehearse first column is our reading of the evidence above. Write-ups linking the thread-safe follow-up come from Apple, Microsoft, Amazon and LinkedIn candidates, while those linking LFU come from Microsoft, Salesforce, LinkedIn and Google candidates. Write-ups linking Weighted LRU Cache come from Amazon, Snapchat and Netflix candidates. Meta's reported expiry question is the timed cache in the table above, and Anthropic's reports centre on debugging and durability.

Worked example. Suppose your next round is a LinkedIn phone screen. LinkedIn's thread-safe follow-up is the latest dated report for that rung, so build the base with a key on every node, then add one lock and explain why get must hold it. LFU Cache is also filed under LinkedIn, so your second session switches eviction from recency to frequency in the same class. An Amazon candidate would swap the second session for weighted eviction, and an Anthropic candidate would spend both on reading and hardening an existing implementation.

What changes at senior and staff level?

Senior candidates do get this round, but they write up the follow-ups more than the plain version. Write-ups link these questions 68 times from candidates who reported a senior, staff-plus or manager level and 87 times from candidates who reported a junior, new-grad or intern level. Levels are self-reported on each write-up.

Plain LRU Cache is the most junior-leaning row, while thread safety, LFU and Netflix's weighted cache are even or senior-leaning. Weighted LRU Cache is the exception among follow-ups, with only 2 of its 8 links from senior-or-above candidates. By format, senior and junior links split 40 to 49 on object-oriented design, 7 to 5 on coding and 21 to 33 on multi-file repo.

Our take: at senior level, expect the interviewer to move past the base quickly and spend the time on locking, eviction-policy trade-offs and reading or hardening existing code. Lead with a design you can extend and narrate the choices: lock granularity, what expiry does to capacity, what weight means and how recovery handles a torn write.

Down-leveling note (our view): a clean base solution earns little level signal for a senior candidate. The signal sits in how you handle the follow-up, so a candidate who finishes the base late and never reaches it is the one most at risk of a lower-level offer.

What do ML and AI candidates get on top of the base?

A KV-cache variant, usually inside a debugging task, alongside the classic question rather than in place of it. Plain LRU Cache is linked from 3 write-ups by machine-learning, AI, research or data-science candidates. Debug a Transformer Implementation and Implement a KV Cache for Decoding is linked from 4 write-ups by machine-learning, AI, research or data-science candidates and none by software-engineer candidates. OpenAI's Debug a GPT-Style Transformer with KV-Cache Generation was last reported as a multi-file repo question in a phone screen in 2026-09.

That OpenAI question is linked from 4 write-ups by senior-or-above candidates. Across the whole set, ML and AI candidates' links are 50% multi-file repo and 40% coding (algorithm), against 34% and 6% for software-engineer candidates, though the ML side rests on only 10 links.

Our take: if you are interviewing for an ML role, keep the base LRU and add the KV-cache variant as your follow-up rung instead of the weighted or durability rungs; the ML side has few links, so treat the split as a hint, not a rule. Prepare to explain that the cache stores keys and values for past tokens so each decoding step computes attention only for the new token, then practise finding the bugs that break it: positions that do not advance with the cache, concatenation along the wrong axis and a causal mask that ignores the cached length.

How we counted

Counts come from TrueInterview's question bank as of 2026-11-02. A write-up link means a candidate's write-up points to that question, so link counts are not write-up counts, and levels and roles are what candidates reported. A question can be reported in more than one round, which is why the round totals exceed the question total. Quarterly figures are shares of links in each quarter, because collection volume changes between quarters.

FAQ

Is the LRU cache question asked in the phone screen or the onsite?

Both, and the follow-ups appear in both stages. The dated examples in the ladder table include phone screens at LinkedIn, Amazon, Netflix, Meta and ByteDance, and onsites at Oracle and Anthropic. In either round, object-oriented design is the dominant framing. Plan for a phone screen to cover the base plus one follow-up, and treat an onsite as a chance to be pushed further down the ladder, into locking, durability or debugging, with more time on trade-offs.

How does LFU differ from LRU in an interview?

LRU evicts the least recently used entry; LFU evicts the least frequently used one, which needs frequency buckets and a pointer to the lowest frequency to stay O(1). Wikipedia's cache replacement article says each replacement strategy is "a compromise between hit rate and latency." In the interview, the deciding detail is the tie-break among keys with equal frequency, so build each frequency bucket as its own LRU list and say so before the interviewer asks.

How do you make an LRU cache thread-safe?

Put one mutex around get and put first, because in an LRU every get changes the recency order and therefore writes. A read-write lock does not help for that reason. If the interviewer asks for more throughput, shard the cache by key hash so each shard has its own lock and its own list, and state the cost: eviction becomes per-shard rather than global. The Java and Python details are in the shortcuts section above.

Do senior engineers still get the LRU cache question?

Yes, though the senior write-ups lean toward the follow-ups rather than the plain version, as the level table above shows. For a senior candidate, treat the base as a warm-up and finish it fast enough to leave most of the round for the follow-up. In our view, the evaluation centres on the follow-up: whether you state invariants, choose a lock scope deliberately and explain what expiry or weight does to capacity, rather than whether the pointers are right.

What are the most common bugs in LRU cache implementations?

The two classic ones are a node that does not store its key, which breaks eviction, and inserting at the head in the wrong pointer order, which loses the current first node. Beyond those, check that get moves the node, that put on an existing key updates in place rather than adding a second node, and that eviction removes the map entry too. The debugging section above lists the full set to rehearse.

Your practice plan

1. In week one, write the LRU Cache from scratch with sentinel nodes and a key on every node, and repeat it on separate days until you can finish it with time to spare for a follow-up.
2. Still in week one, extend the same class with a single lock and practise the explanation of why get needs it, using the thread-safe follow-up.
3. In week two, add expiry with the TTL and LFU follow-ups question, stating your choices on lazy expiry, capacity and the clock before you code.
4. Next, switch eviction to frequency with the LFU Cache, and say how you break ties and age old counts.
5. Then change capacity to a weight budget with the Weighted LRU Cache, deciding up front what happens to an item heavier than the whole cache.
6. In week three, rehearse reading code with the debug-an-existing-implementation question and the In-Memory Cache: Bug-Fix + Durability question, narrating each bug against an invariant.
7. Before the interview, find your target company's row in the company table and redo that follow-up out loud, start to finish, as a timed mock; ML candidates should add the KV-cache debugging question to that rehearsal.

Sources

• TrueInterview question bank — LRU and LFU cache at big-tech companies — counted 2026-11-02
• LRU Cache Interview Question: Python and Java Solutions — checked 2026-11-02
• Cache replacement policies - Wikipedia — checked 2026-11-02
• Key eviction | Docs — checked 2026-11-02
• LinkedHashMap (Java SE 21 & JDK 21) — checked 2026-11-02
• functools — Higher-order functions and operations on callable objects — Python 3.15.2 documentation — checked 2026-11-02

Last reviewed: 2026-11-02.