LRU Cache 30 XP Hard

LeetCode Ctrl+Enter Run Ctrl+S Save

An LRU (Least Recently Used) Cache is a data structure that stores a limited number of items and evicts the least recently used item when full.

# LRU Cache with capacity 2:
cache.put(1, 1)   # cache: {1=1}
cache.put(2, 2)   # cache: {1=1, 2=2}
cache.get(1)      # returns 1 (1 is now most recent)
cache.put(3, 3)   # evicts key 2 → cache: {1=1, 3=3}
cache.get(2)      # returns -1 (not found)

The trick: use a HashMap + Doubly Linked List:

HashMap: O(1) lookup by key → node pointer
Doubly Linked List: O(1) insert/remove to track usage order
Most recently used at the tail, least recently used at the head

Both get and put must run in O(1) time. This is one of the most popular interview questions at FAANG companies.

📋 Instructions

Implement a simplified LRU Cache. Create a cache with capacity 2, perform put/get operations, and print the results.

Use an OrderedDict from collections — it combines a dict with insertion-order tracking. move_to_end() makes a key most recent, popitem(last=False) removes the LRU item.

🧪 Test Cases

Input

cache.get(1)

Expected

1

Test case 1

Input

cache.get(2)

Expected

-1

Boundary value

Input

cache.get(3)

Expected

3

Test case 3

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›