# The Forgetful Machine

> It remembers everything, until it does not.

Canonical URL: <https://datadriven.io/problems/the_forgetful_machine>

Domain: Python · Difficulty: medium · Seniority: L5

## Problem

Implement LRUCache(capacity) with get(key) returning the value or -1 if missing, and put(key, value) that inserts/updates and evicts the least-recently-used entry when capacity is exceeded. Also implement LRUCache_driver(capacity, ops) which runs a sequence of ops (each ['get', k] or ['put', k, v]) against an LRUCache(capacity) and returns the list of get() return values, in order.

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **LRU cache implementation**, a staple system design problem that also appears as a coding challenge. It probes understanding of combining hash maps with ordered data structures for O(1) operations.

> **Trick to Solving**
>
> Python's `OrderedDict` provides `move_to_end` and `popitem(last=False)` in O(1), making it the ideal backing store for an LRU cache.

---

### Break down the requirements

#### Step 1: get: return value and refresh recency

Move the accessed key to the end of the order. Return -1 if absent.

#### Step 2: put: insert or update and refresh recency

Move existing keys to the end. For new keys at capacity, evict the least recent (first item).

---

### The solution

**OrderedDict-backed LRU cache**

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

> **Time and Space Complexity**
>
> **Time:** O(1) for both `get` and `put`.
> 
> **Space:** O(capacity) for the stored entries.

> **Interviewers Watch For**
>
> Whether you can also implement this with a raw dict + doubly-linked list. The `OrderedDict` solution is clean, but the manual approach proves deeper understanding.

> **Common Pitfall**
>
> Not calling `move_to_end` on `put` when the key already exists. This means a key update does not refresh its recency, leading to premature eviction.

---

## Common follow-up questions

- Implement this with a dict and doubly-linked list. _(Tests building sentinel nodes, remove/insert operations, and maintaining the invariant.)_
- What is the difference between LRU, LFU, and FIFO caches? _(Tests knowledge of eviction policies and their tradeoffs.)_
- How would you add TTL (time-to-live) expiration? _(Tests storing timestamps and checking expiry on access.)_
- How would you make this thread-safe? _(Tests lock strategies and the performance implications.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_forgetful_machine)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.