[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":85,"_72":86,"_35":87},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":52,"_64":65,"_66":67,"_68":69,"_70":71},"id",48,"title","Probabilistic Data Structures","slug","algorithms-part-21-probabilistic-algorithms","excerpt","Distinguish Las Vegas vs Monte Carlo algorithms. Implement Bloom filters, Count-Min Sketch, and HyperLogLog for space-efficient streaming data.","# Part 21: Probabilistic & Approximation Algorithms - Trading Exactness for Efficiency\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 35 minutes |\n| Prerequisites | Part 1 (Algorithm Analysis), Basic probability |\n| Key Concepts | Randomized Algorithms, Bloom Filters, HyperLogLog, Approximation |\n| Difficulty | ⭐⭐⭐ (Intermediate) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ PROBABILISTIC ALGORITHMS │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ WHY RANDOMIZATION? │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ • Simpler algorithms │ │\n│ │ • Better average-case performance │ │\n│ │ • Avoid worst-case inputs │ │\n│ │ • Sublinear space for streaming │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ TWO TYPES │\n│ ┌─────────────────────┐ ┌─────────────────────┐ │\n│ │ LAS VEGAS │ │ MONTE CARLO │ │\n│ │ ─────────────────── │ │ ─────────────────── │ │\n│ │ Always correct │ │ Usually correct │ │\n│ │ Random running time │ │ Fixed running time │ │\n│ │ Example: QuickSort │ │ Example: Miller-Rabin│ │\n│ │ with random pivot │ │ primality test │ │\n│ └─────────────────────┘ └─────────────────────┘ │\n│ │\n│ SKETCHING DATA STRUCTURES │\n│ ┌─────────────────┐ ┌─────────────────┐ ┌──────────────┐ │\n│ │ Bloom Filter │ │ Count-Min Sketch│ │ HyperLogLog │ │\n│ │ ─────────────── │ │ ─────────────── │ │ ──────────── │ │\n│ │ Set membership │ │ Frequency est. │ │ Cardinality │ │\n│ │ No false neg │ │ May overcount │ │ estimation │ │\n│ └─────────────────┘ └─────────────────┘ └──────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Distinguish algorithm types**: Las Vegas vs Monte Carlo\n2. **Implement Bloom filters**: Space-efficient set membership\n3. **Use Count-Min Sketch**: Frequency estimation in streams\n4. **Apply HyperLogLog**: Count distinct elements in O(1) space\n5. **Design approximation algorithms**: Trade accuracy for speed\n\n---\n\n## 🔥 Production Story: Counting Unique Visitors at Scale\n\nA social media platform needed to count unique daily visitors - but with 500 million users, storing all IDs was impossible.\n\n### The Problem\n\n```java\n// ❌ Exact counting: O(n) space\npublic class NaiveUniqueCounter {\n private Set seen = new HashSet<>();\n\n public void visit(long userId) {\n seen.add(userId);\n }\n\n public long getUniqueCount() {\n return seen.size();\n }\n\n // 500M users × 8 bytes = 4GB RAM PER COUNTER\n // Need counters per page, per feature, per country...\n // IMPOSSIBLE\n}\n```\n\n### The Solution: HyperLogLog\n\n```java\n// ✅ HyperLogLog: O(1) space, ~2% error\npublic class HyperLogLogCounter {\n private static final int P = 14; // Precision parameter\n private static final int M = 1 << P; // 16384 registers\n private byte[] registers = new byte[M];\n\n public void visit(long userId) {\n long hash = hash64(userId);\n int index = (int) (hash >>> (64 - P)); // First P bits for bucket\n // Count leading zeros in remaining bits (positions 0 to 63-P)\n long w = hash << P; // Shift out the index bits\n int rank = (w == 0) ? (64 - P + 1) : (Long.numberOfLeadingZeros(w) + 1);\n registers[index] = (byte) Math.max(registers[index], rank);\n }\n\n public long estimateCardinality() {\n double sum = 0;\n int zeros = 0;\n\n for (byte r : registers) {\n sum += 1.0 / (1L << r);\n if (r == 0) zeros++;\n }\n\n double estimate = ALPHA_M * M * M / sum;\n\n // Small range correction\n if (estimate <= 2.5 * M && zeros > 0) {\n estimate = M * Math.log((double) M / zeros);\n }\n\n return Math.round(estimate);\n }\n\n // Memory: 16KB instead of 4GB\n // Error: ~2%\n}\n```\n\n### The Impact\n\n| Metric | HashSet | HyperLogLog |\n|--------|---------|-------------|\n| Memory per counter | 4GB | 16KB |\n| Counters possible | 1 | 250,000+ |\n| Error | 0% | ~2% |\n| Mergeable | No | Yes |\n\n---\n\n## 🧠 Mental Model: The Coin Flip Experiment\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ HYPERLOGLOG INTUITION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Thought experiment: Flip coins until you get heads │\n│ │\n│ 1 flip: H (50% probability) │\n│ 2 flips: TH (25% probability) │\n│ 3 flips: TTH (12.5% probability) │\n│ k flips: T...TH (1/2^k probability) │\n│ │\n│ If you observe k flips, ~2^k unique experiments happened │\n│ │\n│ HyperLogLog: │\n│ 1. Hash each element → random bit string │\n│ 2. Count leading zeros = \"coin flips until heads\" │\n│ 3. Maximum leading zeros ≈ log₂(n) │\n│ │\n│ Example: │\n│ Element → Hash → Leading zeros │\n│ \"alice\" → 0001... → 3 zeros │\n│ \"bob\" → 0000001... → 6 zeros ← Maximum! │\n│ \"carol\" → 001... → 2 zeros │\n│ │\n│ Max leading zeros = 6 → Estimate ~2^6 = 64 unique elements │\n│ │\n│ Problem: High variance! Solution: Use M registers, average. │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Bloom Filters\n\n### The Concept\n\nA Bloom filter answers \"Is X in the set?\" with:\n- **No** → Definitely not in set\n- **Yes** → Probably in set (false positives possible)\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ BLOOM FILTER │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Bit array: [0][0][0][0][0][0][0][0][0][0] (m bits) │\n│ 0 1 2 3 4 5 6 7 8 9 │\n│ │\n│ Add \"apple\" (k=3 hash functions): │\n│ h1(\"apple\") = 2, h2(\"apple\") = 5, h3(\"apple\") = 8 │\n│ │\n│ [0][0][1][0][0][1][0][0][1][0] │\n│ ↑ ↑ ↑ │\n│ │\n│ Add \"banana\": │\n│ h1(\"banana\") = 1, h2(\"banana\") = 5, h3(\"banana\") = 9 │\n│ │\n│ [0][1][1][0][0][1][0][0][1][1] │\n│ ↑ (already 1) ↑ │\n│ │\n│ Query \"cherry\": │\n│ h1(\"cherry\") = 2, h2(\"cherry\") = 7, h3(\"cherry\") = 9 │\n│ Check bits 2, 7, 9: [1][0][1] → 0 found → NOT IN SET │\n│ │\n│ Query \"date\": │\n│ h1(\"date\") = 1, h2(\"date\") = 5, h3(\"date\") = 8 │\n│ Check bits 1, 5, 8: [1][1][1] → All 1 → PROBABLY IN SET │\n│ (false positive! \"date\" was never added) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Implementation\n\n```java\npublic class BloomFilter {\n private final BitSet bits;\n private final int numBits;\n private final int numHashes;\n\n public BloomFilter(int expectedElements, double falsePositiveRate) {\n // Optimal parameters\n this.numBits = optimalNumBits(expectedElements, falsePositiveRate);\n this.numHashes = optimalNumHashes(expectedElements, numBits);\n this.bits = new BitSet(numBits);\n }\n\n private int optimalNumBits(int n, double p) {\n return (int) Math.ceil(-n * Math.log(p) / (Math.log(2) * Math.log(2)));\n }\n\n private int optimalNumHashes(int n, int m) {\n return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));\n }\n\n public void add(T element) {\n long hash64 = hash(element);\n int hash1 = (int) hash64;\n int hash2 = (int) (hash64 >>> 32);\n\n for (int i = 0; i < numHashes; i++) {\n int combinedHash = hash1 + i * hash2;\n int index = Math.abs(combinedHash % numBits);\n bits.set(index);\n }\n }\n\n public boolean mightContain(T element) {\n long hash64 = hash(element);\n int hash1 = (int) hash64;\n int hash2 = (int) (hash64 >>> 32);\n\n for (int i = 0; i < numHashes; i++) {\n int combinedHash = hash1 + i * hash2;\n int index = Math.abs(combinedHash % numBits);\n if (!bits.get(index)) {\n return false; // Definitely not in set\n }\n }\n return true; // Probably in set\n }\n\n private long hash(T element) {\n // Use a good hash function like MurmurHash3\n byte[] bytes = element.toString().getBytes();\n return MurmurHash3.hash64(bytes);\n }\n\n // Merge two Bloom filters\n public void merge(BloomFilter other) {\n if (this.numBits != other.numBits || this.numHashes != other.numHashes) {\n throw new IllegalArgumentException(\"Incompatible filters\");\n }\n this.bits.or(other.bits);\n }\n}\n```\n\n### Use Cases\n\n```java\npublic class BloomFilterUseCases {\n // 1. Cache lookup optimization\n public class CacheWithBloom {\n private BloomFilter bloom = new BloomFilter<>(1_000_000, 0.01);\n private Map cache = new HashMap<>();\n\n public Object get(String key) {\n // Quick bloom check before expensive cache lookup\n if (!bloom.mightContain(key)) {\n return null; // Definitely not in cache\n }\n return cache.get(key); // Might be in cache\n }\n\n public void put(String key, Object value) {\n bloom.add(key);\n cache.put(key, value);\n }\n }\n\n // 2. Duplicate detection in streams\n public class DuplicateDetector {\n private BloomFilter seen = new BloomFilter<>(10_000_000, 0.001);\n\n public boolean isProbablyNew(String item) {\n if (seen.mightContain(item)) {\n return false; // Probably seen before\n }\n seen.add(item);\n return true; // Definitely new\n }\n }\n\n // 3. Database query optimization\n public class DatabaseOptimizer {\n // Each table has Bloom filter of primary keys\n private Map> tableFilters;\n\n public List findTablesToQuery(Long id) {\n List candidates = new ArrayList<>();\n for (var entry : tableFilters.entrySet()) {\n if (entry.getValue().mightContain(id)) {\n candidates.add(entry.getKey());\n }\n }\n return candidates; // Only query these tables\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Count-Min Sketch\n\n### The Concept\n\nEstimate frequency of elements in a stream with limited memory.\n\n```java\npublic class CountMinSketch {\n private final int width;\n private final int depth;\n private final int[][] table;\n private final long[] hashA;\n private final long[] hashB;\n\n // depth = number of hash functions\n // width = size of each row\n // Error: ε = e / width\n // Probability of error > ε: δ = 1 / e^depth\n\n public CountMinSketch(double epsilon, double delta) {\n this.width = (int) Math.ceil(Math.E / epsilon);\n this.depth = (int) Math.ceil(Math.log(1 / delta));\n this.table = new int[depth][width];\n\n // Initialize hash function parameters\n Random rand = new Random(42);\n hashA = new long[depth];\n hashB = new long[depth];\n for (int i = 0; i < depth; i++) {\n hashA[i] = rand.nextLong();\n hashB[i] = rand.nextLong();\n }\n }\n\n public void add(long item) {\n add(item, 1);\n }\n\n public void add(long item, int count) {\n for (int i = 0; i < depth; i++) {\n int index = hash(item, i);\n table[i][index] += count;\n }\n }\n\n public int estimateCount(long item) {\n int min = Integer.MAX_VALUE;\n for (int i = 0; i < depth; i++) {\n int index = hash(item, i);\n min = Math.min(min, table[i][index]);\n }\n return min; // Minimum is closest to true count\n }\n\n private int hash(long item, int i) {\n long hash = hashA[i] * item + hashB[i];\n return Math.abs((int) (hash % width));\n }\n\n // Merge two sketches\n public void merge(CountMinSketch other) {\n for (int i = 0; i < depth; i++) {\n for (int j = 0; j < width; j++) {\n table[i][j] += other.table[i][j];\n }\n }\n }\n}\n```\n\n### Visualization\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ COUNT-MIN SKETCH │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Add \"apple\" (appears 3 times): │\n│ │\n│ Row 0: h0(\"apple\")=2 [0][0][3][0][0][0] │\n│ Row 1: h1(\"apple\")=5 [0][0][0][0][0][3] │\n│ Row 2: h2(\"apple\")=1 [0][3][0][0][0][0] │\n│ │\n│ Add \"banana\" (appears 2 times, collides with apple in row 0): │\n│ │\n│ Row 0: h0(\"banana\")=2 [0][0][5][0][0][0] ← Collision! │\n│ Row 1: h1(\"banana\")=3 [0][0][0][2][0][3] │\n│ Row 2: h2(\"banana\")=4 [0][3][0][0][2][0] │\n│ │\n│ Query \"apple\": │\n│ Row 0: table[0][2] = 5 │\n│ Row 1: table[1][5] = 3 │\n│ Row 2: table[2][1] = 3 │\n│ Estimate = min(5, 3, 3) = 3 ✓ (correct!) │\n│ │\n│ Query \"banana\": │\n│ Row 0: table[0][2] = 5 ← Overestimate due to collision │\n│ Row 1: table[1][3] = 2 │\n│ Row 2: table[2][4] = 2 │\n│ Estimate = min(5, 2, 2) = 2 ✓ (correct!) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n### Use Cases\n\n```java\npublic class CountMinSketchUseCases {\n // 1. Finding heavy hitters (frequent items)\n public class HeavyHittersFinder {\n private CountMinSketch cms = new CountMinSketch(0.001, 0.01);\n private int totalCount = 0;\n private double threshold = 0.01; // 1% of total\n\n public void process(long item) {\n cms.add(item);\n totalCount++;\n }\n\n public boolean isHeavyHitter(long item) {\n return cms.estimateCount(item) >= threshold * totalCount;\n }\n }\n\n // 2. Rate limiting\n public class RateLimiter {\n private CountMinSketch minuteCounts = new CountMinSketch(0.01, 0.001);\n private int maxRequestsPerMinute = 100;\n\n public boolean allowRequest(long userId) {\n int count = minuteCounts.estimateCount(userId);\n if (count >= maxRequestsPerMinute) {\n return false; // Rate limit exceeded\n }\n minuteCounts.add(userId);\n return true;\n }\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: HyperLogLog\n\n### Implementation\n\n```java\npublic class HyperLogLog {\n private static final int P = 14; // Precision (4 to 16)\n private static final int M = 1 << P; // Number of registers\n private static final double ALPHA;\n\n static {\n // Alpha constant for bias correction\n switch (P) {\n case 4: ALPHA = 0.673; break;\n case 5: ALPHA = 0.697; break;\n case 6: ALPHA = 0.709; break;\n default: ALPHA = 0.7213 / (1 + 1.079 / M);\n }\n }\n\n private byte[] registers = new byte[M];\n\n public void add(Object element) {\n long hash = hash64(element);\n\n // First P bits determine register index\n int index = (int) (hash >>> (64 - P));\n\n // Remaining bits: count leading zeros + 1\n long w = hash << P;\n int rank = Long.numberOfLeadingZeros(w) + 1;\n\n // Update register with max\n if (rank > registers[index]) {\n registers[index] = (byte) rank;\n }\n }\n\n public long cardinality() {\n // Harmonic mean of 2^(-register)\n double sum = 0;\n int zeros = 0;\n\n for (byte r : registers) {\n sum += Math.pow(2, -r);\n if (r == 0) zeros++;\n }\n\n double estimate = ALPHA * M * M / sum;\n\n // Small range correction (linear counting)\n if (estimate <= 2.5 * M && zeros > 0) {\n return Math.round(M * Math.log((double) M / zeros));\n }\n\n // Large range correction (for hash collisions)\n double pow32 = Math.pow(2, 32);\n if (estimate > pow32 / 30) {\n return Math.round(-pow32 * Math.log(1 - estimate / pow32));\n }\n\n return Math.round(estimate);\n }\n\n // Merge two HyperLogLog counters\n public void merge(HyperLogLog other) {\n for (int i = 0; i < M; i++) {\n registers[i] = (byte) Math.max(registers[i], other.registers[i]);\n }\n }\n\n private long hash64(Object element) {\n return MurmurHash3.hash64(element.toString().getBytes());\n }\n}\n```\n\n### Error Analysis\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ HYPERLOGLOG PRECISION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Precision P | Registers M | Memory | Standard Error │\n│ ───────────────────────────────────────────────────────────────│\n│ 4 | 16 | 16B | 26% │\n│ 8 | 256 | 256B | 6.5% │\n│ 12 | 4096 | 4KB | 1.6% │\n│ 14 | 16384 | 16KB | 0.8% │\n│ 16 | 65536 | 64KB | 0.4% │\n│ │\n│ Standard Error ≈ 1.04 / √M │\n│ │\n│ P=14 (default): 16KB memory, 0.8% error │\n│ Can count up to 2^64 distinct elements! │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Reservoir Sampling\n\n### The Problem\n\nSelect k random items from a stream of unknown length.\n\n```java\npublic class ReservoirSampling {\n private final T[] reservoir;\n private final int k;\n private int count = 0;\n private final Random random = new Random();\n\n @SuppressWarnings(\"unchecked\")\n public ReservoirSampling(int k) {\n this.k = k;\n this.reservoir = (T[]) new Object[k];\n }\n\n public void process(T item) {\n count++;\n\n if (count <= k) {\n // Fill reservoir\n reservoir[count - 1] = item;\n } else {\n // Replace with probability k/count\n int j = random.nextInt(count);\n if (j < k) {\n reservoir[j] = item;\n }\n }\n }\n\n public T[] getSample() {\n if (count < k) {\n return Arrays.copyOf(reservoir, count);\n }\n return reservoir.clone();\n }\n}\n\n// Proof of correctness:\n// P(item i in final sample) = k/n for all i\n//\n// For item i ≤ k:\n// P(survives) = (k/k+1) × (k+1/k+2) × ... × (n-1/n) = k/n ✓\n//\n// For item i > k:\n// P(selected) = k/i\n// P(survives) = (i/i+1) × (i+1/i+2) × ... × (n-1/n) = i/n\n// P(in sample) = (k/i) × (i/n) = k/n ✓\n```\n\n### Weighted Reservoir Sampling\n\n```java\npublic class WeightedReservoirSampling {\n private final int k;\n private final PriorityQueue> reservoir;\n private final Random random = new Random();\n\n static class WeightedItem implements Comparable> {\n T item;\n double key;\n\n WeightedItem(T item, double key) {\n this.item = item;\n this.key = key;\n }\n\n @Override\n public int compareTo(WeightedItem other) {\n return Double.compare(this.key, other.key);\n }\n }\n\n public WeightedReservoirSampling(int k) {\n this.k = k;\n this.reservoir = new PriorityQueue<>();\n }\n\n public void process(T item, double weight) {\n // Key = random^(1/weight), higher weight → higher key\n double key = Math.pow(random.nextDouble(), 1.0 / weight);\n\n if (reservoir.size() < k) {\n reservoir.offer(new WeightedItem<>(item, key));\n } else if (key > reservoir.peek().key) {\n reservoir.poll();\n reservoir.offer(new WeightedItem<>(item, key));\n }\n }\n\n public List getSample() {\n return reservoir.stream()\n .map(wi -> wi.item)\n .collect(Collectors.toList());\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Randomized Algorithms\n\n### QuickSelect (Las Vegas)\n\n```java\npublic class QuickSelect {\n private Random random = new Random();\n\n // Find k-th smallest element in O(n) expected time\n public int select(int[] arr, int k) {\n return quickSelect(arr, 0, arr.length - 1, k - 1);\n }\n\n private int quickSelect(int[] arr, int left, int right, int k) {\n if (left == right) return arr[left];\n\n // Random pivot for Las Vegas guarantee\n int pivotIndex = left + random.nextInt(right - left + 1);\n pivotIndex = partition(arr, left, right, pivotIndex);\n\n if (k == pivotIndex) {\n return arr[k];\n } else if (k < pivotIndex) {\n return quickSelect(arr, left, pivotIndex - 1, k);\n } else {\n return quickSelect(arr, pivotIndex + 1, right, k);\n }\n }\n\n private int partition(int[] arr, int left, int right, int pivotIndex) {\n int pivotValue = arr[pivotIndex];\n swap(arr, pivotIndex, right);\n int storeIndex = left;\n\n for (int i = left; i < right; i++) {\n if (arr[i] < pivotValue) {\n swap(arr, i, storeIndex);\n storeIndex++;\n }\n }\n\n swap(arr, storeIndex, right);\n return storeIndex;\n }\n\n private void swap(int[] arr, int i, int j) {\n int temp = arr[i];\n arr[i] = arr[j];\n arr[j] = temp;\n }\n}\n```\n\n### Miller-Rabin Primality Test (Monte Carlo)\n\n```java\npublic class MillerRabin {\n private Random random = new Random();\n\n // Returns true if n is probably prime\n // False positive probability: < 4^(-k) where k = iterations\n public boolean isProbablePrime(long n, int iterations) {\n if (n < 2) return false;\n if (n == 2 || n == 3) return true;\n if (n % 2 == 0) return false;\n\n // Write n-1 as 2^r × d\n long d = n - 1;\n int r = 0;\n while (d % 2 == 0) {\n d /= 2;\n r++;\n }\n\n // Witness loop\n for (int i = 0; i < iterations; i++) {\n long a = 2 + Math.abs(random.nextLong()) % (n - 3);\n if (!millerRabinTest(n, d, r, a)) {\n return false; // Definitely composite\n }\n }\n\n return true; // Probably prime\n }\n\n private boolean millerRabinTest(long n, long d, int r, long a) {\n long x = modPow(a, d, n);\n\n if (x == 1 || x == n - 1) return true;\n\n for (int i = 0; i < r - 1; i++) {\n x = modPow(x, 2, n);\n if (x == n - 1) return true;\n }\n\n return false;\n }\n\n private long modPow(long base, long exp, long mod) {\n long result = 1;\n base %= mod;\n\n while (exp > 0) {\n if (exp % 2 == 1) {\n result = (result * base) % mod;\n }\n exp /= 2;\n base = (base * base) % mod;\n }\n\n return result;\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Approximation Algorithms\n\n### Vertex Cover (2-Approximation)\n\n```java\npublic class VertexCoverApprox {\n // Guaranteed to find a vertex cover at most 2× optimal size\n\n public Set findVertexCover(int n, List edges) {\n Set cover = new HashSet<>();\n Set remainingEdges = new HashSet<>(edges);\n\n while (!remainingEdges.isEmpty()) {\n // Pick any edge\n int[] edge = remainingEdges.iterator().next();\n int u = edge[0], v = edge[1];\n\n // Add both endpoints to cover\n cover.add(u);\n cover.add(v);\n\n // Remove all edges incident to u or v\n remainingEdges.removeIf(e ->\n e[0] == u || e[1] == u || e[0] == v || e[1] == v);\n }\n\n return cover;\n }\n\n // Why 2-approximation?\n // - Each edge chosen contributes 2 vertices to cover\n // - Optimal must include at least 1 vertex from each chosen edge\n // - So |our cover| ≤ 2 × |optimal cover|\n}\n```\n\n### Set Cover (Greedy log(n)-Approximation)\n\n```java\npublic class SetCoverApprox {\n // Greedy achieves ln(n) + 1 approximation ratio\n\n public List setCovers(int n, List> sets) {\n Set uncovered = new HashSet<>();\n for (int i = 0; i < n; i++) uncovered.add(i);\n\n List chosen = new ArrayList<>();\n List> remainingSets = new ArrayList<>(sets);\n\n while (!uncovered.isEmpty()) {\n // Choose set covering most uncovered elements\n int bestIndex = -1;\n int bestCount = 0;\n\n for (int i = 0; i < remainingSets.size(); i++) {\n Set set = remainingSets.get(i);\n int count = 0;\n for (int elem : set) {\n if (uncovered.contains(elem)) count++;\n }\n if (count > bestCount) {\n bestCount = count;\n bestIndex = i;\n }\n }\n\n if (bestIndex == -1) break; // No progress possible\n\n // Add best set\n chosen.add(bestIndex);\n uncovered.removeAll(remainingSets.get(bestIndex));\n }\n\n return chosen;\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Wrong Bloom Filter Size\n\n```java\n// ❌ WRONG: Too small filter = high false positive rate\nBloomFilter bf = new BloomFilter(100); // Only 100 bits\nfor (int i = 0; i < 1000000; i++) {\n bf.add(i); // Will have ~100% false positive rate!\n}\n\n// ✅ CORRECT: Size based on expected elements and desired FP rate\nBloomFilter bf = new BloomFilter(1000000, 0.01); // 1M elements, 1% FP\n```\n\n---\n\n### Mistake 2: Using Random Without Seed\n\n```java\n// ❌ WRONG: Non-reproducible results\npublic class CountMinSketch {\n private Random random = new Random(); // Different results each run\n // ...\n}\n\n// ✅ CORRECT: Fixed seed for reproducibility\npublic class CountMinSketch {\n private Random random = new Random(42); // Consistent hash functions\n // ...\n}\n```\n\n---\n\n### Mistake 3: Not Handling HyperLogLog Edge Cases\n\n```java\n// ❌ WRONG: No correction for small/large cardinalities\ndouble estimate = ALPHA * M * M / sum;\nreturn (long) estimate;\n\n// ✅ CORRECT: Apply corrections\ndouble estimate = ALPHA * M * M / sum;\n\n// Small range: linear counting\nif (estimate <= 2.5 * M && zeros > 0) {\n estimate = M * Math.log((double) M / zeros);\n}\n\n// Large range: hash collision correction\nif (estimate > POW_2_32 / 30) {\n estimate = -POW_2_32 * Math.log(1 - estimate / POW_2_32);\n}\n\nreturn Math.round(estimate);\n```\n\n---\n\n## 🐛 Debug This: Bloom Filter Bug\n\nThis Bloom filter has a bug causing false negatives. Can you find it?\n\n```java\npublic class BuggyBloomFilter {\n private BitSet bits;\n private int numBits;\n private int numHashes;\n\n public BuggyBloomFilter(int numBits, int numHashes) {\n this.bits = new BitSet(numBits);\n this.numBits = numBits;\n this.numHashes = numHashes;\n }\n\n public void add(String element) {\n for (int i = 0; i < numHashes; i++) {\n int hash = (element.hashCode() + i) % numBits;\n bits.set(hash);\n }\n }\n\n public boolean mightContain(String element) {\n for (int i = 0; i < numHashes; i++) {\n // BUG IS HERE\n int hash = (element.hashCode() + i) % numBits;\n if (!bits.get(hash)) {\n return false;\n }\n }\n return true;\n }\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: Hash can be negative! `hashCode()` can return negative values, and `%` preserves sign in Java.\n\n```java\n// ❌ BUG: Negative hash causes wrong index or ArrayIndexOutOfBounds\nint hash = (element.hashCode() + i) % numBits;\n\n// ✅ FIX: Use Math.abs() or bitwise AND\nint hash = Math.abs((element.hashCode() + i) % numBits);\n// or better:\nint hash = (element.hashCode() + i) & 0x7FFFFFFF % numBits;\n```\n\n**Example**:\n```java\n\"abc\".hashCode() + 0 = 96354 // positive, OK\n\"xyz\".hashCode() + 0 = -1319435 // negative!\n-1319435 % 1000 = -435 // negative index!\n```\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Counting Bloom Filter ⭐⭐\n\nImplement a Bloom filter that supports deletion (use counters instead of bits).\n\n```java\npublic class CountingBloomFilter {\n public void add(T element) { }\n public void remove(T element) { }\n public boolean mightContain(T element) { }\n}\n```\n\n---\n\n### Exercise 2: Min-Hash for Similarity ⭐⭐⭐\n\nImplement MinHash to estimate Jaccard similarity between sets.\n\n```java\npublic class MinHash {\n public double estimateSimilarity(Set set1, Set set2) {\n // Use k hash functions\n // Similarity ≈ fraction of matching minimum hashes\n }\n}\n```\n\n---\n\n### Exercise 3: Streaming Median ⭐⭐⭐\n\nFind approximate median in a stream using reservoir sampling.\n\n```java\npublic class StreamingMedian {\n public double getApproximateMedian(Stream stream) {\n // Sample k elements, return median of sample\n }\n}\n```\n\n---\n\n### Exercise 4: FPTAS for Knapsack ⭐⭐⭐⭐\n\nImplement fully polynomial-time approximation scheme for 0/1 knapsack.\n\n```java\npublic class KnapsackFPTAS {\n public int approximate(int[] weights, int[] values, int capacity, double epsilon) {\n // Scale values, run DP, get (1-ε) approximation\n }\n}\n```\n\n---\n\n### Exercise 5: Streaming Heavy Hitters ⭐⭐⭐⭐\n\nFind all elements appearing more than n/k times using O(k) space.\n\n```java\npublic class MisraGries {\n public Map findHeavyHitters(int[] stream, int k) {\n // Misra-Gries algorithm\n }\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"When should you use a Bloom filter vs a hash set?\"\n\n**Answer**:\n\n| Use Bloom Filter | Use Hash Set |\n|------------------|--------------|\n| Can tolerate false positives | Need 100% accuracy |\n| Memory is constrained | Memory is available |\n| Set is large (millions+) | Set is small |\n| Read-heavy, rarely delete | Need deletions |\n| Distributed merging needed | Single machine |\n\n**Examples**:\n- Bloom: Spell checker, URL blocklist, cache prefetch\n- HashSet: Shopping cart, user session, exact dedup\n\n---\n\n### Q2: \"Explain the trade-offs in HyperLogLog precision.\"\n\n**Answer**:\n\n```\nHigher precision (more registers):\n+ Lower error rate (1.04/√M)\n- More memory (M bytes)\n- Slightly slower merge\n\nTypical choices:\n- P=10 (~1KB, 3.3% error): Resource-constrained\n- P=14 (~16KB, 0.8% error): Good default\n- P=16 (~64KB, 0.4% error): High accuracy needed\n\nThe logarithmic nature means:\n- Doubling memory halves error (roughly)\n- Can count 2^64 items with any precision\n- Error is independent of cardinality\n```\n\n---\n\n### Q3: \"How would you find the top-k frequent items in a stream?\"\n\n**Answer**:\n\n```java\n// Option 1: Count-Min Sketch + Heap\npublic class TopKFrequent {\n CountMinSketch cms;\n PriorityQueue topK; // [item, estimated_count]\n\n void process(long item) {\n cms.add(item);\n int count = cms.estimateCount(item);\n\n // Update top-k heap\n // Challenge: maintaining accurate top-k with overestimates\n }\n}\n\n// Option 2: Space-Saving Algorithm (deterministic)\npublic class SpaceSaving {\n // Keep k counters, each with an item and count\n // When new item: if tracked, increment; else replace min\n\n // Guarantees: true heavy hitters are found\n // but may have false positives\n}\n\n// Option 3: Lossy Counting\n// Divide stream into buckets, decrement all at boundaries\n```\n\n---\n\n### Q4: \"What's the difference between Las Vegas and Monte Carlo algorithms?\"\n\n**Answer**:\n\n| Las Vegas | Monte Carlo |\n|-----------|-------------|\n| Always correct | May be incorrect |\n| Random running time | Fixed running time |\n| E[time] is bounded | Error probability bounded |\n\n**Examples**:\n```\nLas Vegas:\n- QuickSort with random pivot: correct sort, E[O(n log n)] time\n- QuickSelect: correct k-th element, E[O(n)] time\n\nMonte Carlo:\n- Miller-Rabin primality: may say composite is prime, O(k log³ n)\n- Approximate counting: estimate with bounded error\n\nConverting:\n- Monte Carlo → Las Vegas: Run until verifiable answer\n- Las Vegas → Monte Carlo: Set time limit, return best found\n```\n\n---\n\n### Q5: \"Design a system to detect duplicate URLs across multiple servers.\"\n\n**Answer**:\n\n```\nArchitecture:\n┌─────────────────────────────────────────────────────────────────┐\n│ │\n│ ┌─────────┐ ┌─────────┐ ┌─────────┐ ┌─────────┐ │\n│ │ Server1 │ │ Server2 │ │ Server3 │ │ Server4 │ │\n│ │ Bloom │ │ Bloom │ │ Bloom │ │ Bloom │ │\n│ │ Filter │ │ Filter │ │ Filter │ │ Filter │ │\n│ └────┬────┘ └────┬────┘ └────┬────┘ └────┬────┘ │\n│ │ │ │ │ │\n│ └─────────────┴─────────────┴─────────────┘ │\n│ │ │\n│ Merge Layer │\n│ (OR operation) │\n│ │ │\n│ Global Bloom Filter │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n\nAlgorithm:\n1. Each server maintains local Bloom filter\n2. On new URL: check local filter first (fast)\n3. If negative locally, check global (slower)\n4. Periodically merge local → global\n5. For positives: verify in actual URL store (handles false positives)\n\nBenefits:\n- Fast local lookups\n- Distributed, scalable\n- Mergeable filters\n- Bounded false positive rate\n```\n\n---\n\n## 📋 Quick Reference\n\n### Data Structures\n\n| Structure | Operation | Space | Error |\n|-----------|-----------|-------|-------|\n| Bloom Filter | Membership | O(n) | FP: 1% typical |\n| Count-Min Sketch | Frequency | O(1/ε × log(1/δ)) | Overestimate |\n| HyperLogLog | Cardinality | O(1) | ~1% typical |\n\n### Algorithm Types\n\n| Type | Correctness | Time |\n|------|-------------|------|\n| Las Vegas | Always | Random |\n| Monte Carlo | Probably | Deterministic |\n| Approximation | Within factor | Deterministic |\n\n### Key Formulas\n\n```\nBloom Filter:\n- Optimal bits: m = -n × ln(p) / (ln(2))²\n- Optimal hashes: k = (m/n) × ln(2)\n- FP rate: (1 - e^(-kn/m))^k\n\nHyperLogLog:\n- Standard error: 1.04 / √M\n- Memory: M registers × 5 bits\n\nCount-Min Sketch:\n- Width w = e/ε (for error ε)\n- Depth d = ln(1/δ) (for confidence 1-δ)\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 22: Algorithm Design Patterns & Interview Prep**, we'll explore:\n- Two pointers technique\n- Sliding window\n- Monotonic stack/queue\n- Pattern recognition guide\n- Interview strategies\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + Bloom Filter | 90 min |\n| 1 | Quick Reference | 10 min |\n| 3 | Implement HyperLogLog | 30 min |\n| 7 | Count-Min Sketch exercises | 25 min |\n| 14 | Debug exercise + approximation | 20 min |\n| 30 | Interview questions | 15 min |\n\n---\n\n**Next**: [Part 22: Algorithm Design Patterns & Interview Prep →](./algorithms-part-22-interview-patterns.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.324372Z","createdAt","2026-06-10T07:19:25.325175Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",21,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder","author",{"_31":55,"_98":57,"_99":100,"_101":102,"_103":-5,"_104":-5,"_105":-5,"_106":-5,"_107":-5},"category",{"_31":94,"_72":59,"_35":95,"_75":96,"_97":-5},"tags",[78,79,80,81],"series",{"_31":62,"_72":73,"_35":74,"_75":76,"_77":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":91,"_72":92,"_35":93},{"_31":88,"_72":89,"_35":90},{"_31":85,"_72":86,"_35":87},{"_31":82,"_72":83,"_35":84},208,"Probabilistic","probabilistic",206,"Hyperloglog","hyperloglog",207,"Count-min Sketch","count-min-sketch",205,"Bloom Filter","bloom-filter",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]