Design LRU cache interview questions

Question

Code reviewers, I request you review the code and suggest all tips for improvement.

public class LRU<K, V> {

    private final Map<K, Entry<K, V>> map;
    private Entry<K, V> eldest;
    private final int lruSize;

    public LRU (int lruSize) {
        if (lruSize <= 0) {
            throw new IllegalArgumentException("size should atleast be one");
        }
        map = new HashMap<K, Entry<K, V>>();
        this.lruSize = lruSize;
    }

    private static class Entry<K, V> {
        Entry<K, V> left;
        K key;
        V value;
        Entry<K, V> right;

        Entry (Entry<K, V> left, K key, V value, Entry<K, V> right) {
            this.left = left;
            this.key = key;
            this.value = value;
            this.right = right;
        }

    };

    /**
     * Head is first node of the linked list.
     * Similar to - convert tree to doubly linkedlist.
     */
    private void addFirst(Entry<K, V> entry) {
        remove(entry);
        if (eldest == null) {
            entry.left = entry.right = entry;
            eldest = entry;
        } else {
            // last node of the list. extra storage just for purpose of simplification
            Entry<K, V> tail = eldest.left;

            tail.right = entry;
            entry.left = tail;

            // now deal with circularing
            eldest.left = entry;
            entry.right = eldest;
        }
    }

    private void remove (Entry<K, V> entry) {
        assert entry != null;

        if (entry.left != null) entry.left.right = entry.right;
        if (entry.right != null) entry.right.left = entry.left;
        if (entry == eldest) eldest = entry.right;
    }


    /**
     * Allowing null. Since, this is behavior of linkedhashmap.
     * Still adding synchronization as interviewer is bound to ask this question
     */
    public synchronized void put(K key, V value) {
        Entry<K, V> entry = new Entry<K, V>(null, key, value, null);
        map.put(key, entry);
        addFirst(entry);

        if (removeEldestEntry()) {
            remove(eldest.key);
        }
    }

    public synchronized V get (K key) {
        Entry<K, V> entry = map.get(key);
        if (entry != null) {
            addFirst(entry);
            return entry.value;
        }
        return null;
    }

    public synchronized void remove (K key) {
       Entry<K, V> entry = map.remove(key);
       if (entry != null) {
           remove(entry);
       }
    }

    private boolean removeEldestEntry() {
        return map.size() > lruSize;
    }
}

Answer 1

The first thing I had to do when seeing your code was looking up “LRU”. Apparently it stands for “Least Recently Used”, something to do with caching.

In your constructor, you initialize the map. This could also be done at the point of declaration:

private final Map<K, Entry<K, V>> map = new HashMap<K, Entry<K, V>>();

You also keep the eldest entry around – it would be more idiomatic to call it the oldest entry.

In your Entry class, I would swap the arguments to (key, value, left, right). Just because one variable points to the left sublist, this does not mean that it has to be the leftmost parameter in the constructor. For each node, the key and value are the more important information, and should come first. Actually, you never use left and right in the Entry constructor.

(…time goes by, now I understand you are implementing a circular buffer as a doubly linked list…)

It would be beneficial to add some helper methods in the Entry class, as this would be better encapsulation.

/** 
 * An Entry in a (circular) doubly linked list.
 */
private static class Entry<K, V> {
  K key;
  V value;
  Entry<K, V> left, right;

  Entry(K key, V value) {
    this.key   = key;
    this.value = value;
  }

  /**
   * Connect "this" and "left" so that "left" is on the left side.
   *
   * @param left The new left side, may be null
   * @return This entry
   */
  Entry<K, V> addLeft(Entry<K, V> left) {
    this.left = left;
    if (left != null) left.right = this;
    return this;
  }

  /**
   * Connect "this" and "right" so that "right" is on the right side.
   *
   * @param right The new right side, may be null
   * @return This entry
   */
  Entry<K, V> addRight(Entry<K, V> right) {
    this.right = right;
    if (right != null) right.left = this;
    return this;
  }

  /**
   * Insert this entry between the specified nodes, keeping track of backlinks.
   *
   * @param left  The new left side, may be null
   * @param right The new right side, may be null
   * @return This entry
   */
  Entry<K, V> insertBetween(Entry<K, V> left, Entry<K, V> right) {
    return this.addLeft(left).addRight(right);
  }

  /**
   * Remove this entry out of the linked list, so that the left
   * and right entries now connect to each other directly.
   */
  void remove() {
    if (this.left  != null) {
      this.left .addRight(this.right);
    }
    else if (this.right != null) {
      this.right.addLeft (this.left );
    }
    this.left = this.right = null;
  }
}

Doing so would also increase testability of your design, and it makes it easier to reason about your code.

This now simplifies your other methods, e.g. addFirst becomes

private void addFirst(Entry<K, V> entry) {
    remove(entry);
    if (oldest == null) {
        oldest = entry.addLeft(entry); // implies addRight(entry)
    } else {
        entry.insertBetween(oldest.left, oldest);
    }
}

and remove simplifies to:

private void remove(Entry<K, V> entry) {
    assert entry != null;

    if (entry == oldest) oldest = entry.right;
    entry.remove();
}

The remaining methods are Ok, because they build upon these operations.

---

In general, the lack of comments made it very hard for me to understand your code.

• For example, I was wondering why you weren't using a LinkedList as a Queue. Then I realized that removing an element would be O(n) instead of O(1). It makes sense to keep track of design decisions in comments, and to specify complexity guarantees in the documentation.
• Then, such comments like “Allowing null. Since, this is behavior of linkedhashmap.” do not convey useful information. What variable may be null? What is linkedhashmap? What does all of that have to do with insertion?

The algorithmic side was excellent, but your code was rather hard to understand.