2
\$\begingroup\$

Problem Statement

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.

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

Solution

This problem can be solved by implementing the Cache as a doubly linked list with head and tail pointers. This gives us constant time access to the head and tail of the Cache. For constant time access to all other nodes we can create a hashmap processMap which maps a key to its corresponding node in the Cache. Now, we can access any node in the linkedlist in constant time.

public void put(int key, int value) - First we check if there already exists an entry with the same key in the Cache. If it does then we remove this old entry from the processMap and the linked list. After this we insert the new entry at the end of the linked list.

public int get(int key) - We lookup the processMap and if there's an entry for the given key, we output the value of the node, remove the node from its current position and insert it at the end of the list. Otherwise, we return -1.

class ProcessNode {
    private int key, value;
    private ProcessNode previous, next;

    public ProcessNode(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getKey() {
        return key;
    }

    public int getValue() {
        return value;
    }

    public void setNext(ProcessNode next) {
        this.next = next;
    }

    public ProcessNode getNext() {
        return next;
    }

    public void setPrevious(ProcessNode previous) {
        this.previous = previous;
    }

    public ProcessNode getPrevious() {
        return previous;
    }
}

class LRUCache {
    private int size = 0;
    private int capacity;

    private ProcessNode head = null;
    private ProcessNode tail = null;

    private Map<Integer, ProcessNode> processMap = new HashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        ProcessNode processNode = processMap.get(key);

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

        remove(processNode);
        addLast(processNode);

        return processNode.getValue();
    }

    private void remove(ProcessNode processNode) {
        if (processNode == null) {
            return;
        }

        if ((processNode != head) && (processNode != tail)) {
            processNode.getPrevious().setNext(processNode.getNext());
            processNode.getNext().setPrevious(processNode.getPrevious());
        } else {
            if (processNode == head) {
                head = processNode.getNext();

                if (head != null) {
                    head.setPrevious(null);
                }
            }

            if (processNode == tail) {
                tail = processNode.getPrevious();

                if (tail != null) {
                    tail.setNext(null);
                }
            }
        }

        size--;
        processMap.remove(processNode.getKey());
    }

    private void removeFirst() {
        remove(head);
    }

    private void addLast(ProcessNode processNode) {
        if (size == capacity) {
            removeFirst();
        }

        if (tail != null) {
            tail.setNext(processNode);
            processNode.setPrevious(tail);
            tail = processNode;
        } else {
            head = processNode;
            tail = processNode;
        }

        size++;
        processMap.put(processNode.getKey(), processNode);
    }

    public void put(int key, int value) {
        ProcessNode existingNode = processMap.get(key);

        if (existingNode != null) {
            remove(existingNode);
        }

        ProcessNode newProcessNode = new ProcessNode(key, value);

        addLast(newProcessNode);
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Please review my code and let me know if there's room for improvement.

\$\endgroup\$
2
\$\begingroup\$

Information hiding

If ProcessNode is only used by LRUCache, then it's an implementation detail that's best hidden from other classes. Instead of a local class, it would be better as a private static inner class.

Encapsulation and separation of concerns

LRUCache does multiple things:

  • Enforce a maximum number of key value pairs
  • Linked list operations

The linked list operations could be delegated to a dedicated class with remove(ListNode), removeFirst(ListNode), add(ListNode) methods.

With this reorganization, the implementation of LRUCache's main methods can focus on enforcing the bound on the number of entries, and be overall more clear and easier to understand, without having to follow through multiple methods the state changes of nodes, the map, and the size:

  public int get(int key) {
    ListNode node = nodeMap.get(key);

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

    list.remove(node);
    list.add(node);

    return node.getValue();
  }

  public void put(int key, int value) {
    ListNode newNode = new ListNode(key, value);
    list.add(newNode);

    ListNode oldNode = nodeMap.put(key, newNode);

    if (oldNode != null) {
      list.remove(oldNode);
    } else if (nodeMap.size() > capacity) {
      ListNode eldest = list.removeFirst();
      nodeMap.remove(eldest.getKey());
    }
  }

Naming

ProcessNode is just a node in a linked list. I find name "Process" a bit confusing. I recommend renaming to ListNode.

Minor technical improvements

There's no need to manage size manually, the map of nodes already has that information.

Some values are only assigned once, so they can be final, such as capacity, key, value.

The getters and setters are overkill for the node class without plans of future extensions. Especially when moved inside an inner LinkedList class. There's no real need here for such verbose boilerplate code.

\$\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.