LRU Cache DSA Solution - Study Chapter | QuizMaker

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 16: Trie & Advanced Data Structures

Learning Outcome

After this lesson, you should be able to combine direct lookup with a recency order structure.

Problem Statement

Design an LRUCache with get(key) and put(key,value). When capacity is exceeded, remove the least recently used key.

Brute Force Approach

Store pairs in an array and scan to find keys and update recency. This makes operations O(n).

Optimized Approach

Use a hash map for O(1) key lookup and a doubly linked list or ordered map to move touched keys to most recent position.

Exact Pseudocode

get(key):
  if key is missing:
    return -1
  move key to most recent position
  return value

put(key, value):
  if key exists:
    update value and move key to most recent
  else:
    add key as most recent
  if size is greater than capacity:
    remove least recent key

Reference Code

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        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)

class LRUCache {
    int capacity;
    list<pair<int, int>> items;
    unordered_map<int, list<pair<int, int>>::iterator> position;

public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        if (!position.count(key)) return -1;
        items.splice(items.begin(), items, position[key]);
        return position[key]->second;
    }

    void put(int key, int value) {
        if (position.count(key)) {
            items.splice(items.begin(), items, position[key]);
            position[key]->second = value;
            return;
        }

        items.push_front({key, value});
        position[key] = items.begin();

        if (items.size() > capacity) {
            position.erase(items.back().first);
            items.pop_back();
        }
    }
};

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

Sample Dry Run

Complexity

Edge Cases

• Updating an existing key must refresh recency.
• get on a missing key should return -1 and not change the cache.
• Evict only after adding or updating causes size to exceed capacity.

Interview Checklist

• Use a map from key to node or iterator.
• Move every accessed key to most recent position.
• Evict from the least recent end, not the most recent end.

FAQs

The map finds a key quickly, while the list records which key is least or most recently used.

Yes. Updating or inserting a key makes it most recent in the standard LRU design.

Hash map plus recency list.

Tags

• dsa
• trie-advanced-ds
• hash map plus recency list