# The Eviction Policy

> Fixed capacity. Oldest unused entry gets evicted.

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

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Implement LRUCache(capacity) with get(key) (returns value or -1) and put(key, value). Evict least recently used when capacity is exceeded. Both operations O(1). Test harness passes ['LRUCache', capacity] then op sequences; expects list of return values (None for constructor/put, value or -1 for get).

## Worked solution and explanation

### Why this problem exists in real interviews

This tests **LRU cache implementation**, one of the most frequently asked design problems. It probes understanding of the `OrderedDict` approach or the combination of a hash map with a doubly-linked list to achieve O(1) get and put.

> **Trick to Solving**
>
> Use `collections.OrderedDict`. On every `get` or `put`, move the key to the end (most recent). On capacity overflow, pop the first item (least recent). This gives O(1) for all operations.

---

### Break down the requirements

#### Step 1: get returns value and marks as recently used

If the key exists, move it to the end of the order and return its value. Otherwise return -1.

#### Step 2: put inserts or updates and marks as recently used

If the key exists, update and move to end. If new and at capacity, evict the least recently used (first item).

---

### The solution

**OrderedDict-based LRU cache**

```python
from collections import OrderedDict
class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()
    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]
    def put(self, key: int, value: int):
        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`. `OrderedDict.move_to_end` and `popitem` are O(1).
> 
> **Space:** O(capacity) for the cache entries.

> **Interviewers Watch For**
>
> Whether you can also implement this without `OrderedDict` using a hash map and doubly-linked list. The manual implementation proves deeper understanding.

> **Common Pitfall**
>
> Forgetting to move existing keys to the end on `put` (not just `get`). Updating a value without refreshing recency causes incorrect eviction.

---

## Common follow-up questions

- How would you implement this without OrderedDict? _(Tests building a doubly-linked list with head/tail sentinels and a hash map.)_
- What is the difference between LRU and LFU? _(Tests eviction strategy knowledge: recency vs frequency.)_
- How would you make this thread-safe? _(Tests lock granularity and concurrent data structure design.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_eviction_policy)
- [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.