var LFUCache = function(capacity) {
  this.storage = {};
  this.capacity = capacity;
  this.history = [];
  this.usage = 0;
};

LFUCache.prototype.get = function(key) {
  // check if key exists on this.storage
  if (this.storage[key]) {
    // if so, increment frequency by 1
    this.storage[key].frequency += 1;
    // push to this.history
    this.history.push(key);
    return this.storage[key].value;
  }
  return -1;
};

LFUCache.prototype.put = function(key, value) {
  // check if we have reached capacity Object.keys(this.storage).length
  if (Object.keys(this.storage).length === this.capacity) {
    let frequency;
    let least;
    let tiebreaker = [];
    // for each key in this.storage
    for (let key in this.storage) {
      if (!frequency) {
        frequency = this.storage[key].frequency;
      }
      if (this.storage[key].frequency < frequency) {
        frequency = this.storage[key].frequency;
        least = key;
      }
    }
    for (let key in this.storage) {
      if (this.storage[key].frequency === frequency) {
        tiebreaker.push(key);
      }
    }
    delete this.storage[least];
  }
};

 // the put function
 // check the capacity: has it been reached?
 // if it hasn't, we can add it to an object called storage, with frequency of 0
 // if we have reached the capacity, we remove the least used key using for/in
 // if there's a tie, then we loop through history and remove the first key we encounter
 // then we add the kv pair

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

 // get inputs: key
 // get output: value, or -1 if does not exist

 // put: key and value
 // output: return the value

 // constraints: values in puts will always be positive
 // keep track of how many times each kv pair has been accessed
 // kv pair: key: {value: x, frequency: x}
 // array, call it history: [key1, key2, key3]

 // the get function
 // look up the key
 // if it exists return the value
 // increment frequency by 1
 // push the key to the history array
 // if it doesn't exist, return -1