LRU Cache

Problem Highlights

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What is an LRU?
    • A Least Recently Used (LRU) Cache organizes items in order of use, allowing you to quickly identify which item hasn't been used for the longest amount of time. An LRU cache is built by combining two data structures: a doubly linked list and a hash map.You can read more here.
  • What operations do we need to implement?
    • You need to implement 1) Get the key / Check if the key exists 2) Put the key and 3) Delete the first added key

Run through a set of example cases:

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
[null, null, null, 1, null, -1, null, -1, 3, 4]

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked Lists, the top three things we want to consider are:

  • If we were able to take multiple passes of the linked list, would that help solve the problem?
    • Knowing the length of the list is important since we want to rotate only k % len(list) times. Note: This computation may not be necessary for some approaches.
  • Would using a dummy head as a starting point help simplify our code and handle edge cases?
    • Since we are manipulating the order of the list, a dummy head may look like a good strategy, and it may work. However, we don’t necessarily need one to solve this problem.
  • If we used two pointers to iterate through the list at different speeds, would that help us solve this problem?
    • A slow and fast pointer may not help the problem.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea: Solve with a hashmap that keeps track of the keys and its values in the double linked list.

In get method we have to return -1 if key is not in our dict. If it does, then we have to move our key, value pair to the end of our dict. Now it is our most recent key, value pair.

In put method if key is not in our dict and we would go above capacity, then we remove first item in our dict by .popitem(last=False) method.

If we only update value of the existed key, then we have to pop the value from the dict and then assign the value, to put the key, value pair at the end of our dict (so we make the key, value pair most recent one).

⚠️ Common Mistakes

  • If we have the iterator for a particular element then we can access that element in O(1) in any STL. That lets us find an element in our cache's linked list in O(1) time, instead of O(n).

4: I-mplement

Implement the code to solve the algorithm.

class DLinkedNode(): 
    def __init__(self):
        self.key = 0
        self.value = 0
        self.prev = None = None
class LRUCache():
    def _add_node(self, node):
        Always add the new node right after head.
        node.prev = self.head = = node = node

    def _remove_node(self, node):
        Remove an existing node from the linked list.
        prev = node.prev
        new = = new
        new.prev = prev

    def _move_to_head(self, node):
        Move certain node in between to the head.

    def _pop_tail(self):
        Pop the current tail.
        res = self.tail.prev
        return res

    def __init__(self, capacity):
        :type capacity: int
        self.cache = {}
        self.size = 0
        self.capacity = capacity
        self.head, self.tail = DLinkedNode(), DLinkedNode() = self.tail
        self.tail.prev = self.head

    def get(self, key):
        :type key: int
        :rtype: int
        node = self.cache.get(key, None)
        if not node:
            return -1

        # move the accessed node to the head;

        return node.value

    def put(self, key, value):
        :type key: int
        :type value: int
        :rtype: void
        node = self.cache.get(key)

        if not node: 
            newNode = DLinkedNode()
            newNode.key = key
            newNode.value = value

            self.cache[key] = newNode

            self.size += 1

            if self.size > self.capacity:
                # pop the tail
                tail = self._pop_tail()
                del self.cache[tail.key]
                self.size -= 1
            # update the value.
            node.value = value
public class LRUCache {

  class DLinkedNode {
    int key;
    int value;
    DLinkedNode prev;
    DLinkedNode next;

  private void addNode(DLinkedNode node) {
     * Always add the new node right after head.
    node.prev = head; =; = node; = node;

  private void removeNode(DLinkedNode node){
     * Remove an existing node from the linked list.
    DLinkedNode prev = node.prev;
    DLinkedNode next =; = next;
    next.prev = prev;

  private void moveToHead(DLinkedNode node){
     * Move certain node in between to the head.

  private DLinkedNode popTail() {
     * Pop the current tail.
    DLinkedNode res = tail.prev;
    return res;

  private Map<Integer, DLinkedNode> cache = new HashMap<>();
  private int size;
  private int capacity;
  private DLinkedNode head, tail;

  public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    // head.prev = null;

    tail = new DLinkedNode();
    // = null; = tail;
    tail.prev = head;

  public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // move the accessed node to the head;

    return node.value;

  public void put(int key, int value) {
    DLinkedNode node = cache.get(key);

    if(node == null) {
      DLinkedNode newNode = new DLinkedNode();
      newNode.key = key;
      newNode.value = value;

      cache.put(key, newNode);


      if(size > capacity) {
        // pop the tail
        DLinkedNode tail = popTail();
    } else {
      // update the value.
      node.value = value;

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with an input to check for the expected output
  • Catch possible edge cases and off-by-one errors

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

  • Time Complexity: O(1) both for put and get.
  • Space Complexity: O(capacity) since the space is used only for a hashmap and double linked list with at most capacity + 1 elements.
Fork me on GitHub