class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = {};
    this.lfu = null;
  }
  get(key) {
    if (Object.keys(this.cache).contains(key)) {
      let { value } = this.cache[key];
      this.cache[key].frequency += 1;
      this.cache[key].last = new Date();
      return value;
    }
    return -1;
  }

  put(key, value) {
    let keys = Object.keys(this.cache);
    if (!keys.contains(key)) {
      if (keys.length === this.capacity) {
        for (let k = 0; k < keys.length; k += 1) {
          if (this.lfu) {
            if (this.cache[k].frequency < this.cache[this.lfu].frequency) {
              this.lfu = k;
            } else if (this.cache[k].frequency === this.cache[this.lfu].frequency) {
              if (this.cache[k].last < this.cache[this.lfu].last) {
                this.lfu = k;
              }
            }
          } else {
            this.lfu = k;
          }
        }
        delete this.cache[this.lfu];
        this.lfu = null;
      }
      this.cache[key] = {
        value,
        frequency: 0,
        last: new Date(),
      };
    }
  }
}