1 LRU Cache

map: key → node        doubly-linked list: MRU at head
get:  move node to head, return value (or -1)
put:  insert at head;  over capacity → evict tail.prev

All ops O(1).

private void remove(Node n) {
    n.prev.next = n.next;
    n.next.prev = n.prev;
}

private void insert(Node n) {          // at head (MRU)
    n.next = head.next;
    n.prev = head;
    head.next.prev = n;
    head.next = n;
}

---

2 LFU Cache

vals[key], freqs[key], buckets[freq] = ordered keys
bump(key): move key freq → freq+1; fix minFreq
evict:     pop oldest from buckets[minFreq]

---

3 RandomizedSet

insert: append array; map[val] = last index
remove: swap arr[i] ↔ arr[last]; pop; fix moved index
random: arr[rand() % size]

Swap-delete keeps the array dense — uniform random stays O(1).

---

4 TimeMap

set: append (timestamp, value) — always increasing
get: binary search largest timestamp ≤ t

---

5 Ordered Operations Cheat Sheet

Need	Java	C++	Python
Greatest ≤ x	floorKey	prev(lower_bound)	bisect_right-1
Smallest ≥ x	ceilingKey	lower_bound	bisect_left
Sorted container	TreeMap	std::map	SortedList