2
\$\begingroup\$

I'm posting my Java code for LeetCode's LRU Cache. If you have time and would like to review, please do so. Thank you!

Problem

  • Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

  • get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

  • put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

  • The cache is initialized with a positive capacity.

Follow up:

  • Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);  
cache.put(2, 2);  
cache.get(1);       // returns 1  
cache.put(3, 3);    // evicts key 2  
cache.get(2);       // returns -1 (not found)  
cache.put(4, 4);    // evicts key 1  
cache.get(1);       // returns -1 (not found)  
cache.get(3);       // returns 3  
cache.get(4);       // returns 4

Accepted Java

public class LRUCache {
    private final Node head = new Node(0, 0);
    private final Node tail = new Node(0, 0);
    private final Map<Integer, Node> cache;
    private final int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap(capacity);
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        int value = -1;

        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            append(node);
            value = node.value;
        }

        return value;
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            Node node = cache.get(key);
            remove(node);
            node.value = value;
            append(node);

        } else {
            if (cache.size() == capacity) {
                cache.remove(tail.prev.key);
                remove(tail.prev);
            }

            Node node = new Node(key, value);
            append(node);
            cache.put(key, node);
        }
    }

    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void append(Node node) {
        Node headNext = head.next;
        head.next = node;
        headNext.prev = node;
        node.prev = head;
        node.next = headNext;
    }

    private class Node {
        Node prev, next;
        int key, value;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
}

LeetCode's Solution (Not for review)

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.next = head.next;

    head.next.prev = node;
    head.next = node;
  }

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

    prev.next = next;
    next.prev = prev;
  }

  private void moveToHead(DLinkedNode node){
    /**
     * Move certain node in between to the head.
     */
    removeNode(node);
    addNode(node);
  }

  private DLinkedNode popTail() {
    /**
     * Pop the current tail.
     */
    DLinkedNode res = tail.prev;
    removeNode(res);
    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();
    // tail.next = null;

    head.next = 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;
    moveToHead(node);

    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);
      addNode(newNode);

      ++size;

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

Reference

On LeetCode, there is a class usually named Solution with one or more public functions which we are not allowed to rename.

\$\endgroup\$
1
\$\begingroup\$

I have some suggestions for you, good job on the code!

Always add the empty diamond operator, even if defined in the left-hand side

If you don’t add the diamond, Java will use the old raw types instead of the generic types; those are only kept for compatibility.

Here is a good explanation with more details: https://stackoverflow.com/a/4167148/12511456

Before

cache = new HashMap(capacity);

After

cache = new HashMap<>(capacity);

Check if the value is present in a Map

Since you are using both java.util.Map#containsKey and java.util.Map#get, you can save some computation by using the get only and check if the value is null.

But, keep in mind this technique won’t work if you allow the map to have a null key :).

Before

if (cache.containsKey(key)) {
   Node node = cache.get(key);
   //[...]
}

After

Node node = cache.get(key);
if (node != null) {
   //[...]
}

Return the value as soon you have it, instead of storing it in a variable

I must admit that this method is not a favorite of every programmer, and can be hated, since you will have to use multiple return in the same block of code.

In my opinion, adding multiple returns shorten the code, reduce the arrow code, make shorter stack traces (by leaving the method faster, you get fewer lines) and block invalid states before they reach your code (guard clauses).

Examples:

Before

public int get(int key) {
   int value = -1;

   Node node = cache.get(key);
   if (node != null) {
      remove(node);
      append(node);
      value = node.value;
   }

   return value;
}

After

public int get(int key) {
   Node node = cache.get(key);

   if (node == null) {
      return -1;
   }

   remove(node);
   append(node);

   return node.value;
}

Extract some of the logic to methods.

To reduce the size of your methods, you can extract the logic blocks in methods.

Before

public void put(int key, int value) {
   Node currentNode = cache.get(key);

   if (currentNode != null) {
      remove(currentNode);
      currentNode.value = value;
      append(currentNode);
   } else {
      if (cache.size() == capacity) {
         cache.remove(tail.prev.key);
         remove(tail.prev);
      }

      Node node = new Node(key, value);
      append(node);
      cache.put(key, node);
   }
}

After

public void put(int key, int value) {
   Node currentNode = cache.get(key);

   if (currentNode != null) {
      updateNodeValue(value, currentNode);
   } else {
      createNewNode(key, value);
   }
}

private void createNewNode(int key, int value) {
   if (cache.size() == capacity) {
      cache.remove(tail.prev.key);
      remove(tail.prev);
   }

   Node node = new Node(key, value);
   append(node);
   cache.put(key, node);
}

private void updateNodeValue(int value, Node currentNode) {
   remove(currentNode);
   currentNode.value = value;
   append(currentNode);
}

Refactored code

public class LRUCache {
   private final Node head = new Node(0, 0);
   private final Node tail = new Node(0, 0);
   private final Map<Integer, Node> cache;
   private final int capacity;

   public LRUCache(int capacity) {
      this.capacity = capacity;
      cache = new HashMap<>(capacity);
      head.next = tail;
      tail.prev = head;
   }

   public int get(int key) {
      Node node = cache.get(key);

      if (node == null) {
         return -1;
      }

      remove(node);
      append(node);

      return node.value;
   }

   public void put(int key, int value) {
      Node currentNode = cache.get(key);

      if (currentNode != null) {
         updateNodeValue(value, currentNode);
      } else {
         createNewNode(key, value);
      }
   }

   private void createNewNode(int key, int value) {
      if (cache.size() == capacity) {
         cache.remove(tail.prev.key);
         remove(tail.prev);
      }

      Node node = new Node(key, value);
      append(node);
      cache.put(key, node);
   }

   private void updateNodeValue(int value, Node currentNode) {
      remove(currentNode);
      currentNode.value = value;
      append(currentNode);
   }

   private void remove(Node node) {
      node.prev.next = node.next;
      node.next.prev = node.prev;
   }

   private void append(Node node) {
      Node headNext = head.next;
      head.next = node;
      headNext.prev = node;
      node.prev = head;
      node.next = headNext;
   }

   private class Node {
      Node prev, next;
      int key, value;

      Node(int key, int value) {
         this.key = key;
         this.value = value;
      }
   }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.