Skip to content
Complete Algorithm & Data Structure Interview Guide: From Arrays to Distributed Systems with Java Implementations
Fundamentals 76 min read

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.

Rain's Path to Java Mastery
Rain's Path to Java Mastery
Rain's Path to Java Mastery

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/ms

1 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

Original Source

Signed-in readers can open the original source through BestHub's protected redirect.

Sign in to view source
Republication Notice

This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactadmin@besthub.devand we will review it promptly.

Distributed SystemsJavaSystem DesignData StructuresInterview PreparationAlgorithmsRate LimitingDatabase Indexing
Reader feedback

How this landed with the community

Sign in to like

Rate this article

Was this worth your time?

Sign in to rate
Discussion

0 Comments

Thoughtful readers leave field notes, pushback, and hard-won operational detail here.