These are the notes for DSA episode 86: two design problems, where you build a whole data structure whose every operation must be fast. Insert-delete-getRandom O(1) (LeetCode 380): an ArrayList is fair at random picks but its contains and remove are O(n), a HashSet finds names instantly but has no index to pick from, and both time out on 2 lakh names; an array plus a map from value to index, where a removed element's hole is filled by the last element, makes all three operations O(1). The LFU cache (LeetCode 460, hard): scanning every key for the least frequently used one is correct but times out with capacity 1 lakh; one bucket per use count, each bucket a LinkedHashSet that keeps the oldest key first, plus the minimum frequency, makes get and put O(1). Every program below was run with javac 21 (25-second limit and a 1.5 GB heap, like the SyntaxPilot compiler), g++ 13 and Python 3, and every output shown is real (timings vary by machine).
The problems, in real life
| Real life | In code |
|---|---|
| People drop their names into a lucky-draw box at a Diwali mela | insert(x) |
| Some people leave early and take their names out | remove(x) |
| The organiser picks one winner, every name with the same chance | getRandom() |
| A sweet shop's front shelf has room for only a few boxes | a cache with capacity |
| When a new sweet needs the shelf, the least asked-for one goes back | evict the least frequently used key |
| Two sweets asked for equally often? The one asked for longest ago goes back | ties broken by least recently used |
Every word, from zero
- Design problem: build a class with several operations (a data structure), not a single function.
- O(1), constant time: the time doesn't grow with the number of elements.
- Average O(1): most calls are O(1); a rare slow call (a hash map resizing) is allowed, as long as the total stays O(1) per call on average.
- O(n): time that grows in proportion to the number of elements
n. - Uniformly random: every element has the same chance,
1/n. - ArrayList: Java's growable array.
get(i)is O(1);containsandindexOflook at elements one by one (O(n));remove(i)shifts every later element left (O(n)), except at the end (O(1)). - Hash, HashSet, HashMap: a hash turns a value into a slot number, so
add,contains,remove,getandputare O(1) on average. A set has no index, so it can't pick "element number k" quickly. - Seed: the starting number of a random generator; the same seed gives the same "random" numbers, so a demo is repeatable.
- Cache: a small, fast store with room for
capacityitems. - Evict: throw an item out of a full cache to make room.
- LRU (least recently used): evict the item used longest ago (episode 25).
- LFU (least frequently used): evict the item with the smallest use count; every
getand everyputof a key counts as one use. - Frequency / use count: how many times a key was used.
- Bucket: a group of keys that share the same use count.
- LinkedHashSet: a hash set that also remembers the order elements were added;
iterator().next()gives the oldest, andremove(x)is still O(1). - computeIfAbsent(k, f): returns the value for key
k, creating it withffirst if it's missing. - minFreq: the smallest use count that has at least one key.
- Heap: a structure that always keeps its smallest item on top; insert and remove are O(log n).
Problem 1: insert-delete-getRandom O(1) (LeetCode 380)
Build RandomizedSet with insert(x) (add if absent, return true; else false), remove(x) (remove if present, return true; else false) and getRandom() (each element equally likely), all in average O(1).
| Calls | Results |
|---|---|
insert(1) remove(2) insert(2) getRandom() remove(1) insert(2) getRandom() |
true false true (1 or 2) true false 2 |
Obvious idea 1: an ArrayList
import java.util.*;
public class Main {
static class RandomizedSet {
List<Integer> a = new ArrayList<>();
Random rnd = new Random(42);
boolean insert(int x) {
if (a.contains(x)) return false;
a.add(x);
return true;
}
boolean remove(int x) {
int i = a.indexOf(x);
if (i < 0) return false;
a.remove(i);
return true;
}
int getRandom() {
return a.get(rnd.nextInt(a.size()));
}
}
public static void main(String[] args) {
RandomizedSet s = new RandomizedSet();
System.out.println(s.insert(1) + " " + s.remove(2) + " " + s.insert(2));
System.out.println(s.getRandom() + " " + s.remove(1) + " " + s.insert(2));
System.out.println(s.getRandom());
}
}
Output (real):
true false true
2 true false
2
Correct. Now the big test: 2 lakh inserts, 2 lakh random picks, then every second name removed.
import java.util.*;
public class Main {
static class RandomizedSet {
List<Integer> a = new ArrayList<>();
Random rnd = new Random(42);
boolean insert(int x) {
if (a.contains(x)) return false;
a.add(x);
return true;
}
boolean remove(int x) {
int i = a.indexOf(x);
if (i < 0) return false;
a.remove(i);
return true;
}
int getRandom() {
return a.get(rnd.nextInt(a.size()));
}
}
public static void main(String[] args) {
RandomizedSet s = new RandomizedSet();
int n = 200_000, left = 0;
long t0 = System.nanoTime(), sum = 0;
for (int i = 0; i < n; i++) if (s.insert(i)) left++;
for (int i = 0; i < n; i++) sum += s.getRandom();
for (int i = 0; i < n; i += 2) if (s.remove(i)) left--;
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("left " + left + ", " + ms + " ms");
}
}
Output (real): nothing is printed. The program is still running after 25 seconds: Time Limit Exceeded. Every insert calls contains, which walks the whole list: about 2 lakh × 2 lakh / 2 = 2 × 10¹⁰ steps. And remove(i) from the middle shifts every later element.
Obvious idea 2: a HashSet
add and remove are O(1) now, but a set has no index, so getRandom picks a random k and walks the set to the k-th element:
import java.util.*;
public class Main {
static class RandomizedSet {
Set<Integer> set = new HashSet<>();
Random rnd = new Random(42);
boolean insert(int x) { return set.add(x); }
boolean remove(int x) { return set.remove(x); }
int getRandom() {
int k = rnd.nextInt(set.size());
for (int x : set)
if (k-- == 0) return x;
return -1;
}
}
public static void main(String[] args) {
RandomizedSet s = new RandomizedSet();
int n = 200_000, left = 0;
long t0 = System.nanoTime(), sum = 0;
for (int i = 0; i < n; i++) if (s.insert(i)) left++;
for (int i = 0; i < n; i++) sum += s.getRandom();
for (int i = 0; i < n; i += 2) if (s.remove(i)) left--;
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("left " + left + ", " + ms + " ms");
}
}
Output (real): Time Limit Exceeded again. Inserts finish at once, but each of the 2 lakh picks walks about a lakh elements.
The key insight: numbered chairs and a register
| At the mela | In Java | Cost |
|---|---|---|
| Everyone sits on numbered chairs, no gaps | ArrayList<Integer> a |
random pick = a.get(random index): O(1) |
| A register at the door: name → chair number | HashMap<Integer, Integer> pos |
find a name: O(1) |
| Someone leaves: the person on the last chair moves into the empty chair | swap with the last, then remove the end | no shifting: O(1) |
By hand, removing 20 from a = [10, 20, 30, 40], pos = {10:0, 20:1, 30:2, 40:3}:
possays20is at index 1.- The last element is
40: copy it into index 1, soa = [10, 40, 30, 40]. 40moved:pos[40] = 1.- Remove the last slot (O(1), nothing shifts) and delete
20frompos:a = [10, 40, 30],pos = {10:0, 40:1, 30:2}. getRandompicks index 0, 1 or 2, each with chance 1/3.
Solution in Java
import java.util.*;
public class Main {
static class RandomizedSet {
List<Integer> a = new ArrayList<>();
Map<Integer, Integer> pos = new HashMap<>();
Random rnd = new Random(42);
boolean insert(int x) {
if (pos.containsKey(x)) return false;
pos.put(x, a.size());
a.add(x);
return true;
}
boolean remove(int x) {
Integer i = pos.get(x);
if (i == null) return false;
int last = a.get(a.size() - 1);
a.set(i, last);
pos.put(last, i);
a.remove(a.size() - 1);
pos.remove(x);
return true;
}
int getRandom() {
return a.get(rnd.nextInt(a.size()));
}
}
public static void main(String[] args) {
RandomizedSet s = new RandomizedSet();
System.out.println(s.insert(1) + " " + s.remove(2) + " " + s.insert(2));
System.out.println(s.getRandom() + " " + s.remove(1) + " " + s.insert(2));
System.out.println(s.getRandom());
RandomizedSet t = new RandomizedSet();
t.insert(10); t.insert(20); t.insert(30);
System.out.println(t.remove(30) + " " + t.remove(10) + " " + t.a + " " + t.pos);
RandomizedSet f = new RandomizedSet();
int[] cnt = new int[3];
for (int i = 0; i < 3; i++) f.insert(i);
for (int k = 0; k < 300_000; k++) cnt[f.getRandom()]++;
System.out.println(Arrays.toString(cnt));
}
}
Output (real):
true false true
2 true false
2
true true [20] {20=0}
[99988, 99763, 100249]
Removing 30, the last element itself, works because the map is updated (pos.put(last, i), here 30 → 2) before x is deleted (pos.remove(30)). The other order would leave a stale 30 in the map. Three lakh picks from {0, 1, 2} land close to one lakh each: the draw is fair.
The big test, with the same main as the brute forces:
import java.util.*;
public class Main {
static class RandomizedSet {
List<Integer> a = new ArrayList<>();
Map<Integer, Integer> pos = new HashMap<>();
Random rnd = new Random(42);
boolean insert(int x) {
if (pos.containsKey(x)) return false;
pos.put(x, a.size());
a.add(x);
return true;
}
boolean remove(int x) {
Integer i = pos.get(x);
if (i == null) return false;
int last = a.get(a.size() - 1);
a.set(i, last);
pos.put(last, i);
a.remove(a.size() - 1);
pos.remove(x);
return true;
}
int getRandom() {
return a.get(rnd.nextInt(a.size()));
}
}
public static void main(String[] args) {
RandomizedSet s = new RandomizedSet();
int n = 200_000, left = 0;
long t0 = System.nanoTime(), sum = 0;
for (int i = 0; i < n; i++) if (s.insert(i)) left++;
for (int i = 0; i < n; i++) sum += s.getRandom();
for (int i = 0; i < n; i += 2) if (s.remove(i)) left--;
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println("left " + left + ", " + ms + " ms");
}
}
Output (real, timing varies):
left 100000, 83 ms
A real bug: the moved element's index is not updated
Remove the line pos.put(last, i); and run:
RandomizedSet t = new RandomizedSet();
t.insert(10); t.insert(20); t.insert(30);
System.out.println(t.remove(10) + " " + t.a + " " + t.pos);
System.out.println(t.remove(30) + " " + t.a);
Output (real):
true [30, 20] {20=1, 30=2}
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:100)
at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:106)
at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:302)
at java.base/java.util.Objects.checkIndex(Objects.java:385)
at java.base/java.util.ArrayList.set(ArrayList.java:470)
at Main$RandomizedSet.remove(Main.java:18)
at Main.main(Main.java:31)
After removing 10, 30 sits at index 0 but pos still says 2. Removing 30 then writes to index 2 of a list of length 2.
Problem 2: the LFU cache (LeetCode 460, hard)
Build LFUCache(capacity) with get(key) (the value, or -1) and put(key, value) (add or update). When the cache is full and a new key arrives, evict the least frequently used key; on a tie, the least recently used of them. Both operations in O(1) on average.
| Calls (capacity 2) | Result | Counts after |
|---|---|---|
put(1,1), put(2,2) |
1→1, 2→1 | |
get(1) |
1 |
1→2, 2→1 |
put(3,3) |
evicts 2 (smallest count) | 1→2, 3→1 |
get(2), get(3) |
-1, 3 |
1→2, 3→2 |
put(4,4) |
evicts 1 (tie, 1 was used longest ago) | 3→2, 4→1 |
get(1), get(3), get(4) |
-1, 3, 4 |
Obvious idea: store the count and the last-used time, scan for the victim
import java.util.*;
public class Main {
static class LFUCache {
int cap, time = 0;
Map<Integer, int[]> m = new HashMap<>(); // key -> {value, count, last}
LFUCache(int capacity) { cap = capacity; }
int get(int key) {
int[] e = m.get(key);
if (e == null) return -1;
e[1]++; e[2] = time++;
return e[0];
}
void put(int key, int value) {
if (cap == 0) return;
int[] e = m.get(key);
if (e != null) { e[0] = value; e[1]++; e[2] = time++; return; }
if (m.size() == cap) {
int victim = -1; int[] best = null;
for (Map.Entry<Integer, int[]> x : m.entrySet()) {
int[] v = x.getValue();
if (best == null || v[1] < best[1]
|| (v[1] == best[1] && v[2] < best[2])) {
best = v; victim = x.getKey();
}
}
m.remove(victim);
}
m.put(key, new int[]{value, 1, time++});
}
}
public static void main(String[] args) {
LFUCache c = new LFUCache(2);
c.put(1, 1); c.put(2, 2);
System.out.print(c.get(1) + " ");
c.put(3, 3);
System.out.print(c.get(2) + " " + c.get(3) + " ");
c.put(4, 4);
System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4));
}
}
Output (real):
1 -1 3 -1 3 4
Correct. Now capacity 1 lakh and 4 lakh rounds of "put a new key, get an older one":
import java.util.*;
public class Main {
static class LFUCache {
int cap, time = 0;
Map<Integer, int[]> m = new HashMap<>(); // key -> {value, count, last}
LFUCache(int capacity) { cap = capacity; }
int get(int key) {
int[] e = m.get(key);
if (e == null) return -1;
e[1]++; e[2] = time++;
return e[0];
}
void put(int key, int value) {
if (cap == 0) return;
int[] e = m.get(key);
if (e != null) { e[0] = value; e[1]++; e[2] = time++; return; }
if (m.size() == cap) {
int victim = -1; int[] best = null;
for (Map.Entry<Integer, int[]> x : m.entrySet()) {
int[] v = x.getValue();
if (best == null || v[1] < best[1]
|| (v[1] == best[1] && v[2] < best[2])) {
best = v; victim = x.getKey();
}
}
m.remove(victim);
}
m.put(key, new int[]{value, 1, time++});
}
}
public static void main(String[] args) {
int cap = 100_000, ops = 400_000;
LFUCache c = new LFUCache(cap);
long t0 = System.nanoTime(), hits = 0;
for (int i = 0; i < ops; i++) {
c.put(i, i);
if (c.get(i / 2) != -1) hits++;
}
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(hits + " hits, " + ms + " ms");
}
}
Output (real): Time Limit Exceeded (nothing printed after 25 seconds). About 3 lakh evictions, each scanning 1 lakh keys: 3 × 10¹⁰ steps. A heap ordered by (count, time) would make each eviction O(log n), but the problem asks for O(1).
The key insight: group the keys by their count
| At the sweet shop | In Java |
|---|---|
| What is on the shelf | val: key → value |
| A tally per sweet | freq: key → count |
| One queue per tally, oldest at the front | bucket: count → LinkedHashSet of keys |
| The lowest tally that has a sweet | minFreq |
- Using a stored key (
touch): move it frombucket[f]to the end ofbucket[f + 1]. Ifbucket[f]became empty andf == minFreq, thenminFreq++. - Evicting: the victim is the first key in
bucket[minFreq]: the smallest count, and among those, the oldest. The tie is broken for free. - A new key always has count 1, so after inserting it,
minFreq = 1.
The example, bucket by bucket (capacity 2):
| Step | count 1 | count 2 | minFreq |
|---|---|---|---|
put(1), put(2) |
1, 2 | 1 | |
get(1) |
2 | 1 | 1 |
put(3): victim = first of bucket 1 = 2 |
3 | 1 | 1 |
get(3): bucket 1 empties |
1, 3 | 2 | |
put(4): victim = first of bucket 2 = 1 |
4 | 3 | 1 |
Solution in Java
import java.util.*;
public class Main {
static class LFUCache {
int cap, minFreq = 0;
Map<Integer, Integer> val = new HashMap<>(), freq = new HashMap<>();
Map<Integer, LinkedHashSet<Integer>> bucket = new HashMap<>();
LFUCache(int capacity) { cap = capacity; }
void touch(int key) {
int f = freq.get(key);
freq.put(key, f + 1);
bucket.get(f).remove(key);
if (bucket.get(f).isEmpty() && minFreq == f) minFreq++;
bucket.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
}
int get(int key) {
if (!val.containsKey(key)) return -1;
touch(key);
return val.get(key);
}
void put(int key, int value) {
if (cap == 0) return;
if (val.containsKey(key)) {
val.put(key, value);
touch(key);
return;
}
if (val.size() == cap) {
int victim = bucket.get(minFreq).iterator().next();
bucket.get(minFreq).remove(victim);
val.remove(victim);
freq.remove(victim);
}
val.put(key, value);
freq.put(key, 1);
bucket.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minFreq = 1;
}
}
public static void main(String[] args) {
LFUCache c = new LFUCache(2);
c.put(1, 1); c.put(2, 2);
System.out.print(c.get(1) + " ");
c.put(3, 3);
System.out.print(c.get(2) + " " + c.get(3) + " ");
c.put(4, 4);
System.out.println(c.get(1) + " " + c.get(3) + " " + c.get(4));
LFUCache d = new LFUCache(1);
d.put(1, 10); d.put(2, 20);
LFUCache z = new LFUCache(0);
z.put(1, 1);
LFUCache u = new LFUCache(2);
u.put(1, 1); u.put(2, 2); u.put(1, 100); u.put(3, 3);
System.out.println(d.get(1) + " " + d.get(2) + " | " + z.get(1));
System.out.println(u.get(1) + " " + u.get(2) + " " + u.get(3));
}
}
Output (real):
1 -1 3 -1 3 4
-1 20 | -1
100 -1 3
Capacity 1: putting 2 evicts 1. Capacity 0 stores nothing. Updating key 1 raises its count to 2, so put(3, 3) evicts 2.
The big test:
import java.util.*;
public class Main {
static class LFUCache {
int cap, minFreq = 0;
Map<Integer, Integer> val = new HashMap<>(), freq = new HashMap<>();
Map<Integer, LinkedHashSet<Integer>> bucket = new HashMap<>();
LFUCache(int capacity) { cap = capacity; }
void touch(int key) {
int f = freq.get(key);
freq.put(key, f + 1);
bucket.get(f).remove(key);
if (bucket.get(f).isEmpty() && minFreq == f) minFreq++;
bucket.computeIfAbsent(f + 1, k -> new LinkedHashSet<>()).add(key);
}
int get(int key) {
if (!val.containsKey(key)) return -1;
touch(key);
return val.get(key);
}
void put(int key, int value) {
if (cap == 0) return;
if (val.containsKey(key)) {
val.put(key, value);
touch(key);
return;
}
if (val.size() == cap) {
int victim = bucket.get(minFreq).iterator().next();
bucket.get(minFreq).remove(victim);
val.remove(victim);
freq.remove(victim);
}
val.put(key, value);
freq.put(key, 1);
bucket.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
minFreq = 1;
}
}
public static void main(String[] args) {
int cap = 100_000, ops = 400_000;
LFUCache c = new LFUCache(cap);
long t0 = System.nanoTime(), hits = 0;
for (int i = 0; i < ops; i++) {
c.put(i, i);
if (c.get(i / 2) != -1) hits++;
}
long ms = (System.nanoTime() - t0) / 1000000;
System.out.println(hits + " hits, " + ms + " ms");
}
}
Output (real, timing varies):
100000 hits, 376 ms
(The scanning version gives the same answers: on a smaller run with capacity 1,000 and 4,000 rounds both print 1000 hits.)
A real bug: minFreq not moved up
Remove the line if (bucket.get(f).isEmpty() && minFreq == f) minFreq++; and run the example:
1 -1 3 Exception in thread "main" java.util.NoSuchElementException
at java.base/java.util.LinkedHashMap$LinkedHashIterator.nextNode(LinkedHashMap.java:1025)
at java.base/java.util.LinkedHashMap$LinkedKeyIterator.next(LinkedHashMap.java:1046)
at Main$LFUCache.put(Main.java:28)
at Main.main(Main.java:45)
After get(3), bucket 1 is empty but minFreq is still 1, so put(4, 4) asks an empty set for its first element.
The same solutions in C++
#include <bits/stdc++.h>
using namespace std;
// LeetCode 380: array + map value -> index; remove = swap with the last.
class RandomizedSet {
vector<int> a;
unordered_map<int, int> pos;
mt19937 rng{42};
public:
bool insert(int x) {
if (pos.count(x)) return false;
pos[x] = a.size();
a.push_back(x);
return true;
}
bool remove(int x) {
auto it = pos.find(x);
if (it == pos.end()) return false;
int i = it->second, last = a.back();
a[i] = last;
pos[last] = i;
a.pop_back();
pos.erase(x);
return true;
}
int getRandom() { return a[rng() % a.size()]; }
};
// LeetCode 460: val, freq, one list per count (oldest at the front), minFreq.
class LFUCache {
int cap, minFreq = 0;
unordered_map<int, int> val, freq;
unordered_map<int, list<int>> bucket; // count -> keys, oldest first
unordered_map<int, list<int>::iterator> where; // key -> its place in its list
void touch(int key) {
int f = freq[key]++;
bucket[f].erase(where[key]);
if (bucket[f].empty() && minFreq == f) minFreq++;
bucket[f + 1].push_back(key);
where[key] = prev(bucket[f + 1].end());
}
public:
LFUCache(int capacity) : cap(capacity) {}
int get(int key) {
if (!val.count(key)) return -1;
touch(key);
return val[key];
}
void put(int key, int value) {
if (cap == 0) return;
if (val.count(key)) { val[key] = value; touch(key); return; }
if ((int)val.size() == cap) {
int victim = bucket[minFreq].front();
bucket[minFreq].pop_front();
val.erase(victim); freq.erase(victim); where.erase(victim);
}
val[key] = value; freq[key] = 1;
bucket[1].push_back(key);
where[key] = prev(bucket[1].end());
minFreq = 1;
}
};
int main() {
RandomizedSet s;
cout << boolalpha << s.insert(1) << " " << s.remove(2) << " " << s.insert(2) << "\n";
int r = s.getRandom();
cout << (r == 1 || r == 2) << " " << s.remove(1) << " " << s.insert(2) << "\n";
cout << s.getRandom() << "\n";
RandomizedSet f; int cnt[3] = {0, 0, 0};
for (int i = 0; i < 3; i++) f.insert(i);
for (int k = 0; k < 300000; k++) cnt[f.getRandom()]++;
cout << cnt[0] << " " << cnt[1] << " " << cnt[2] << "\n";
LFUCache c(2);
c.put(1, 1); c.put(2, 2);
cout << c.get(1) << " ";
c.put(3, 3);
cout << c.get(2) << " " << c.get(3) << " ";
c.put(4, 4);
cout << c.get(1) << " " << c.get(3) << " " << c.get(4) << "\n";
LFUCache u(2);
u.put(1, 1); u.put(2, 2); u.put(1, 100); u.put(3, 3);
cout << u.get(1) << " " << u.get(2) << " " << u.get(3) << "\n";
LFUCache big(100000); long long hits = 0;
for (int i = 0; i < 400000; i++) { big.put(i, i); if (big.get(i / 2) != -1) hits++; }
cout << hits << " hits\n";
}
Output (real, g++ -O2):
true false true
true true false
2
99978 99963 100059
1 -1 3 -1 3 4
100 -1 3
100000 hits
In C++ a std::list per count plus a map from each key to its iterator gives O(1) removal from the middle of a bucket, which is what LinkedHashSet does for us in Java.
The same solutions in Python
import random
from collections import defaultdict, OrderedDict
class RandomizedSet: # LeetCode 380
def __init__(self):
self.a, self.pos = [], {}
self.rnd = random.Random(42)
def insert(self, x):
if x in self.pos:
return False
self.pos[x] = len(self.a)
self.a.append(x)
return True
def remove(self, x):
if x not in self.pos:
return False
i, last = self.pos[x], self.a[-1]
self.a[i] = last
self.pos[last] = i
self.a.pop()
del self.pos[x]
return True
def getRandom(self):
return self.a[self.rnd.randrange(len(self.a))]
class LFUCache: # LeetCode 460
def __init__(self, capacity):
self.cap, self.min_freq = capacity, 0
self.val, self.freq = {}, {}
self.bucket = defaultdict(OrderedDict) # count -> keys, oldest first
def _touch(self, key):
f = self.freq[key]
self.freq[key] = f + 1
del self.bucket[f][key]
if not self.bucket[f] and self.min_freq == f:
self.min_freq += 1
self.bucket[f + 1][key] = None
def get(self, key):
if key not in self.val:
return -1
self._touch(key)
return self.val[key]
def put(self, key, value):
if self.cap == 0:
return
if key in self.val:
self.val[key] = value
self._touch(key)
return
if len(self.val) == self.cap:
victim, _ = self.bucket[self.min_freq].popitem(last=False)
del self.val[victim], self.freq[victim]
self.val[key], self.freq[key] = value, 1
self.bucket[1][key] = None
self.min_freq = 1
s = RandomizedSet()
print(s.insert(1), s.remove(2), s.insert(2))
r = s.getRandom()
print(r in (1, 2), s.remove(1), s.insert(2))
print(s.getRandom())
f = RandomizedSet()
for i in range(3):
f.insert(i)
cnt = [0, 0, 0]
for _ in range(300_000):
cnt[f.getRandom()] += 1
print(cnt)
c = LFUCache(2)
c.put(1, 1); c.put(2, 2)
out = [c.get(1)]
c.put(3, 3)
out += [c.get(2), c.get(3)]
c.put(4, 4)
out += [c.get(1), c.get(3), c.get(4)]
print(*out)
u = LFUCache(2)
u.put(1, 1); u.put(2, 2); u.put(1, 100); u.put(3, 3)
print(u.get(1), u.get(2), u.get(3))
big, hits = LFUCache(100_000), 0
for i in range(400_000):
big.put(i, i)
if big.get(i // 2) != -1:
hits += 1
print(hits, "hits")
Output (real):
True False True
True True False
2
[100219, 99799, 99982]
1 -1 3 -1 3 4
100 -1 3
100000 hits
OrderedDict keeps insertion order and popitem(last=False) removes the oldest key, so it plays the role of LinkedHashSet.
Complexity
| Solution | insert / put | remove | getRandom / get | Space |
|---|---|---|---|---|
| ArrayList set | O(n) | O(n) | O(1) | O(n) |
| HashSet set | O(1) avg | O(1) avg | O(n) | O(n) |
| Array + map (swap with last) | O(1) avg | O(1) avg | O(1) | O(n) |
| LFU, scan for the victim | O(capacity) | O(1) avg | O(capacity) | |
| LFU with a heap | O(log capacity) | O(log capacity) | O(capacity) | |
| LFU with buckets + minFreq | O(1) avg | O(1) avg | O(capacity) |
Common mistakes
| Mistake | What you see (real) | Why | Fix |
|---|---|---|---|
ArrayList contains / remove(i) |
Time Limit Exceeded | O(n) scan and shift | map value → index, swap with the last |
HashSet + walk for getRandom |
Time Limit Exceeded | a set has no index | an array for the random pick |
| Moved element's index not updated | IndexOutOfBoundsException: Index 2 out of bounds for length 2 |
stale index in pos |
pos.put(last, i) |
pos.remove(x) before pos.put(last, i) |
removing the last element leaves it in pos |
the put re-adds it | update first, delete x last |
| LFU: scan every key for the victim | Time Limit Exceeded | O(capacity) per put | buckets + minFreq |
minFreq not moved up when its bucket empties |
java.util.NoSuchElementException |
empty minimum bucket | if (empty && minFreq == f) minFreq++ |
minFreq not reset to 1 for a new key |
the wrong key is evicted | new keys have count 1 | minFreq = 1 after every new key |
Forgetting capacity == 0 |
a key is stored in a cache that must stay empty | if (cap == 0) return; |
Mini project: a lucky-draw app with a shelf
Write a small console program for a mela stall: commands join <name>, leave <name>, draw (a fair random winner, using RandomizedSet over name ids), and ask <sweet> (counts customer requests in an LFUCache of capacity 3 that holds the sweets on the front shelf, printing which sweet went back inside). Print the shelf after every command.
Practice
1. Insert Delete GetRandom O(1), duplicates allowed (LeetCode 381): the map stores a set of indexes per value.
2. All O'one Data Structure (LeetCode 432): inc, dec, getMaxKey, getMinKey. The simple version below groups keys by count in a TreeMap (O(log n)); the O(1) version links the count buckets in a doubly linked list, the same bucket idea as LFU.
3. Who is evicted? Capacity 2: put(1,1), put(2,2), get(1), get(2), put(3,3).
Solutions
import java.util.*;
public class Main {
// 1. LeetCode 381: duplicates allowed. Map value -> SET of indexes.
static class RandomizedCollection {
List<Integer> a = new ArrayList<>();
Map<Integer, Set<Integer>> idx = new HashMap<>();
Random rnd = new Random(42);
boolean insert(int x) {
Set<Integer> s = idx.computeIfAbsent(x, k -> new HashSet<>());
s.add(a.size());
a.add(x);
return s.size() == 1;
}
boolean remove(int x) {
Set<Integer> s = idx.get(x);
if (s == null || s.isEmpty()) return false;
int i = s.iterator().next(), lastI = a.size() - 1, last = a.get(lastI);
s.remove(i);
a.set(i, last);
Set<Integer> ls = idx.get(last);
ls.add(i);
ls.remove(lastI);
a.remove(lastI);
if (s.isEmpty()) idx.remove(x);
return true;
}
int getRandom() { return a.get(rnd.nextInt(a.size())); }
}
// 2. LeetCode 432 (All O'one), simple version: count map + TreeMap of buckets, O(log n) per call.
static class AllOne {
Map<String, Integer> cnt = new HashMap<>();
TreeMap<Integer, Set<String>> byCount = new TreeMap<>();
void move(String k, int from, int to) {
if (from > 0) { byCount.get(from).remove(k); if (byCount.get(from).isEmpty()) byCount.remove(from); }
if (to > 0) { byCount.computeIfAbsent(to, x -> new LinkedHashSet<>()).add(k); cnt.put(k, to); }
else cnt.remove(k);
}
void inc(String k) { int c = cnt.getOrDefault(k, 0); move(k, c, c + 1); }
void dec(String k) { int c = cnt.get(k); move(k, c, c - 1); }
String getMaxKey() { return byCount.isEmpty() ? "" : byCount.lastEntry().getValue().iterator().next(); }
String getMinKey() { return byCount.isEmpty() ? "" : byCount.firstEntry().getValue().iterator().next(); }
}
public static void main(String[] args) {
RandomizedCollection rc = new RandomizedCollection();
System.out.println(rc.insert(1) + " " + rc.insert(1) + " " + rc.insert(2));
System.out.println(rc.remove(1) + " " + rc.a + " " + rc.remove(1) + " " + rc.remove(1) + " " + rc.a);
AllOne ao = new AllOne();
ao.inc("chai"); ao.inc("chai"); ao.inc("lassi");
System.out.println(ao.getMaxKey() + " " + ao.getMinKey());
ao.inc("lassi"); ao.inc("lassi"); ao.dec("chai");
System.out.println(ao.getMaxKey() + " " + ao.getMinKey());
}
}
Output (real):
true false true
true [2, 1] true false [2]
chai lassi
lassi chai
3: key 1 is evicted. Both keys have count 2; key 1 was used longest ago. Running it with the LFU solution and printing c.get(1) + " " + c.get(2) + " " + c.get(3) gives (real):
-1 2 3
Quick quiz
Capacity 2: put(1,1), put(2,2), get(1), get(2), put(3,3). Who is evicted? A) key 1 B) key 2 C) key 3 is not stored D) both 1 and 2
Answer
A. Keys 1 and 2 both have a count of 2, a tie. Key 1 was used longest ago, so it is first in bucket 2 and is evicted.
Interview questions
- Why can't a HashSet alone give O(1)
getRandom? It has no index; picking the k-th element means walking the set. - Why swap with the last element instead of removing from the middle? Removing from the end of an array shifts nothing, so it's O(1); only one element moves, and its index is updated in the map.
- Is
getRandomreally uniform after many removals? Yes: the array never has gaps, so each of thenslots is picked with chance1/n. - What changes when duplicates are allowed (LeetCode 381)? The map stores a set of indexes per value; remove one index and fix the moved element's set.
- LRU vs LFU? LRU evicts the item used longest ago; LFU evicts the item used the fewest times, with LRU as the tie-break.
- Why does a new key reset
minFreqto 1? A new key has count 1, the smallest possible count. - When does
minFreqgo up? Only intouch, when the minimum bucket empties; it rises by exactly 1, because the touched key just moved tof + 1. - What would a heap-based LFU cost? O(log capacity) per call; fine in practice, but not O(1).
Glossary
| Term | Meaning |
|---|---|
| Design problem | Build a data structure with several operations |
| O(1) / constant time | Time doesn't grow with n |
| Average O(1) | O(1) per call on average; rare slow calls allowed |
| Uniformly random | Each element with chance 1/n |
| ArrayList | Java's growable array |
| HashSet / HashMap | Hash-based set / key-value map, O(1) average operations |
| Seed | Start value of a random generator; same seed, same numbers |
| Cache | A small fast store with a capacity |
| Evict | Remove an item from a full cache |
| LRU | Least recently used |
| LFU | Least frequently used |
| Frequency / use count | How many times a key was used |
| Bucket | All keys with the same count |
| LinkedHashSet | A hash set that remembers insertion order |
| computeIfAbsent | Get a map value, creating it if missing |
| minFreq | The smallest count that has a key |
| Heap | Keeps the smallest item on top, O(log n) updates |
Summary
- A randomized set = an array (random pick) + a map value → index (lookup).
- Remove by moving the last element into the hole, updating its index, then dropping the end.
- The LFU cache =
val,freq, oneLinkedHashSetbucket per count, andminFreq. - The victim is the first key in
bucket[minFreq]; the order inside the bucket breaks ties. minFreqgoes up when its bucket empties intouch, and resets to 1 for every new key.- Both designs are O(1) average per operation, O(n) / O(capacity) space.
- Next episode: hard mix 1: first missing positive, longest valid parentheses.