Design LRU cache interview questions

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

```
public class LRU {

private final Map> map;
private Entry eldest;
private final int lruSize;

public LRU (int lruSize) {
if (lruSize >();
this.lruSize = lruSize;
}

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

Entry (Entry left, K key, V value, Entry 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 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 tail = eldest.left;

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

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

private void remove (Entry 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 entry = new Entry(null, key, value, null);
map.put(key, entry);
addFirst(entry);

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

public synchronized V get (K key) {
Entry entry = map.get(key);
if (entry != null) {
addFi

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> map = new HashMap>();

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 key;
  V value;
  Entry 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 addLeft(Entry 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 addRight(Entry 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 insertBetween(Entry left, Entry 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 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 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.

StackExchange Code Review Q#32849, answer score: 2