Almighty javascript! :)


  • 1
    S

    /**

    • @constructor
      */
      var LRUCache = function(capacity) {
      this._capacity = capacity;
      this._usage = [];
      this._cache = {};
      };

    /**

    • @param {number} key
    • @returns {number}
      */
      LRUCache.prototype.get = function(key) {
      var val = this._cache[key];
      if(val === undefined){
      return -1;
      }
      var idx = this._usage.indexOf(key);
      this._usage.splice(idx,1);
      this._usage.push(key);
      return val;
      };

    /**

    • @param {number} key
    • @param {number} value
    • @returns {void}
      */
      LRUCache.prototype.set = function(key, value) {
      if(this._cache[key]){
      this._cache[key] = value;
      var idx = this._usage.indexOf(key);
      this._usage.splice(idx,1);
      this._usage.push(key);
      }else{
      if(this._usage.length === this._capacity){
      var tbd = this._usage.shift();
      delete this._cache[tbd];
      }
      this._usage.push(key);
      this._cache[key] = value;
      }
      };

  • 0

    @soloist Simple and easy solution. Javascript is always fun :)


  • 3
    D

    @soloist I thought splice and shift operation costs O(n) time. If this code works on O(n) it is not a cache :)


  • 0
    S

    @dralpus I guess we just use array to mimic the linkedlist data structure, though it's O(n) in this case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.