跳到主要内容

LFU 缓存题库

LFU 缓存(Least Frequently Used) 最近最不常用的缓存,是一种缓存淘汰策略。 它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。

缓存数据结构​

cache:{
    cnt: 表示缓存使用的频率
    key: 表示缓存的使用时间
    time: 缓存的键
    value: 缓存的值
}

方案一、双哈希表​

实现

class Node {
  prev;
  next;
  constructor(key, val, freq) {
    this.key = key ?? -1;
    this.val = val ?? -1;
    this.freq = freq ?? 0;
  }
}

class DoubleLinkedList {
  constructor() {
    this.size = 0;
    this.dummyHead = new Node();
    this.dummyTail = new Node();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }
  addFirst(node) {
    let prevHead = this.dummyHead.next;
    node.prev = this.dummyHead;
    this.dummyHead.next = node;
    node.next = prevHead;
    prevHead.prev = node;
    this.size++;
  }

  remove(node) {
    let prev = node.prev;
    let next = node.next;
    prev.next = next;
    next.prev = prev;
    this.size--;
  }
  getHead() {
    return this.dummyHead.next;
  }
  getTail() {
    return this.dummyTail.prev;
  }
}

class HashMap {
  constructor(capacity) {
    this.size = 0;
    this.capacity = capacity || 769;
    this.data = new Array(this.capacity).fill(0).map(() => new Array());
  }
  hash(key) {
    return key % this.capacity;
  }
  put(key, value) {
    const hash = this.hash(key);
    for (const item of this.data[hash]) {
      if (item[0] === key) {
        item[1] = value;
        return;
      }
    }
    this.size++;
    this.data[hash].push([key, value]);
  }
  remove(key) {
    const hash = this.hash(key);
    const index = this.data[hash].findIndex((item) => item[0] === key);
    if (index !== -1) {
      this.size--;
      this.data[hash].splice(index, 1);
    }
  }
  get(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return item[1];
      }
    }
    return -1;
  }
  containsKey(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return true;
      }
    }
    return false;
  }
  getOrDefault(key, defaultValue) {
    let result = this.get(key);
    if (result === -1) {
      result = defaultValue;
    }
    return result;
  }
}

class LFUCache {
  constructor(capacity) {
    this.minfreq = 0;
    this.capacity = capacity;
    this.keyTable = new HashMap();
    this.freqTable = new HashMap();
  }

  get(key) {
    if (this.capacity == 0) {
      return -1;
    }
    if (!this.keyTable.containsKey(key)) {
      return -1;
    }
    const node = this.keyTable.get(key);
    const { val, freq } = node;
    const freqItem = this.freqTable.get(freq);
    if (freqItem !== -1) {
      freqItem.remove(node);
    }
    if (freqItem.size == 0) {
      this.freqTable.remove(freq);
      if (this.minfreq == freq) {
        this.minfreq += 1;
      }
    }
    const list = this.freqTable.getOrDefault(freq + 1, new DoubleLinkedList());
    list.addFirst(new Node(key, val, freq + 1));
    this.freqTable.put(freq + 1, list);
    this.keyTable.put(key, this.freqTable.get(freq + 1).getHead());
    return val;
  }

  put(key, value) {
    if (this.capacity == 0) {
      return;
    }
    if (!this.keyTable.containsKey(key)) {
      if (this.keyTable.size === this.capacity) {
        const node = this.freqTable.get(this.minfreq).getTail();
        this.keyTable.remove(node.key);
        const freqItem = this.freqTable.get(this.minfreq);
        if (freqItem !== -1) {
          freqItem.remove(node);
        }
        if (freqItem.size == 0) {
          this.freqTable.remove(this.minfreq);
        }
      }
      const list = this.freqTable.getOrDefault(1, new DoubleLinkedList());
      list.addFirst(new Node(key, value, 1));
      this.freqTable.put(1, list);
      this.keyTable.put(key, this.freqTable.get(1).getHead());
      this.minfreq = 1;
    } else {
      const node = this.keyTable.get(key);
      this.freq = node.freq;
      const freqItem = this.freqTable.get(this.freq);
      if (freqItem !== -1) {
        freqItem.remove(node);
      }
      if (freqItem.size == 0) {
        this.freqTable.remove(this.freq);
        if (this.minfreq == this.freq) {
          this.minfreq += 1;
        }
      }
      const list = this.freqTable.getOrDefault(
        this.freq + 1,
        new DoubleLinkedList()
      );
      list.addFirst(new Node(key, value, this.freq + 1));
      this.freqTable.put(this.freq + 1, list);
      this.keyTable.put(key, this.freqTable.get(this.freq + 1).getHead());
    }
  }
}

方案二、哈希表与AVL树​

思路

用哈希表HashMap 以键 key 为索引存储缓存,建立一个**平衡二叉树 TreeSet**来保持缓存根据(cnt，time)双关键字

  • 对于 get(key) 操作，我们只要查看一下哈希表(HashMap)是否有key这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。

  • 对于 put(key, value) 操作，首先需要查看 HashMap 中是否已有对应的键值。如果有的话操作基本等同于 get(key)，不同的是需要更新缓存的 value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量 capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除 HashMap 中对应的索引，最后向 HashMap 和 TreeSet 插入新的缓存信息即可。

完整代码

class Node {
  left;
  right;
  parent;
  height;
  constructor(key) {
    this.key = key;
    this.height = 0;
  }
  compareTo(target) {
    let targetKey = target;
    if (target instanceof Node) {
      targetKey = target.key;
    }
    return this.key.cnt === targetKey.cnt
      ? this.key.time - targetKey.time
      : this.key.cnt - targetKey.cnt;
  }
}
class TreeSet {
  constructor() {
    this.size = 0;
    this.root = null;
  }
  balanceFactor(node) {
    if (node == null) {
      return 0;
    }
    return this.height(node.left) - this.height(node.right);
  }
  height(node) {
    if (node == null) {
      return 0;
    }
    return node.height;
  }
  updateHeight(node) {
    node.height = Math.max(this.height(node.left), this.height(node.right)) + 1;
  }
  leftRotate(node) {
    let right = node.right;
    node.right = right.left;
    if (right.left) {
      right.left.parent = node;
    }
    right.parent = node.parent;
    if (!node.parent) {
      this.root = right;
    } else if (node.parent.left == node) {
      node.parent.left = right;
    } else {
      node.parent.right = right;
    }
    right.left = node;
    node.parent = right;
    this.updateHeight(node);
    this.updateHeight(right);
  }
  rightRotate(node) {
    let left = node.left;
    node.left = left.right;
    if (left.right) {
      left.right.parent = node;
    }
    left.parent = node.parent;
    if (!node.parent) {
      this.root = left;
    } else if (node.parent.left == node) {
      node.parent.left = left;
    } else {
      node.parent.right = left;
    }
    left.right = node;
    node.parent = left;
    this.updateHeight(node);
    this.updateHeight(left);
  }
  isBalanced(node) {
    if (!node) {
      return true;
    }
    let balanceFactor = this.balanceFactor(node);
    if (Math.abs(balanceFactor) > 1) {
      return false;
    }
    return this.isBalanced(node.left) && this.isBalanced(node.right);
  }
  balance(node) {
    let current = node;
    while (current) {
      this.updateHeight(current);
      if (this.balanceFactor(current) > 1) {
        if (this.balanceFactor(current.left) < 0) {
          this.leftRotate(current.left);
        }
        this.rightRotate(current);
      } else if (this.balanceFactor(current) < -1) {
        if (this.balanceFactor(current.right) > 0) {
          this.rightRotate(current.right);
        }
        this.leftRotate(current);
      } else {
        current = current.parent;
      }
    }
  }
  transplant(aNode, bNode) {
    if (!aNode.parent) {
      this.root = bNode;
    } else if (aNode.parent.left === aNode) {
      aNode.parent.left = bNode;
    } else {
      aNode.parent.right = bNode;
    }
    if (bNode) {
      bNode.parent = aNode.parent;
    }
  }
  add(key) {
    let parent = null;
    let current = this.root;
    this.size++;
    while (current) {
      parent = current;
      if (current.compareTo(key) > 0) {
        current = current.left;
      } else if (current.compareTo(key) < 0) {
        current = current.right;
      } else {
        current.key = key;
        this.size--;
        return;
      }
    }
    const node = new Node(key);
    if (!parent) {
      this.root = node;
    } else {
      if (node.compareTo(parent) < 0) {
        parent.left = node;
      } else {
        parent.right = node;
      }
      node.parent = parent;
    }
    this.balance(node);
  }
  remove(key) {
    let node = this.getNode(key);
    if (node) {
      return this.removeNode(node);
    }
    return false;
  }
  removeNode(node) {
    let remove = node;
    let replace;
    if (!node.left) {
      replace = node.right;
      this.transplant(node, node.right);
    } else if (!node.right) {
      replace = node.left;
      this.transplant(node, node.left);
    } else {
      remove = this.getSucceed(node);
      replace = remove.right;
      if (remove.parent == node) {
        if (replace) {
          replace.parent = remove;
        }
      } else {
        this.transplant(remove, remove.right);
        remove.right = node.right;
        remove.right.parent = remove;
      }
      this.transplant(node, remove);
      remove.left = node.left;
      remove.left.parent = remove;
    }
    this.balance(replace);
    this.size--;
    return true;
  }
  get(key) {
    const node = this.getNode(key);
    return node;
  }
  first() {
    let current = this.root;
    while (current.left) {
      current = current.left;
    }
    return current;
  }
  getNode(key) {
    let current = this.root;
    while (current) {
      if (current.compareTo(key) > 0) {
        current = current.left;
      } else if (current.compareTo(key) < 0) {
        current = current.right;
      } else {
        return current;
      }
    }
    return current;
  }
  getSucceed(node) {
    let right = node.right;
    let succeed = right;
    while (right) {
      succeed = right;
      right = right.left;
    }
    return succeed;
  }
  preOrderTraverse() {
    const result = [];
    if (!this.root) {
      return result;
    }
    const stack = [];
    let currentNode = this.root;
    while (currentNode || stack.length) {
      while (currentNode) {
        stack.push(currentNode);
        result.push(currentNode.key);
        currentNode = currentNode.left;
      }
      currentNode = stack.pop();
      currentNode = currentNode.right;
    }
    return result;
  }
}

class HashMap {
  constructor(capacity) {
    this.size = 0;
    this.capacity = capacity || 769;
    this.data = new Array(this.capacity).fill(0).map(() => new Array());
  }
  hash(key) {
    return key % this.capacity;
  }
  put(key, value) {
    const hash = this.hash(key);
    for (const item of this.data[hash]) {
      if (item[0] === key) {
        item[1] = value;
        return;
      }
    }
    this.size++;
    this.data[hash].push([key, value]);
  }
  remove(key) {
    const hash = this.hash(key);
    const index = this.data[hash].findIndex((item) => item[0] === key);
    if (index !== -1) {
      this.size--;
      this.data[hash].splice(index, 1);
    }
  }
  get(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return item[1];
      }
    }
    return -1;
  }
  containsKey(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return true;
      }
    }
    return false;
  }
}

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.time = 0;
    this.treeSet = new TreeSet();
    this.hashMap = new HashMap();
  }

  get(key) {
    if (this.capacity == 0) {
      return -1;
    }
    if (!this.hashMap.containsKey(key)) {
      return -1;
    }
    const cache = this.hashMap.get(key);
    this.treeSet.remove(cache);
    cache.cnt += 1;
    cache.time = ++this.time;
    this.treeSet.add(cache);
    this.hashMap.put(key, cache);
    return cache.value;
  }

  put(key, value) {
    if (this.capacity == 0) {
      return;
    }
    if (!this.hashMap.containsKey(key)) {
      if (this.hashMap.size === this.capacity) {
        const min = this.treeSet.first();
        if (min) {
          const {
            key: { key: minKey },
          } = min;
          this.hashMap.remove(minKey);
          this.treeSet.remove(min);
        }
      }
      const cache = {
        cnt: 1,
        time: this.time++,
        key,
        value,
      };
      this.hashMap.put(key, cache);
      this.treeSet.add(cache);
    } else {
      const cache = this.hashMap.get(key);
      this.treeSet.remove(cache);
      cache.cnt += 1;
      cache.time = ++this.time;
      cache.value = value;
      this.treeSet.add(cache);
      this.hashMap.put(key, cache);
    }
  }
}

测试用例

const lfu = new LFUCache(3);

[[2, 2], [1, 1], [2], [1], [2], [3, 3], [4, 4], [3], [2], [1], [4]].forEach(
  (item) => {
    if (item.length == 1) {
      eval(`console.log(lfu.get(${item[0]}))`);
    } else {
      eval(`lfu.put(${item[0]},${item[1]})`);
    }
  }
);

方案三、哈希表与红黑树​

思路

用哈希表HashMap 以键 key 为索引存储缓存,建立一个**平衡二叉树 TreeSet**来保持缓存根据(cnt，time)双关键字

  • 对于 get(key) 操作，我们只要查看一下哈希表(HashMap)是否有key这个键即可，有的话需要同时更新哈希表和集合中该缓存的使用频率以及使用时间，否则返回 -1。

  • 对于 put(key, value) 操作，首先需要查看 HashMap 中是否已有对应的键值。如果有的话操作基本等同于 get(key)，不同的是需要更新缓存的 value 值。如果没有的话相当于是新插入一个缓存，这时候需要先查看是否达到缓存容量 capacity，如果达到了的话，需要删除最近最少使用的缓存，即平衡二叉树中最左边的结点，同时删除 HashMap 中对应的索引，最后向 HashMap 和 TreeSet 插入新的缓存信息即可。

实现

const RED = "0";
const BLACK = "1";

class Node {
  left;
  right;
  parent;
  constructor(key, color) {
    this.key = key;
    this.color = color || RED;
  }
  compareTo(target) {
    let targetKey = target;
    if (target instanceof Node) {
      targetKey = target.key;
    }
    return this.key.cnt === targetKey.cnt
      ? this.key.time - targetKey.time
      : this.key.cnt - targetKey.cnt;
  }
}
class TreeSet {
  constructor() {
    this.size = 0;
    this.root = null;
    this.dummyNode = new Node(null, BLACK);
  }
  leftRotate(node) {
    let right = node.right;
    node.right = right.left;
    if (right.left !== this.dummyNode) right.left.parent = node;
    right.parent = node.parent;
    if (node.parent === this.dummyNode) this.root = right;
    else if (node.parent.left == node) node.parent.left = right;
    else node.parent.right = right;
    right.left = node;
    node.parent = right;
  }
  rightRotate(node) {
    let left = node.left;
    node.left = left.right;
    if (left.right !== this.dummyNode) left.right.parent = node;
    left.parent = node.parent;
    if (node.parent === this.dummyNode) {
      this.root = left;
    } else if (node.parent.left == node) {
      node.parent.left = left;
    } else {
      node.parent.right = left;
    }
    left.right = node;
    node.parent = left;
  }
  transplant(aNode, bNode) {
    if (aNode.parent === this.dummyNode) {
      this.root = bNode;
    } else if (aNode.parent.left === aNode) {
      aNode.parent.left = bNode;
    } else {
      aNode.parent.right = bNode;
    }
    bNode.parent = aNode.parent;
  }
  fixAdd(node) {
    while (node.parent.color == RED) {
      if (node.parent == node.parent.parent.left) {
        let uncle = node.parent.parent.right;
        if (uncle && uncle.color == RED) {
          uncle.color = BLACK;
          node.parent.color = BLACK;
          node.parent.parent.color = RED;
          node = node.parent.parent;
        } else if (node == node.parent.right) {
          node = node.parent;
          this.leftRotate(node);
        } else {
          node.parent.color = BLACK;
          node.parent.parent.color = RED;
          this.rightRotate(node.parent.parent);
        }
      } else {
        let uncle = node.parent.parent.left;
        if (uncle && uncle.color == RED) {
          uncle.color = BLACK;
          node.parent.color = BLACK;
          node.parent.parent.color = RED;
          node = node.parent.parent;
        } else if (node == node.parent.left) {
          node = node.parent;
          this.rightRotate(node);
        } else {
          node.parent.color = BLACK;
          node.parent.parent.color = RED;
          this.leftRotate(node.parent.parent);
        }
      }
    }
    this.root.color = BLACK;
  }
  fixRemove(node) {
    while (node != this.root && node.color == BLACK) {
      if (node === node.parent.left) {
        let brother = node.parent.right;
        if (brother.color == RED) {
          brother.color = BLACK;
          node.parent.color = RED;
          this.leftRotate(node.parent);
          brother = node.parent.right;
        }
        if (brother.left.color === BLACK && brother.right.color === BLACK) {
          brother.color = RED;
          node = node.parent;
        } else if (brother.right.color === BLACK) {
          brother.left.color = BLACK;
          brother.color = RED;
          this.rightRotate(brother);
          brother = node.parent.right;
        } else {
          brother.color = node.parent.color;
          node.parent.color = BLACK;
          brother.right.color = BLACK;
          this.leftRotate(node.parent);
          node = this.root;
        }
      } else {
        let brother = node.parent.left;
        if (brother.color == RED) {
          brother.color = BLACK;
          node.parent.color = RED;
          this.rightRotate(node.parent);
          brother = node.parent.left;
        }
        if (brother.right.color === BLACK && brother.left.color === BLACK) {
          brother.color = RED;
          node = node.parent;
        } else if (brother.left.color === BLACK) {
          brother.right.color = BLACK;
          brother.color = RED;
          this.leftRotate(brother);
          brother = node.parent.left;
        } else {
          brother.color = node.parent.color;
          node.parent.color = BLACK;
          brother.left.color = BLACK;
          this.rightRotate(node.parent);
          node = this.root;
        }
      }
    }
    if (node) {
      node.color = BLACK;
    }
  }
  add(key) {
    let parent = this.dummyNode;
    let current = this.root;
    this.size++;
    while (current !== null && current !== this.dummyNode) {
      parent = current;
      if (current.compareTo(key) > 0) {
        current = current.left;
      } else if (current.compareTo(key) < 0) {
        current = current.right;
      } else {
        current.key = key;
        this.size--;
        return;
      }
    }
    const node = new Node(key);
    node.parent = parent;
    if (parent === this.dummyNode) {
      this.root = node;
    } else if (node.compareTo(parent) < 0) {
      parent.left = node;
    } else {
      parent.right = node;
    }
    node.left = this.dummyNode;
    node.right = this.dummyNode;
    this.fixAdd(node);
  }
  remove(key) {
    let node = this.getNode(key);
    if (node) {
      return this.removeNode(node);
    }
    return false;
  }
  removeNode(node) {
    let remove = node;
    let removeColor = remove.color;
    let replace;
    if (node.left === this.dummyNode) {
      replace = node.right;
      this.transplant(node, node.right);
    } else if (node.right === this.dummyNode) {
      replace = node.left;
      this.transplant(node, node.left);
    } else {
      remove = this.getSucceed(node);
      removeColor = remove.color;
      replace = remove.right;
      if (remove.parent == node) {
        replace.parent = remove;
      } else {
        this.transplant(remove, remove.right);
        remove.right = node.right;
        remove.right.parent = remove;
      }
      this.transplant(node, remove);
      remove.left = node.left;
      remove.left.parent = remove;
      remove.color = node.color;
    }
    if (removeColor === BLACK) {
      this.fixRemove(replace);
    }
    this.size--;
    return true;
  }
  get(key) {
    return this.getNode(key);
  }
  first() {
    let current = this.root;
    while (current.left !== this.dummyNode) {
      current = current.left;
    }
    return current;
  }
  getNode(key) {
    let current = this.root;
    while (current !== null && current !== this.dummyNode) {
      if (current.compareTo(key) > 0) {
        current = current.left;
      } else if (current.compareTo(key) < 0) {
        current = current.right;
      } else {
        return current;
      }
    }
    return current;
  }
  getSucceed(node) {
    let right = node.right;
    let succeed = right;
    while (right !== this.dummyNode) {
      succeed = right;
      right = right.left;
    }
    return succeed;
  }
  levelRraversal() {
    const result = [];
    const queue = [];
    queue.push(this.root);
    while (queue.length) {
      let temp = queue.shift();
      result.push(temp);
      if (temp.left !== this.dummyNode) queue.push(temp.left);
      if (temp.right !== this.dummyNode) queue.push(temp.right);
    }
    return result;
  }
}

class HashMap {
  constructor(capacity) {
    this.size = 0;
    this.capacity = capacity || 769;
    this.data = new Array(this.capacity).fill(0).map(() => new Array());
  }
  hash(key) {
    return key % this.capacity;
  }
  put(key, value) {
    const hash = this.hash(key);
    for (const item of this.data[hash]) {
      if (item[0] === key) {
        item[1] = value;
        return;
      }
    }
    this.size++;
    this.data[hash].push([key, value]);
  }
  remove(key) {
    const hash = this.hash(key);
    const index = this.data[hash].findIndex((item) => item[0] === key);
    if (index !== -1) {
      this.size--;
      this.data[hash].splice(index, 1);
    }
  }
  get(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return item[1];
      }
    }
    return -1;
  }
  containsKey(key) {
    const hash = this.hash(key);
    for (let item of this.data[hash]) {
      if (item[0] === key) {
        return true;
      }
    }
    return false;
  }
}

class LFUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.time = 0;
    this.treeSet = new TreeSet();
    this.hashMap = new HashMap();
  }

  get(key) {
    if (this.capacity == 0) {
      return -1;
    }
    if (!this.hashMap.containsKey(key)) {
      return -1;
    }
    const cache = this.hashMap.get(key);
    this.treeSet.remove(cache);
    cache.cnt += 1;
    cache.time = ++this.time;
    this.treeSet.add(cache);
    this.hashMap.put(key, cache);
    return cache.value;
  }

  put(key, value) {
    if (this.capacity == 0) {
      return;
    }
    if (!this.hashMap.containsKey(key)) {
      if (this.hashMap.size === this.capacity) {
        const min = this.treeSet.first();
        if (min) {
          const {
            key: { key: minKey },
          } = min;
          this.hashMap.remove(minKey);
          this.treeSet.remove(min);
        }
      }
      const cache = {
        cnt: 1,
        time: this.time++,
        key,
        value,
      };
      this.hashMap.put(key, cache);
      this.treeSet.add(cache);
    } else {
      const cache = this.hashMap.get(key);
      this.treeSet.remove(cache);
      cache.cnt += 1;
      cache.time = ++this.time;
      cache.value = value;
      this.treeSet.add(cache);
      this.hashMap.put(key, cache);
    }
  }
}

测试用例

const lfu = new LFUCache(10);

[
  [10],
  [10, 13],
  [3, 17],
  [6, 11],
  [10, 5],
  [9, 10],
  [13],
  [2, 19],
  [2],
  [3],
  [5, 25],
  [8],
  [9, 22],
  [5, 5],
  [1, 30],
  [11],
  [9, 12],
  [7],
  [5],
  [8],
  [9],
  [4, 30],
  [9, 3],
  [9],
  [10],
  [10],
  [6, 14],
  [3, 1],
  [3],
  [10, 11],
  [8],
  [2, 14],
  [1],
  [5],
  [4],
  [11, 4],
  [12, 24],
  [5, 18],
  [13],
  [7, 23],
  [8],
  [12],
  [3, 27],
  [2, 12],
  [5],
  [2, 9],
  [13, 4],
  [8, 18],
  [1, 7],
  [6],
  [9, 29],
  [8, 21],
  [5],
  [6, 30],
  [1, 12],
  [10],
  [4, 15],
  [7, 22],
  [11, 26],
  [8, 17],
  [9, 29],
  [5],
  [3, 4],
  [11, 30],
  [12],
  [4, 29],
  [3],
  [9],
  [6],
  [3, 4],
  [1],
  [10],
  [3, 29],
  [10, 28],
  [1, 20],
  [11, 13],
  [3],
  [3, 12],
  [3, 8],
  [10, 9],
  [3, 26],
  [8],
  [7],
  [5],
  [13, 17],
  [2, 27],
  [11, 15],
  [12],
  [9, 19],
  [2, 15],
  [3, 16],
  [1],
  [12, 17],
  [9, 1],
  [6, 19],
  [4],
  [5],
  [5],
  [8, 1],
  [11, 7],
  [5, 2],
  [9, 28],
  [1],
  [2, 2],
  [7, 4],
  [4, 22],
  [7, 24],
  [9, 26],
  [13, 28],
  [11, 26],
].forEach((item) => {
  if (item.length == 1) {
    eval(`lfu.get(${item[0]})`);
  } else {
    eval(`lfu.put(${item[0]},${item[1]})`);
  }
});