Original Problem

Past Solutions


  • The idea here is to use a Hash Map to keep a mapping between the key and the value. And we use a Double Linked List to keep track the least recently used key-value pair and most recently used key-value pair in constant time
  • The value in the hash map is mapped to a node inside the double linked list, so we are able to locate the least recently used key-value pair in linear time
  • We also make use of Virtual Node to make the linked list operations easy to manage. Refer to Linked List Tips to help with the solution implementation

Space & Time Analysis

The analysis method we are using is Algorithm Complexity Analysis

Space - O(n)

  • Ignore input size & language dependent space
  • we are using a Hash Map to hold the key-node pairs

Time - O(1)

  • Both get() and put() are O(1)


4th Attempt (Java)

public class Node {
    int key;
    int val;
    Node prev;
    Node next;
    Node(int key, int val) {
        this.key = key;
        this.val = val;
class LRUCache {
    int capacity;
    HashMap<Integer, Node> map;
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        // Recently Used
        Node currNode = map.get(key);
        return currNode.val;
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node currNode = map.get(key);
            currNode.val = value;
            // Recently Used (updated)
        if (map.size() < capacity) {
            Node newNode = new Node(key, value);
            // Recently Used (added)
            map.put(key, newNode);
        // Evict
        Node lastNode = tail.prev;
        // Add
        Node newNode = new Node(key, value);
        map.put(key, newNode);
        // Recently Used (added)
    void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    void accessed(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next = node;
        node.next.prev = node;
 * 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);

Personal Reflection

  • Why it takes so long to solve: Rusty with Double Linked List implementation in Java
  • What you could have done better: Sketch out the things to note. For example, the place to update the Hash Map and the double linked list
  • What you missed: NIL
  • Ideas you’ve seen before: hashmap, double linked list
  • Ideas you found here that could help you later: NIL
  • Ideas that didn’t work and why: NIL