1
class MinStack {
2
  private stack: number[] = [];
3
  private minStack: number[] = [];
4

5
  push(value: number): void {
6
    this.stack.push(value);
7
    const min = this.minStack.length === 0
8
      ? value
9
      : Math.min(value, this.minStack[this.minStack.length - 1]);
10
    this.minStack.push(min);
11
  }
12

13
  pop(): void {
14
    this.stack.pop();
15
    this.minStack.pop();
16
  }
17

18
  top(): number {
19
    return this.stack[this.stack.length - 1];
20
  }
21

22
  getMin(): number {
23
    return this.minStack[this.minStack.length - 1];
24
  }
25
}

1
class MyHashSet {
2
  private readonly size = 769;
3
  private buckets: number[][] = Array.from({ length: 769 }, () => []);
4

5
  private hash(key: number): number {
6
    return key % this.size;
7
  }
8

9
  add(key: number): void {
10
    const bucket = this.buckets[this.hash(key)];
11
    if (!bucket.includes(key)) bucket.push(key);
12
  }
13

14
  remove(key: number): void {
15
    const bucket = this.buckets[this.hash(key)];
16
    const index = bucket.indexOf(key);
17
    if (index !== -1) bucket.splice(index, 1);
18
  }
19

20
  contains(key: number): boolean {
21
    return this.buckets[this.hash(key)].includes(key);
22
  }
23
}

1
class DLinkedNode {
2
  key: number;
3
  value: number;
4
  prev: DLinkedNode | null = null;
5
  next: DLinkedNode | null = null;
6

7
  constructor(key: number, value: number) {
8
    this.key = key;
9
    this.value = value;
10
  }
11
}

1
class LRUCache {
2
  private cache = new Map<number, DLinkedNode>();
3
  private head = new DLinkedNode(0, 0);
4
  private tail = new DLinkedNode(0, 0);
5

6
  constructor(private capacity: number) {
7
    this.head.next = this.tail;
8
    this.tail.prev = this.head;
9
  }
10

11
  get(key: number): number {
12
    const node = this.cache.get(key);
13
    if (!node) return -1;
14

15
    this.moveToHead(node);
16
    return node.value;
17
  }
18

19
  put(key: number, value: number): void {
20
    const existing = this.cache.get(key);
21
    if (existing) {
22
      existing.value = value;
23
      this.moveToHead(existing);
24
      return;
25
    }
26

27
    const node = new DLinkedNode(key, value);
28
    this.cache.set(key, node);
29
    this.addToHead(node);
30

31
    if (this.cache.size > this.capacity) {
32
      const removed = this.removeTail();
33
      this.cache.delete(removed.key);
34
    }
35
  }
36

37
  private addToHead(node: DLinkedNode): void {
38
    node.prev = this.head;
39
    node.next = this.head.next;
40
    this.head.next!.prev = node;
41
    this.head.next = node;
42
  }
43

44
  private removeNode(node: DLinkedNode): void {
45
    node.prev!.next = node.next;
46
    node.next!.prev = node.prev;
47
  }
48

49
  private moveToHead(node: DLinkedNode): void {
50
    this.removeNode(node);
51
    this.addToHead(node);
52
  }
53

54
  private removeTail(): DLinkedNode {
55
    const node = this.tail.prev!;
56
    this.removeNode(node);
57
    return node;
58
  }
59
}

1
interface LFUNode {
2
  key: number;
3
  value: number;
4
  freq: number;
5
}
6

7
class LFUCache {
8
  private minFreq = 0;
9
  private keyToNode = new Map<number, LFUNode>();
10
  private freqToKeys = new Map<number, Set<number>>();
11

12
  constructor(private capacity: number) {}
13

14
  get(key: number): number {
15
    const node = this.keyToNode.get(key);
16
    if (!node) return -1;
17

18
    this.increaseFreq(key);
19
    return node.value;
20
  }
21

22
  put(key: number, value: number): void {
23
    if (this.capacity === 0) return;
24

25
    const node = this.keyToNode.get(key);
26
    if (node) {
27
      node.value = value;
28
      this.increaseFreq(key);
29
      return;
30
    }
31

32
    if (this.keyToNode.size >= this.capacity) {
33
      const evictKey = this.freqToKeys.get(this.minFreq)!.values().next().value;
34
      this.freqToKeys.get(this.minFreq)!.delete(evictKey);
35
      this.keyToNode.delete(evictKey);
36
    }
37

38
    this.keyToNode.set(key, { key, value, freq: 1 });
39
    if (!this.freqToKeys.has(1)) this.freqToKeys.set(1, new Set());
40
    this.freqToKeys.get(1)!.add(key);
41
    this.minFreq = 1;
42
  }
43

44
  private increaseFreq(key: number): void {
45
    const node = this.keyToNode.get(key)!;
46
    const oldKeys = this.freqToKeys.get(node.freq)!;
47
    oldKeys.delete(key);
48

49
    if (oldKeys.size === 0 && node.freq === this.minFreq) {
50
      this.minFreq++;
51
    }
52

53
    node.freq++;
54
    if (!this.freqToKeys.has(node.freq)) this.freqToKeys.set(node.freq, new Set());
55
    this.freqToKeys.get(node.freq)!.add(key);
56
  }
57
}