LLD Interview Question - Design LRU Cache

March 12, 2026

Problem Statement

Design and implement a Least Recently Used (LRU) cache data structure that supports get and put operations in O(1) time complexity. The cache should evict the least recently used item when it reaches its capacity limit.

Requirements

The cache should be able to store upto capacity number of key-value pairs.
The cache should be able to get the value of a key in O(1) time complexity.
The cache should be able to put a key-value pair in O(1) time complexity.
The cache should be able to evict the least recently used item when it reaches its capacity limit.

Solution

I would use a HashMap to store the key-value pairs for O(1) lookup, and a doubly linked list to maintain the usage order of keys.

The reason for using a doubly linked list is that when a key is accessed, I may need to remove its node from the middle of the list and move it to the front, and DLL allows that in O(1) if I already have the node reference.

The brute force approach would be to use a normal map for storage and a normal list for tracking order. That would work functionally, but on every get or put, I may need to search the list, remove a key from the middle, or update recency, which would make the operation O(n) in the worst case.

So to achieve O(1) get and put, I would use a combination of HashMap and doubly linked list.

Lets write the code for the LRU Cache.

First i will create a LRU Cache class.

class LRUCache:
  def __init__(self, capacity:int): 
    self.head = Node(-1, -1)
    self.tail = Node(-1, -1)
    self.head.next = self.tail
    self.tail.prev = self.head
    self.capacity = capacity
    self.map = {} # we store the key and the node in the map for O(1) lookup

Now i will create a Node class.

class Node:
  def __init__(self, key:int, value:int): 
    self.key = key 
    self.value = value 
    self.prev = None 
    self.next = None

the 2 operations are get and put.

In LRU every get operation would involve :

Check if key is there in the map,
If yes, then return the value and move the node to the front of the list. (indicating MRU)
If no, then return -1.

In LRU every put operation would involve :

Check if key is there in the map,
If yes, then update the value and move the node to the front of the list. (indicating MRU)
If no, then add the key-value pair to the map and the list, and if the cache is full, then evict the least recently used item from the list and the map.

So from the understanding of the operations, we would need functions to :

move a node to the front of the list.
to remove a node from the end of the list.

def insert(self, node:Node):
  self.map[node.key] = node 
  node.next = self.head.next 
  node.next.prev = node 
  self.head.next = node 
  node.prev = self.head

def remove(self, node:Node):
  del self.map[node.key]
  node.prev.next= node.next
  node.next.prev = node.prev

Now we can implement the get and put operations.

def get(self, key:int) -> int : 
  if key in self.map : 
    node = self.map[key]
    self.remove(node)
    self.insert(node)
    return node.value
  return -1

def put(self, key:int, value:int): 
  if key in self.map : 
    self.remove(self.map[key])
  if len(self.map) == self.capacity : 
    self.remove(self.tail.prev)
  self.insert(Node(key, value))

Now our LRU Cache is complete.

Follow up questions

Now introduce the concept of TTL to the cache.