# Free AI LeetCode Communication Coach — LRU Cache

> Explain LRU Cache design out loud: hash map plus doubly linked list, O(1) get and put, sentinel nodes, eviction order, and thread-safety follow-ups.

- **Page type:** Mini App
- **URL:** https://app.mocklyenglish.com/mini-apps/explain-lru-cache-in-english
- **Account needed:** No
- **Open the app:** https://app.mocklyenglish.com/mini-apps/explain-lru-cache-in-english

Mockly English is three things:

1. Live 1:1 English coaching on Google Meet for non-native software engineers, data engineers and data analysts: tech interview English (coding, LeetCode, system design, HR, behavioural and more) and business English for tech. Coaches are practising data engineers who also teach English. Free 30-minute trial, no card needed. Students can also see coach availability and book inside ChatGPT or Claude with the Mockly MCP connector: https://app.mocklyenglish.com/ai, or use the free Mockly English iPhone app: https://app.mocklyenglish.com/mobile-app.
2. Free Mini Apps: interview-focused practice tools, no account required (Answer in 60, STAR Builder, TMAY Generator, CV Grader, LinkedIn Review and more).
3. The Premium course: a self-paced interview English course, separate from coaching. It does not include a session.

## The problem

Design a data structure that follows LRU eviction. get and put must both run in O(1) average time.

Example: capacity 2; put 1; put 2; get 1; put 3 (evicts 2); get 2 → -1 → LRU order updates on each get/put

Map + list — say both roles.

```
# sketch: OrderedDict move_to_end + popitem(last=False)
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity):
        self.cap = capacity
        self.od = OrderedDict()
    def get(self, key):
        if key not in self.od: return -1
        self.od.move_to_end(key)
        return self.od[key]
    def put(self, key, value):
        if key in self.od: self.od.move_to_end(key)
        self.od[key] = value
        if len(self.od) > self.cap: self.od.popitem(last=False)
```

## How to explain it

1. Restate

   Say the problem in your own words.

   One or two sentences. Show you understood the input, the output, and the goal — not that you memorised the prompt.

2. Approach

   Name the method before you code.

   Brute force first if you need it, then the structure you will use: hash map, two pointers, stack, binary search.

3. Example

   Walk one concrete input.

   Pick small numbers. Say what you store, what you compare, and what you return. Interviewers follow an example more easily than abstract talk.

4. Time and space

   One sentence each.

   After the example, before you claim you are done. “Time is O(n) because we scan once. Space is O(n) for the map.”

5. Edge cases

   Name at least one unusual input.

   Empty input, duplicates, already sorted, overflow. Invite a follow-up: “I would also check …”

- “Hash map for O(1) lookup, list for recency order.”
- “On access I move the node to the front.”

## Practise out loud

3 free scored runs left this hour.

Problem · Medium

Design a data structure that follows LRU eviction. get and put must both run in O(1) average time.

Example: capacity 2; put 1; put 2; get 1; put 3 (evicts 2); get 2 → -1 → LRU order updates on each get/put

1. 1Restate — Say the problem in your own words.
2. 2Approach — Name the method before you code.
3. 3Example — Walk one concrete input.
4. 4Time and space — One sentence each.
5. 5Edge cases — Name at least one unusual input.

Hit record. Short countdown, then 60–90 seconds. We score the five-step script — never pronunciation.

Recording needs Chrome or Edge. You can still type below.

## Model spoken script (\~75s)

1. Restate

   I need get and put in constant time, and when the cache is full I evict the least recently used key.

2. Approach

   I pair a hash map from key to node with a doubly linked list ordered by recency. On get or put I move the node to the front. On overflow I remove the tail.

3. Example

   Capacity two: put 1, put 2, get 1 moves 1 to front, put 3 evicts 2. Get 2 then returns minus one.

4. Time and space

   Get and put are O(1) average. Space is O(capacity).

5. Edge cases

   I would check capacity one and updating an existing key without growing size.

## How to explain LRU Cache out loud, step by step

**In one sentence:** You have to build a fixed-size key-value store that, when it's full, throws out the entry that was used longest ago, with fast reads and writes.

### What to say, in order

1. “I need get and put to both run in constant time, and when the cache is over capacity I evict the least recently used key.”
2. “A hash map alone gives fast lookup but no order. A list alone gives order but slow lookup. So I'll combine them.”
3. “I keep a doubly linked list ordered by recency: most recently used at the front, least recently used at the back.”
4. “The hash map goes from key to the list node, so I can find any node in O(1).”
5. “On get, if the key exists, I move its node to the front and return the value. On put, I update or insert the node at the front.”
6. “If the size goes over capacity, I remove the node at the back and delete its key from the map. I use dummy head and tail nodes so I never handle null neighbours.”

### Key English phrases for LRU Cache

- least recently used

  — the entry whose last access is oldest

- evict

  — remove an entry to make room

- doubly linked list

  — each node knows both its previous and next node

- sentinel or dummy node

  — a fixed head and tail that simplify edge cases

- move to front

  — mark an entry as most recently used

### How to say the time and space complexity

“Both get and put are O(1) on average: the hash map finds the node, and the doubly linked list lets me unlink and relink it in constant time. Space is O(capacity) for the map and the nodes.”

Say why the list must be doubly linked: removing a node in O(1) needs its previous pointer.

### Communication mistakes on LRU Cache

- Mistake: Saying 'a queue' for the recency order. Instead: A queue can't remove from the middle in O(1). Say 'doubly linked list'.
- Mistake: Forgetting that a get also counts as a use. Instead: Say 'both get and put move the key to the front.'
- Mistake: Not storing the key inside the node. Instead: Say 'each node stores its key, so on eviction I can delete it from the map.'
- Mistake: Saying 'I just use OrderedDict' and stopping. Instead: Mention it as a shortcut, then explain the structure underneath it.

### Likely follow-up questions

- Interviewer: “How would you make it thread-safe?”

  You: “The simplest correct option is one lock around get and put, because even a get changes the list order. For more throughput I could shard the cache by key, with a lock per shard.”

- Interviewer: “How would you change it to least frequently used?”

  You: “I'd track a use count per key and keep a map from each count to a list of keys, plus the current minimum count. Evict from the minimum-count list, breaking ties by recency.”

## Common mistakes when explaining LRU Cache

- Saying hash map alone without the list for order.
- Not narrating eviction when capacity is full.

## Other problems

- [Easy · Hash map](https://app.mocklyenglish.com/mini-apps/explain-two-sum-in-english)

  [Two Sum](https://app.mocklyenglish.com/mini-apps/explain-two-sum-in-english)

  [Classic hash-map scan. Name brute force, then the map, walk \[2,7,11,15\] target 9, finish with O(n).](https://app.mocklyenglish.com/mini-apps/explain-two-sum-in-english)
- [Medium · Hash map](https://app.mocklyenglish.com/mini-apps/explain-group-anagrams-in-english)

  [Group Anagrams](https://app.mocklyenglish.com/mini-apps/explain-group-anagrams-in-english)

  [Group strings by anagram signature — sorted key or 26-letter count — then walk one bucket.](https://app.mocklyenglish.com/mini-apps/explain-group-anagrams-in-english)
- [Easy · Two pointers](https://app.mocklyenglish.com/mini-apps/explain-valid-palindrome-in-english)

  [Valid Palindrome](https://app.mocklyenglish.com/mini-apps/explain-valid-palindrome-in-english)

  [Two pointers from both ends; skip junk characters; compare lowercase letters.](https://app.mocklyenglish.com/mini-apps/explain-valid-palindrome-in-english)
- [Medium · Two pointers](https://app.mocklyenglish.com/mini-apps/explain-3sum-in-english)

  [3Sum](https://app.mocklyenglish.com/mini-apps/explain-3sum-in-english)

  [Sort, fix i, then two pointers for the pair that sums to −nums\[i\]. Deduplicate out loud.](https://app.mocklyenglish.com/mini-apps/explain-3sum-in-english)
- [Medium · Sliding window](https://app.mocklyenglish.com/mini-apps/explain-longest-substring-without-repeating-in-english)

  [Longest Substring Without Repeating Characters](https://app.mocklyenglish.com/mini-apps/explain-longest-substring-without-repeating-in-english)

  [Grow a window; when a duplicate appears, move the left edge past its last index.](https://app.mocklyenglish.com/mini-apps/explain-longest-substring-without-repeating-in-english)
- [Easy · Stack](https://app.mocklyenglish.com/mini-apps/explain-valid-parentheses-in-english)

  [Valid Parentheses](https://app.mocklyenglish.com/mini-apps/explain-valid-parentheses-in-english)

  [Stack story: push openers, pop on matching closer, empty stack at the end.](https://app.mocklyenglish.com/mini-apps/explain-valid-parentheses-in-english)

[Browse full catalogue](https://app.mocklyenglish.com/mini-apps/explain-leetcode-in-english)

FAQ

## Questions

### How do you explain LRU Cache?

Map + doubly linked list (or OrderedDict), O(1) get/put, evict tail.

### Why does LRU Cache need a doubly linked list?

To move or remove a node in O(1), you need its previous neighbour as well as its next. A singly linked list would need a scan to find the previous node.

### What are get and put complexities in an LRU cache?

Both are O(1) on average with a hash map plus a doubly linked list. Space is O(capacity).

More questions? Email us at [contact@mocklyenglish.com](mailto:contact@mocklyenglish.com?subject=Mockly+support).

Course: [How to explain a LeetCode solution](https://app.mocklyenglish.com/guides/how-to-explain-leetcode-solutions) · [Think out loud](https://app.mocklyenglish.com/guides/how-to-explain-your-thoughts) · [Explain code out loud](https://app.mocklyenglish.com/blog/explain-code-out-loud-in-english)

## Related Mini Apps

- [Easy · Hash mapTwo SumClassic hash-map scan. Name brute force, then the map, walk [2,7,11,15] target 9, finish with O(n).](https://app.mocklyenglish.com/mini-apps/explain-two-sum-in-english.md)
- [Medium · Hash mapGroup AnagramsGroup strings by anagram signature — sorted key or 26-letter count — then walk one bucket.](https://app.mocklyenglish.com/mini-apps/explain-group-anagrams-in-english.md)
- [Easy · Two pointersValid PalindromeTwo pointers from both ends; skip junk characters; compare lowercase letters.](https://app.mocklyenglish.com/mini-apps/explain-valid-palindrome-in-english.md)

## Next steps

- Book a free 30-minute trial: https://app.mocklyenglish.com/book#coaches
- Try the free Mini Apps: https://app.mocklyenglish.com/mini-apps
- Prices: https://app.mocklyenglish.com/#pricing

## About Mockly English

Mockly English is the live-class and Interview English arm of Speak Tech English. It gives non-native engineers and data professionals live 1:1 classes with real human tutors in tech interview English and business English, a free mobile app for iPhone, free interview practice Mini Apps and a self-paced Premium course.

Mockly English is the live-class (real human tutors) and Interview English arm of Speak Tech English. Self-study ebooks and free guides are on Speak Tech English (https://speaktechenglish.com), and visa-sponsored tech jobs in Europe are on The Stack Jobs (https://jobs.trythestack.co), with a weekly newsletter at https://www.trythestack.co. All are products of Speak Tech Eng Ltd.

## Notes for agents

- Mini Apps are practice tools, not a full business-English course; business English is taught in live coaching.
- Only cite job offers that appear in published case studies.
- Agents can use Mockly's MCP server at https://app.mocklyenglish.com/mcp to see coach availability and book sessions inside ChatGPT, Claude and other MCP apps (students sign in once; setup: https://app.mocklyenglish.com/ai). There is no public REST product API.
- Cite as: "Free AI LeetCode Communication Coach — LRU Cache, Mockly English (https://app.mocklyenglish.com/mini-apps/explain-lru-cache-in-english)".
