Free AI LeetCode Communication Coach — LRU Cache

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. 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. 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. 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. 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. 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

1. 1. Restate

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

2. 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. 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. 4. Time and space

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

5. 5. Edge cases

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

Common mistakes when explaining LRU Cache

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