146. LRU Cache - JS

1. Description

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.

2. Follow up:

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

3. 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

4. Solution

class LRU{
  
  constructor(v){
    this.size = v;
    this.map = new Map();
    this.head = new Node(0,0);
    this.tail = new Node(0,0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }
  
  put( key, val ){
    let node = new Node(key, val);
    this.map.set( key, node );
    this.insertFront( node );
    
    if( this.size < this.map.size ){
      this.removeLast();
    }
  }
  
  get( key ){
    if( !this.map.has(key) ) return -1;
    let node = this.map.get(key);
    this.breakAndLink(node);
    this.insertFront(node);
    return node.val;
  }
  
  breakAndLink(node){
    let p = node.prev;
    let n = node.next;
    p.next = n;
    n.prev = p;
    node.next = null;
    node.prev = null;
  }
  
  insertFront(node){
    let h2 = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    h2.prev = node;
    node.next = h2;
  }
  
  removeLast(){
    // remove from linklist
    let node = this.tail.prev;
    this.breakAndLink(node);
    // remove from map
    this.map.delete(node.key);
  }  
}

class Node{
  constructor(key, val){
    this.key = key;
    this.val = val;
    this.next = null;
    this.prev = null;
  }
}


// test
let cache = new LRU( 2 );
cache.put(1, 1);
cache.put(2, 2);

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