// ============================================ // Probabilistic Data Structures // ============================================ // ---------- Bloom Filter ---------- class BloomFilter { constructor(size = 1024, hashCount = 3) { this.size = size; this.hashCount = hashCount; this.bitArray = new Uint8Array(size); } add(item) { for (let i = 0; i < this.hashCount; i++) { const index = this.hash(item, i) % this.size; this.bitArray[index] = 1; } } mightContain(item) { for (let i = 0; i < this.hashCount; i++) { const index = this.hash(item, i) % this.size; if (this.bitArray[index] === 0) return false; // Definitely not in set } return true; // Probably in set (maybe false positive) } hash(item, seed) { let hash = seed; const str = String(item); for (let i = 0; i < str.length; i++) { hash = ((hash << 5) - hash + str.charCodeAt(i)) | 0; } return Math.abs(hash); } } // ---------- HyperLogLog (Simplified) ---------- class HyperLogLog { constructor(precision = 14) { this.precision = precision; this.m = 1 << precision; // Number of registers (16384) this.registers = new Uint8Array(this.m); } add(item) { const hash = this.hash64(item); const index = hash >>> (32 - this.precision); // First p bits → register index const remaining = hash << this.precision; // Remaining bits const leadingZeros = this.countLeadingZeros(remaining) + 1; this.registers[index] = Math.max(this.registers[index], leadingZeros); } count() { // Harmonic mean of 2^register values let sum = 0; let zeros = 0; for (let i = 0; i < this.m; i++) { sum += Math.pow(2, -this.registers[i]); if (this.registers[i] === 0) zeros++; } const alpha = 0.7213 / (1 + 1.079 / this.m); let estimate = alpha * this.m * this.m / sum; // Small range correction if (estimate < 2.5 * this.m && zeros > 0) { estimate = this.m * Math.log(this.m / zeros); } return Math.round(estimate); } hash64(item) { let hash = 0x811c9dc5; const str = String(item); for (let i = 0; i < str.length; i++) { hash ^= str.charCodeAt(i); hash = (hash * 0x01000193) >>> 0; } return hash; } countLeadingZeros(n) { if (n === 0) return 32; let count = 0; while ((n & 0x80000000) === 0) { n <<= 1; count++; } return count; } } // Demo const bloom = new BloomFilter(10000, 5); bloom.add('hello'); bloom.add('world'); console.log('Contains "hello":', bloom.mightContain('hello')); // true console.log('Contains "missing":', bloom.mightContain('missing')); // false (probably) const hll = new HyperLogLog(); for (let i = 0; i < 100000; i++) hll.add(`user_\${i}`); console.log('Estimated unique:', hll.count()); // ~100000 (±1%)

Phase 12: Advanced Topics

0 of 2 topics completed

Distributed Consensus & Leader Election

Probabilistic Data Structures

🎤 Mock Interview