LRU Cache

Description

doc

Solutions

First Idea

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity

  this.LRUCache = new Map()
  this.low = 0
  this.high = 0

  this.cache = new Map()
}

LRUCache.prototype.getLRUKey = function () {
  while (!this.LRUCache.has(this.low) && this.low < this.high) {
    this.low++
  }

  return this.LRUCache.get(this.low)
}

LRUCache.prototype.remove = function (key) {
  const cur = this.cache.get(key)
  if (cur) {
    this.cache.delete(key)
    this.LRUCache.delete(cur.cacheKey)
  }

  return cur
}

LRUCache.prototype.add = function (key, value) {
  this.cache.set(key, { cacheKey: this.high, value })
  this.LRUCache.set(this.high++, key)
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.cache.has(key)) {
    return -1
  }

  const prev = this.remove(key)
  this.add(key, prev.value)
  return prev.value
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.cache.has(key)) {
    this.remove(key)
  }

  if (this.cache.size >= this.capacity) {
    const LRUKey = this.getLRUKey()
    this.remove(LRUKey)
  }

  this.add(key, value)
}

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