SyntaxPilot
Courses/DSA and Coding Problems/Lesson 86
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

DSA and Coding Problems · Lesson 86 of 90

Design: insert-delete-getRandom O(1) and the LFU cache (hard)

queued

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); contains and indexOf look 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, get and put are 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 capacity items.
  • 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 get and every put of 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, and remove(x) is still O(1).
  • computeIfAbsent(k, f): returns the value for key k, creating it with f first 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}:

  1. pos says 20 is at index 1.
  2. The last element is 40: copy it into index 1, so a = [10, 40, 30, 40].
  3. 40 moved: pos[40] = 1.
  4. Remove the last slot (O(1), nothing shifts) and delete 20 from pos: a = [10, 40, 30], pos = {10:0, 40:1, 30:2}.
  5. getRandom picks 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 from bucket[f] to the end of bucket[f + 1]. If bucket[f] became empty and f == minFreq, then minFreq++.
  • 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

  1. Why can't a HashSet alone give O(1) getRandom? It has no index; picking the k-th element means walking the set.
  2. 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.
  3. Is getRandom really uniform after many removals? Yes: the array never has gaps, so each of the n slots is picked with chance 1/n.
  4. 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.
  5. LRU vs LFU? LRU evicts the item used longest ago; LFU evicts the item used the fewest times, with LRU as the tie-break.
  6. Why does a new key reset minFreq to 1? A new key has count 1, the smallest possible count.
  7. When does minFreq go up? Only in touch, when the minimum bucket empties; it rises by exactly 1, because the touched key just moved to f + 1.
  8. 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, one LinkedHashSet bucket per count, and minFreq.
  • The victim is the first key in bucket[minFreq]; the order inside the bucket breaks ties.
  • minFreq goes up when its bucket empties in touch, 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.