Complete Algorithm & Data Structure Interview Guide: From Arrays to Distributed Systems with Java Implementations
This comprehensive 30,000-word guide covers 9 core modules — data structures, sorting, search algorithms, algorithm paradigms, string algorithms, hash engineering, rate limiting, distributed IDs, and massive data processing — with Java code, complexity tables, and interview-focused explanations for big-tech preparation.
Data Structures: Arrays, Linked Lists, Stacks, Queues, Hash Tables, Trees, Heaps, Graphs
All data structures solve "how to efficiently store and operate data," with core differences in CRUD time complexity and memory usage.
1. Array (ArrayList)
Core: Contiguous memory, fixed-length (primitive) or dynamic (ArrayList, default capacity 10, 1.5x expansion)
Strength: Random access O(1), cache-friendly
Weakness: Insert/delete O(n), expansion copy overhead
Scenario: Frequent reads, known size, config lists
2. Linked List (LinkedList)
Core: Non-contiguous, node = data + pointer(s)
Types: Singly, doubly, circular
Java: LinkedList (doubly, implements List & Deque)
Strength: Insert/delete O(1) given predecessor, unlimited capacity
Weakness: Random access O(n), cache-unfriendly, pointer overhead
Scenario: Frequent inserts/deletes, LRU cache (LinkedHashMap internal list)
Array vs Linked List Comparison
Memory Layout: Array contiguous, Linked List non-contiguous
Random Access: Array O(1), Linked List O(n)
Head Insert/Delete: Array O(n), Linked List O(1)
Tail Insert/Delete: Both O(1)
Middle Insert/Delete: Array O(n), Linked List O(1) given predecessor
Cache Hit Rate: Array high, Linked List low
Memory Waste: Array expansion reserved space, Linked List pointer overhead
3. Stack (ArrayDeque)
Core: LIFO, operations only at top
Java: Avoid legacy Stack (extends Vector, synchronized, slow); use ArrayDeque
Operations: push/pop/peek all O(1)
Scenario: Bracket matching, call stack, expression evaluation, DFS
4. Queue
Core: FIFO, enqueue at tail, dequeue at head
Java Types:
Non-blocking: ArrayDeque (array-based, recommended), LinkedList
Blocking: ArrayBlockingQueue, LinkedBlockingQueue (thread-safe, producer-consumer)
Priority: PriorityQueue (heap-based)
Scenario: Message queues, task scheduling, BFS, rate limiting
5. Hash Table (HashMap)
Core: Hash function maps key to array index
Collision Resolution: Chaining (HashMap: array + linked list + red-black tree), Open Addressing (ThreadLocalMap)
Java Implementations: HashMap (non-thread-safe, null allowed), ConcurrentHashMap (thread-safe, high concurrency), LinkedHashMap (insertion/access order), TreeMap (sorted, red-black tree)
Key Interview Points: Default capacity 16, load factor 0.75, 2x expansion; treeify at linked list length ≥8 AND array length ≥64; untreeify at ≤6 nodes
Complexity: Average O(1), worst O(n)
Scenario: Fast lookup, deduplication, frequency counting, caching
6. Tree
Core: Hierarchical non-linear structure
Types & Java: Binary Tree, BST (left < root < right, inorder sorted), Red-Black Tree (TreeMap/TreeSet), B-Tree, B+Tree
Traversal: DFS (pre/in/post-order), BFS (level-order)
Scenario: Ordered storage, range queries, DB indexes, file systems
7. Heap (PriorityQueue)
Core: Complete binary tree with heap property: max-heap (parent ≥ children) or min-heap (parent ≤ children)
Java: PriorityQueue (default min-heap, use Comparator for max-heap)
Operations: Insert O(log n), delete top O(log n), peek top O(1)
Scenario: Top K, priority scheduling, heap sort, median finding
8. Graph
Core: Vertices + edges
Storage: Adjacency matrix (dense, O(n²) space), Adjacency list (sparse, O(n+e) space)
Algorithms: DFS (stack), BFS (queue), Dijkstra (shortest path), Topological sort, MST
Scenario: Social networks, navigation, dependency analysis, recommendations
All Data Structures Time Complexity Cheat Sheet
Array: Access O(1), Search O(n), Insert O(n), Delete O(n) — ArrayList
Linked List: Access O(n), Search O(n), Insert O(1), Delete O(1) — LinkedList
Stack: Access O(n), Search O(n), Insert O(1), Delete O(1) — ArrayDeque
Queue: Access O(n), Search O(n), Insert O(1), Delete O(1) — ArrayDeque / LinkedList
Hash Table: Access -, Search O(1), Insert O(1), Delete O(1) — HashMap
BST: Access O(log n), Search O(log n), Insert O(log n), Delete O(log n) — TreeMap (Red-Black)
Red-Black Tree: Access O(log n), Search O(log n), Insert O(log n), Delete O(log n) — TreeMap
Heap: Access O(1), Search O(n), Insert O(log n), Delete O(log n) — PriorityQueue
Note: Hash table is average complexity; heap search arbitrary element O(n), but peek top is O(1).
Selection Principle
Fast random access → Array
Frequent insert/delete → Linked List
FIFO → Queue
LIFO → Stack
Fast key-value lookup → Hash Table
Ordered + range query → Red-Black Tree / TreeMap
Fast max/min → Heap
Sorting Algorithms: Quick Sort, Merge Sort, Heap Sort
Quick Sort
Core: Divide & conquer + pivot partitioning
Process: Pick pivot, partition into < pivot and > pivot, recurse
Partition: Two-pointer scan, swap misplaced elements, place pivot correctly
Complexity: Best/Avg O(n log n), Worst O(n²) (sorted/reverse + bad pivot), Space O(log n) avg, O(n) worst
Stability: Unstable
Optimizations: Random pivot, median-of-three, insertion sort for small arrays
Java: Dual-pivot quicksort for primitives (Arrays.sort)
Merge Sort
Core: Divide & conquer + merge two sorted arrays
Process: Recursively split until single elements, then merge with two pointers
Complexity: Best/Avg/Worst O(n log n), Space O(n)
Stability: Stable (only stable O(n log n) sort)
Drawback: Extra O(n) space
Variant: In-place merge sort (O(1) space, complex)
Application: External sorting (data > memory)
Java: TimSort (optimized merge sort) for objects (Arrays.sort)
Heap Sort
Core: Build max-heap (ascending), repeatedly swap root with last element, sink down, shrink heap
Steps: 1) Heapify entire array O(n) from last non-leaf node; 2) Sort: swap root with end, sink, repeat
Complexity: Best/Avg/Worst O(n log n), Space O(1) in-place
Stability: Unstable
Drawback: Poor cache locality (jumping access)
Application: Priority queues, Top K
Three-Way Comparison
Quick Sort: Avg O(n log n), Worst O(n²), Space O(log n), Unstable, Most cases, large data
Merge Sort: Avg O(n log n), Worst O(n log n), Space O(n), Stable, Stability needed, external sort
Heap Sort: Avg O(n log n), Worst O(n log n), Space O(1), Unstable, Memory constrained, Top K
Search Algorithms: Binary Search, BST, Red-Black Tree, B/B+ Tree
Binary Search
Prerequisite: Sorted array (critical!)
Core: Compare middle, halve search range
Anti-overflow: mid = low + (high - low) / 2
Java: Arrays.binarySearch() returns -(insertion_point+1) if not found
Complexity: Iterative O(log n) time, O(1) space; Recursive O(log n) time, O(log n) space
Variants: Left/right boundary search, rotated array search
Limitation: Insert/delete O(n) shifting → static data only
Binary Search Tree (BST)
Properties: Left < root < right, subtrees are BSTs, inorder traversal sorted
Avg: O(log n), Worst: O(n) (degenerates to linked list with ordered inserts)
Why not used in production: Unbalanced risk
Red-Black Tree
Core: Self-balancing BST via color constraints + rotations; guarantees max path ≤ 2× min path
5 Rules: 1) Red/Black nodes, 2) Root black, 3) NIL leaves black, 4) Red node → black children, 5) Equal black-height on all root-to-leaf paths
Operations: Recolor, left-rotate, right-rotate
Performance: Insert/delete/search worst-case O(log n)
Trade-off vs AVL: Slightly less balanced but fewer rotations → better for write-heavy
Java Uses: TreeMap/TreeSet (ordered map/set), HashMap JDK8+ treeify at ≥8 nodes & capacity ≥64
B-Tree
Motivation: DB indexes millions of rows; binary tree height 20-30 → too many disk I/Os
Solution: Multi-way tree, each node stores many keys, matches disk page size (4KB)
Properties (order m): Max m-1 keys per node, root min 1 key, non-root min ⌈m/2⌉-1 keys, all leaves same level
Data stored in all nodes (including internal)
B+ Tree (MySQL InnoDB Default)
Optimization over B-Tree: Data only in leaf nodes; internal nodes only store navigation keys
Leaf nodes linked via doubly linked list → native range query support (BETWEEN, ORDER BY)
Comparison:
Data Storage: B-Tree all nodes, B+ Tree leaf nodes only
Leaf Links: B-Tree no, B+ Tree doubly linked list
Search Stability: B-Tree unstable (may stop early), B+ Tree stable (always to leaf)
Range Query: B-Tree complex (inorder traversal), B+ Tree simple (scan leaf list)
Why MySQL chooses B+ over Red-Black:
Lower height: 16KB page, ~1KB record → 1000+ keys per internal node → 3-4 levels store tens of millions → 3-4 disk I/Os vs 20+ for RB tree
Range queries via leaf linked list
Stable query performance (always to leaf)
Full scan = traverse leaf list
Disk prefetch: large nodes utilize spatial locality; RB tree nodes too small, waste bandwidth
Five Search Algorithms Summary
Binary Search: Avg O(log n), Worst O(log n), Space O(1), Sorted array
BST: Avg O(log n), Worst O(n), Space O(n), Theoretical, not production
Red-Black Tree: Avg O(log n), Worst O(log n), Space O(n), In-memory ordered map
B-Tree: Avg O(log₋ n), Worst O(log₋ n), Space O(n), File system indexes
B+ Tree: Avg O(log₋ n), Worst O(log₋ n), Space O(n), Database indexes
Evolution chain: Binary Search → BST (degenerates) → Red-Black Tree (self-balancing, write-optimized) → B+ Tree (short & fat, disk I/O optimized). Java memory world uses Red-Black; DB world uses B+.
Algorithm Paradigms: Recursion, Divide & Conquer, Greedy, DP, Backtracking
Recursion
Core: Function calls itself, breaks problem into same-structured subproblems until base case
Three Essentials: Base case (avoid stack overflow), recurrence relation, return value merging
Java Example: Factorial with base case n≤1 return 1
Scenarios: Tree/graph traversal, foundation for divide & conquer/backtracking/DP
Risks: Stack overflow (~1000 depth in Java), repeated computation
Divide & Conquer
Core: Divide → Conquer (recurse) → Merge; subproblems independent, no overlap
Relation to Recursion: Usually implemented recursively but adds merge step
Example: Merge sort (split, sort halves, merge)
Pros: Natural parallelism, reduces O(n²) to O(n log n)
Cons: Merge step extra space
Problems: Merge/Quick sort, binary search, large integer multiplication
Greedy
Core: Make locally optimal choice each step, hope for global optimum
Two Required Properties: Greedy choice property (local optimal → global optimal), Optimal substructure
Counterexample: Coin change [1,3,4] for 6: greedy 4+1+1=3 coins, optimal 3+3=2
Example: Activity selection (sort by end time, pick non-overlapping)
Pros: Low time complexity (O(n) or O(n log n)), simple code
Cons: Not always globally optimal
Problems: Huffman coding, Kruskal MST, activity selection, Jump Game II
Dynamic Programming
Core: Overlapping subproblems + optimal substructure → store subproblem solutions (memoization/DP table) to avoid recomputation
Three Pillars: Memoization + Optimal Substructure + State Transition Equation
Two Conditions: Overlapping subproblems, Optimal substructure
Example: Fibonacci with DP array: dp[i] = dp[i-1] + dp[i-2]
Four-Step Method: 1) Define state (what dp[i] means), 2) Derive transition, 3) Set base cases, 4) Determine iteration order
0-1 Knapsack Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]] + val[i])
Pros: Eliminates recomputation, guarantees global optimum
Cons: State/transition design hard, higher space (optimizable with rolling array)
Problems: LCS, 0-1 Knapsack, Climbing Stairs, Edit Distance
Backtracking
Core: DFS + pruning; try all paths, backtrack when dead end
Template: if end condition → record path; for choice in choices: make choice → recurse → undo choice
Essence: DFS + pruning
vs DP: Backtracking enumerates all solutions (no optimal substructure); DP finds optimal (requires overlapping subproblems)
Example: Permutations with used[] array, path add/remove
Pros: Solves almost all combinatorial enumeration
Cons: Worst-case exponential O(2ⁿ) or O(n!)
Problems: N-Queens, Permutations, Subsets, Combination Sum
Paradigm Comparison
Recursion: Self-call, base case; same structure; no backtrack; problem-dependent; Tree traversal, Hanoi
Divide & Conquer: Divide→Conquer→Merge, independent; independent, no overlap; no backtrack; usually O(n log n); Merge sort, binary search
Greedy: Local optimal each step; no direct dependency; no backtrack; O(n) or O(n log n); Activity selection, Huffman
DP: Store subproblem solutions; heavy overlap; no backtrack; O(n²) or O(nm); 0-1 Knapsack, LCS
Backtracking: DFS + pruning, try all; enumerate all combos; yes backtrack; exponential worst; N-Queens, Permutations
Key Interview Distinctions
Greedy vs DP: Greedy = local optimal, irreversible, not always global; DP = stores all subproblems, reversible, always global; Greedy is DP special case when local→global holds
Divide & Conquer vs DP: D&C = independent subproblems, no overlap; DP = overlapping subproblems, need memoization
Recursion Optimization: Tail recursion (Java doesn't support natively), Iteration (manual stack), Memoized recursion (essentially top-down DP)
Backtracking Optimization: Pruning (sort + skip duplicates), Space optimization (reuse array for state)
String Algorithms: KMP, Trie
KMP Algorithm
Problem: Brute force backtracks main string pointer → O(n×m) worst case
Solution: Preprocess pattern to build next array (longest proper prefix = suffix length), main pointer never backtracks → O(n+m)
next[j] Definition: Length of longest equal prefix/suffix in pattern[0..j-1]
Example Pattern "ABABC": next = [-1, 0, 0, 1, 2]
Construction: Two pointers j,k; if k==-1 or P[j]==P[k] → j++,k++, next[j]=k; else k=next[k] (fallback to shorter prefix)
Matching: On mismatch, j = next[j], i unchanged
Complexity: Time O(n+m), Space O(m)
Optimization: nextval array reduces redundant comparisons for repeated chars
Applications: Text editor find, DNA sequence matching, log keyword search
Trie (Prefix Tree)
Core: Multi-way tree sharing common prefixes; space-for-time
Structure: Each node = char + children[26] (lowercase) + isEnd flag
Operations: Insert O(k), Search O(k), StartsWith O(k) where k = string length
Java Implementation: TrieNode with children[26], isEnd; insert/search/startsWith traverse char by char
Pros: Fast prefix match, natural string sort, no hash collisions
Cons: High memory (26 pointers per node), unsuitable for long strings
Applications: Search autocomplete, spell check, IP routing (longest prefix match), sensitive word filter, deduplication
Optimizations: Radix Tree (compress single-child paths), Double-Array Trie (state machine compression), array instead of Map for small alphabets
Wildcard Search: Pure Trie can't handle "." patterns; need DFS backtracking on Trie or Aho-Corasick/Suffix Tree
KMP vs Trie Comparison
KMP: Single pattern exact match; Ctrl+F find; Time O(n+m); Space O(m)
Trie: Multi-pattern prefix match; Autocomplete, spell check, sensitive words; Time O(L) per word; Space O(nodes × charset)
Hash Algorithms: Consistent Hashing, Bloom Filter
Consistent Hashing
Problem: Traditional hash(key) % nodeCount → node count change invalidates almost all mappings → cache avalanche
Solution: Hash ring 0..2³²-1; map nodes and keys to ring; key → first node clockwise
Effect: Only affected interval data migrates on node add/remove
Data Skew Fix: Virtual nodes (100-200 per physical node) evenly distributed on ring
Pros: Minimal migration, good scalability
Cons: Skew without virtual nodes, higher implementation complexity
Applications: Redis Cluster, distributed caches, Nginx load balancing, Ceph
Java Sketch: TreeMap ring; ceilingEntry for lookup; wrap to firstEntry if null
Bloom Filter
Problem: Cache penetration (non-existent keys hit DB); HashSet too large for massive data
Core: Bit array + k independent hash functions
Add: Set k bits to 1
Query: If any bit 0 → definitely absent; all 1 → possibly present (false positive)
Key Property: "Absent" is 100% accurate; "Present" has false positive rate; No deletion (standard)
False Positive Rate: p ≈ (1 - e^(-kn/m))^k; optimal k = (m/n) ln2
Space Efficiency: 1B items ≈ 1GB at 1% false positive
Pros: Extreme space/time efficiency
Cons: False positives, no deletion, pre-allocated space
Applications: Redis cache penetration, crawler URL dedup, spam filter, blacklist, recommendation dedup
Java (Guava): BloomFilter.create(funnel, expectedInsertions, fpp); put()/mightContain()
Over-capacity: False positive rate spikes sharply; use scalable Bloom filter or pre-allocate
Combined Use
Consistent hashing solves distributed storage location; Bloom filter solves per-node fast existence check. Typical: client uses consistent hash to locate node, node uses Bloom filter to quickly return "not found" avoiding disk/DB I/O.
Rate Limiting Algorithms: Counter, Sliding Window, Leaky Bucket, Token Bucket
Fixed Window Counter
Core: Time divided into fixed windows (e.g., 1s), counter per window, reset at boundary
Pros: Simple, high performance
Cons: Boundary burst — 2× threshold at window edges (e.g., 3 req at 0.9s + 3 at 1.1s = 6 in 0.2s)
Scenario: Low precision needs, stable traffic, internal APIs
Sliding Window
Core: Divide large window into small grids (e.g., 1s = 10×100ms), slide by dropping expired grids, sum active grids
Redis Implementation: ZSET with member=uniqueID, score=timestamp; ZREMRANGEBYSCORE expired, ZCARD count
Pros: Eliminates boundary burst, higher precision
Cons: More complex, slightly lower performance
Scenario: High precision needs, public APIs
Leaky Bucket
Core: Requests enter fixed-capacity bucket; leak out at constant rate; overflow = reject
Mechanics: Track last leak time + current water; on request: leaked = (now - lastLeak) × rate; water = max(0, water - leaked); if water+1 ≤ capacity → accept, water++
Pros: Forces smooth outflow, guarantees stable processing rate
Cons: Cannot handle bursts even when system idle; low resource utilization
Scenario: Strict rate control, message queue smoothing, DB write limiting
Token Bucket
Core: Tokens generated at constant rate into bucket (max capacity); request consumes 1 token; no token = reject
Key Difference: Allows burst up to bucket capacity (pre-stored tokens)
Params: rate (tokens/sec), capacity (max tokens)
Pros: Smooths traffic + handles bursts; industry standard
Cons: More complex implementation
Leaky vs Token: Leaky controls outflow rate (strict smoothing); Token controls inflow rate (allows burst = capacity)
Mnemonics: Leaky = scenic spot queue; Token = restaurant with pre-booked tickets
Scenario: Most internet scenarios: API gateway, microservices, crawler rate control
Four-Way Comparison
Fixed Window: Fixed time counting; Simple, fast; Boundary burst; Simple internal systems
Sliding Window: Sliding time counting; No burst, precise; Complex, slower; Public APIs
Leaky Bucket: Constant outflow; Forces smoothness; No burst handling, low utilization; MQ smoothing, DB writes
Token Bucket: Constant token generation; Smooth + burst support; Complex; Most internet scenarios
Java Ecosystem Implementations
Fixed Window: AtomicInteger (single), Redis incr+expire (distributed)
Sliding Window: Redis ZSET (timestamp score) or Lua script
Token Bucket: Guava RateLimiter (supports warmup, production-grade)
Distributed: Redis + Lua for atomicity
Key Implementation Notes: Sliding window uses ZSET or ring buffer; Token/Leaky bucket use lazy calculation (compute tokens/water from time delta, no background thread); Distributed requires Redis centralized counting with Lua atomic ops.
Snowflake Algorithm (Distributed Unique ID)
64-bit Structure
┌─┬──────────────────────────┬────────────┬──────────────┐
│1│ 41-bit timestamp │ 10-bit machine ID │ 12-bit sequence │
│ │ (milliseconds) │ (5+5 dc+worker) │ (per ms) │
└─┴──────────────────────────┴────────────┴──────────────┘
↑ ↑ ↑ ↑
Reserved Custom epoch 1024 nodes 4096/ms1 bit sign: Always 0 (positive long)
41 bits timestamp: Milliseconds since custom epoch (e.g., 2020-01-01) → ~69 years
10 bits machine ID: 5 bits datacenter + 5 bits worker → 1024 unique nodes
12 bits sequence: Auto-increment per millisecond → 4096 IDs/ms per node → 4.09M IDs/sec theoretical
Benefit: Pure numeric Long, naturally ordered → sequential B+Tree inserts → optimal disk I/O
Java Implementation Highlights
Bit shifts for composition: (timestamp << 22) | (machineId << 12) | sequence
Synchronized nextId() for thread safety
Same millisecond: sequence = (sequence + 1) & MAX_SEQUENCE; if overflow (sequence==0) → wait next millisecond
New millisecond: sequence = 0
Clock backward protection: throw exception (simple), wait for catch-up (advanced), or switch backup machine ID pool (high-end)
Machine ID Allocation Strategies
Manual config (small clusters)
IP hash (simple, collision risk)
ZooKeeper/Redis/etcd auto-assignment (production)
Containerized: bind to Pod hostname/IP hash
Pros/Cons
Pros: High performance: millions IDs/sec/node; Trend-increasing: ideal for DB indexes; Decentralized: no third-party dependency; Customizable bit allocation
Cons: Clock dependency → backward clock issues; Machine ID allocation needs extra mechanism; 41-bit timestamp → ~69 year limit; 4096 IDs/ms per node ceiling
Popular Variants
Baidu UidGenerator: better clock backward handling, higher concurrency
Meituan Leaf: segment mode + snowflake mode
Sonyflake: 16-bit sequence, 10ms precision, longer usable time
Massive Data Processing: Top K, BitMap, Bloom Filter
Top K Problem
Goal: Find K most frequent elements in billions of records (cannot fit in memory)
Approaches Comparison:
Full Sort: O(n log n) time, O(n) space, small data, OOM on massive data
Max Heap: O(n log K) time, O(K) space, single machine small K, only Top K no dedup counting
Divide + Hash + Min Heap: O(n log K) time, O(n/m) space, massive data, engineering complexity
Quick Select: O(n) time, O(n) space, find K-th largest, unstable, not for frequency
Min-Heap Method: Maintain size-K min-heap (root = smallest of top K); traverse data: if heap not full → push; else if new > root → pop root, push new; final heap = Top K
Divide & Conquer for Huge Data: Hash partition into buckets (Map), each bucket computes local Top K via min-heap (Reduce), merge all local Top K with global min-heap
Special Cases: Limited range (age 0-100) → counting/bucket sort O(n); Real-time dynamic Top K → TreeMap + heap combo
Java: HashMap for frequency, PriorityQueue (min-heap default) for heap
BitMap
Core: 1 bit represents 1 integer's existence; 1GB = 8 billion bits
Operations: set(x), get(x), clear(x) via bitwise ops
Classic Problem: Sort 500M unique 32-bit ints with 1GB RAM → int[] needs 2GB (fail); BitMap needs 2³² bits = 512MB (pass)
Java: java.util.BitSet; nextSetBit() for ordered output
Pros: Extreme space efficiency, O(1) time, simple
Cons: Integers only, no duplicates, sparse data wastes space (0 and 2³±-1 still 512MB)
Applications: Integer existence check, distinct count, set intersection/union, crawler URL dedup (after hash to int)
Sparse Optimization: RoaringBitmap (used in Redis, Elasticsearch) compresses sparse bitsets
Bloom Filter (Revisited for Massive Data Context)
Structure: Bit array + k hash functions
Parameters: n=expected items, m=bit array size, k=hash count
Optimal: k = (m/n) ln2; m = -n ln(p) / (ln2)² for target false positive rate p
Example: n=1M, p<1% → m≈9.6M bits (1.2MB), k≈7
Limitation: False positive rate rises as inserted elements exceed n; no deletion (Counting Bloom Filter uses counters instead of bits)
Java (Guava): BloomFilter.create(funnel, n, p)
Applications: Cache penetration (filter non-existent keys), crawler URL dedup (trillion URLs, tiny memory), spam filter, HBase BlockCache
Interview Mantra: "Present may be false; Absent is definitely true"
Three-Way Selection Guide
Top K: Frequency ranking; No false positive; Deletion supported; Space O(n/m); Hot search, popular items
BitMap: Integer existence; No false positive; Deletion supported; Space O(n/8); Integer dedup, set ops
Bloom Filter: Probabilistic existence; False positive yes; No deletion (Counting BF yes); Space O(n); Cache penetration, URL dedup
Bonus Points for Interviews
Mention RoaringBitmap for sparse BitMap optimization
Mention Counting Bloom Filter for deletable Bloom Filter
Discuss Bloom Filter initialization/update strategy in Redis cache penetration context
Note boundary: if K is huge (e.g., 1M), min-heap fails → need divide & conquer sort
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
