Use this guide to choose a data structure based on the access patterns and core operations your application requires.
| If Your Primary Goal Is To... | Use This Data Structure | Time Complexity (Average) | Key Trade-off / Constraint |
|---|---|---|---|
| Access items rapidly by index | Array / Vector | O(1) Read | Slow O(n) insertions/deletions in the middle. |
| Insert/Delete frequently at ends | Linked List | O(1) Inserts/Deletes | Slow O(n) sequential search to find elements. |
| Enforce Last-In, First-Out (LIFO) | Stack | O(1) Push / Pop | No random access to middle elements. |
| Enforce First-In, First-Out (FIFO) | Queue | O(1) Enqueue / Dequeue | No random access to middle elements. |
| Look up values instantly by key | Hash Table / HashMap | O(1) Search / Insert | Elements are completely unordered. |
| Keep keys sorted with fast lookup | Balanced BST / TreeMap | O(log n) Search / Insert | Slightly slower lookups than Hash Maps. |
| Constantly pull min or max values | Binary Heap / Priority Queue | O(1) Peek, O(log n) Extract | Poor O(n) time to search for arbitrary items. |
| Look up strings by prefixes | Trie | O(L) where L is length | Higher memory usage compared to hashing. |
| Model networks or connections | Graph | Varies by algorithm | High complexity to store and traverse. |
| Query range sums dynamically | Segment Tree / Fenwick | O(log n) Queries & Updates | Complex to implement and maintain. |
When designing a custom solution, evaluate your problem traits against these core algorithmic strategies. [6, 7]
- Divide and Conquer
- Dynamic Programming (DP)
- When to use: Your problem breaks into overlapping sub-problems with an optimal substructure.
- Examples: Knapsack Problem, Longest Common Subsequence, and Fibonacci.
- Greedy Approach
- When to use: Making the locally optimal choice at each step yields a globally optimal solution.
- Examples: Huffman Encoding, Dijkstra's Shortest Path, and Prim's MST.
- Backtracking
- When to use: You must explore all possible permutations, combinations, or paths, dropping paths as soon as they fail.
- Examples: N-Queens, String Permutations, and Sudoku Solvers.
| Traversal Type | Strategy | Order of Visits | Common Use Case |
|---|---|---|---|
| Preorder | DFS | Root → Left → Right | Copying or serializing a tree |
| Inorder | DFS | Left → Root → Right | Getting sorted data from a Binary Search Tree (BST) |
| Postorder | DFS | Left → Right → Root | Deleting a tree or parsing math expressions |
| Level Order | BFS | Level by level (Left to Right) | Finding the shortest path or level-by-level printing |
In standard BFS scenarios, a visited array or set is diligently maintained to steer clear of revisiting nodes. However, BFS with Bitmasking challenges this norm. Nodes, instead of being dismissed, are revisited, now equipped with an additional layer of information — the state. This state, often represented by a bitmask, augments the node’s identity, enriching the exploration process. Used in solution of Travelling salesman problem.
TSP solution with BFS + Bitmasking video explanation pt1
TSP solution with BFS + Bitmasking video explanation pt2, code
Graph pathfinding algorithms find the most efficient route between nodes in a network and are classified into four main categories:
Explore a graph systematically without external knowledge or distance estimates.
- Breadth-First Search (BFS): Explores nodes layer by layer. Guarantees the shortest path in unweighted graphs.
- Depth-First Search (DFS): Explores as deep as possible before backtracking. Does not guarantee an optimal path.
- Iterative Deepening DFS (IDDFS): Combines DFS's space efficiency with BFS's path optimality by gradually increasing depth limits.
- Uniform Cost Search (UCS): Traverses the graph by expanding the lowest cumulative cost node. Variant of Dijkstra’s algorithm.
- Bidirectional Search: Runs two simultaneous searches (forward from start, backward from goal) meeting in the middle.
Use heuristics (educated guesses about remaining distance) to guide the search, significantly cutting down calculation time.
- A Search*: Combines actual distance from start with a heuristic estimate to the goal. Highly efficient and optimal.
- Greedy Best-First Search: Focuses solely on the heuristic estimate to the destination. Fast but prone to suboptimal paths.
- Iterative Deepening A (IDA)**: Optimizes memory usage by using an incrementally increasing cutoff cost threshold.
- D (Dynamic A)**: Incremental search algorithm that recalculates paths in real-time as environments change.
- Fringe Search: Variation of A* using a fringe list to find the shortest path faster by reducing node sorting overhead.
- Lifelong Planning A (LPA)**: Incremental heuristic search designed for dynamic graphs where edge costs change over time.
Calculate the shortest paths from one specific source node to all other reachable nodes in a weighted graph.
- Dijkstra's Algorithm: Solves SSSP on graphs with non-negative edge weights using a priority queue.
- Bellman-Ford Algorithm: Computes SSSP and handles negative edge weights. Detects negative weight cycles.
- DAG Shortest Path: Utilizes topological sorting to find shortest paths in Directed Acyclic Graphs in linear time.
- Dial's Algorithm: Optimized version of Dijkstra's algorithm tailored specifically for small integer edge weights.
- Delta-stepping: Parallel algorithm that divides Dijkstra's workload into steps for massive networks.
Calculate the absolute shortest routes between every single pair of nodes across the entire network.
- Floyd-Warshall Algorithm: Dynamic programming approach updating a distance matrix for dense graphs.
- Johnson's Algorithm: Combines Bellman-Ford and Dijkstra's algorithms to efficiently handle sparse graphs with negative weights.
- Seidel's Algorithm: Utilizes fast matrix multiplication to solve the APSP problem efficiently on unweighted graphs.
| Algorithm | Graph Type | Edge Weights | Best For | Key Advantage / When to Use |
|---|---|---|---|---|
| BFS | Unweighted | None | Single-Source | Shortest path on unweighted or uniform-cost networks |
| DFS | Unweighted | None | Connectivity | Checking if a path exists or exploring full mazes |
| IDDFS | Unweighted | None | Single-Source | Finding shortest paths when memory is extremely limited |
| Bidirectional | Unweighted / Weighted | Non-negative | Single-Pair | Cutting search space in half when start and goal are known |
| Dijkstra | Weighted | Non-negative | Single-Source | Finding the absolute shortest path from one point to all others |
| Bellman-Ford | Weighted | Negative allowed | Single-Source | Graphs containing negative weights or needing cycle detection |
| DAG Shortest Path | Directed Acyclic | Any weight | Single-Source | Maximum speed on directional graphs with no cycles |
| A* | Weighted | Non-negative | Single-Pair | Standard game AI and GPS routing with geometric coordinates |
| Greedy Best-First | Weighted | Non-negative | Single-Pair | Getting a fast answer where accuracy is not critical |
| IDA* | Weighted | Non-negative | Single-Pair | Finding optimal heuristic paths on memory-constrained systems |
| D* | Dynamic / Changing | Non-negative | Single-Pair | Robotics and autonomous vehicles navigating unknown terrain |
| LPA* | Dynamic / Changing | Non-negative | Single-Pair | Path replanning when edge costs change frequently over time |
| Floyd-Warshall | Dense / Weighted | Negative allowed | All-Pairs | Small, dense networks where you need distances between all nodes |
| Johnson's | Sparse / Weighted | Negative allowed | All-Pairs | Large, sparse networks where you need distances between all nodes |
- Breadth-First Search (BFS): Use when every step costs exactly the same (e.g., social networks finding 1st/2nd-degree connections, or peer-to-peer networks).
- Depth-First Search (DFS): Use when you need to visit every node anyway (topological sorting), or when solving puzzles where you must backtrack from dead ends.
- Iterative Deepening (IDDFS): Use in game trees (like chess) where you want the completeness of BFS but cannot afford its massive memory footprint.
- Bidirectional Search: Use in massive social networks or maps when you know both the starting point and the exact destination point.
- Dijkstra’s Algorithm: Use for stable networks with varying positive costs (e.g., network routing protocols like OSPF, or transit routing).
- Bellman-Ford Algorithm: Use when your graph has negative values (like financial arbitrage networks or transactional balances) and you must detect illegal infinitely repeating loops.
- DAG Shortest Path: Use for scheduling problems, project management (PERT/CPM), or asset valuation where dependencies only move forward in time.
- A Search*: Use when you need the shortest path to a single target and can calculate a straight-line distance estimate (e.g., video game character movement, Google Maps).
- Greedy Best-First Search: Use when you need immediate results and a "close enough" path is acceptable (e.g., quick path estimation in real-time strategy games).
- D / LPA**: Use when a robot or vehicle maps a territory in real-time, allowing it to fix its route dynamically without recalculating the entire map from scratch.
- Floyd-Warshall: Use when you have a small network (under a few hundred nodes) and need to build a permanent look-up routing table.
- Johnson’s Algorithm: Use for the exact same purpose as Floyd-Warshall, but when your network is sparse (mostly disconnected nodes) to save significant memory and processing time.
A topological sort is a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u → v, vertex u comes before v. It is widely used for task scheduling, package dependency resolution, and course prerequisites
algorithms which can be used in topological sort:
- Kahn's Algorithm: A breadth-first approach that repeatedly removes nodes with an in-degree of zero to build the sorted list.
- Depth-First Search (DFS) Method: A recursive approach that visits nodes deeply and adds them to the result list upon backtracking.
- Parallel Topological Sort: A variation of Kahn's algorithm that groups independent tasks into concurrent levels for scheduling.
- Tarjan's Algorithm: A cycle-detecting approach that groups strongly connected components and sorts them in a reverse topological order.
https://leetcode.com/discuss/post/4252467/topological-sorting-on-graph-by-sanjeev1-m0ly/
Union-Find, also known as the Disjoint-Set Union (DSU) data structure, is a highly efficient tool used to keep track of a partition of elements into mutually exclusive (disjoint) sets. It is widely used to solve graph connectivity problems, group elements together, and detect cycles in undirected graphs
is used when you need to track, merge, and query partitions of a dataset into non-overlapping groups in near-constant time. It is primarily applied in graph theory and network analysis to solve dynamic connectivity problems.
When to Choose Union-Find Over Other Algorithms:
- Dynamic Graph Modification: Choose it when edges are continuously being added over time, and you need to query connectivity at any moment.
- Efficiency Over BFS/DFS: While Breadth-First Search (BFS) or Depth-First Search (DFS) can find connected components, they take (O(V + E)) time and require a full graph traversal every time a new edge is added.
- Near-Constant Operations: With optimizations like path compression and union by rank, Union-Find handles updates and queries in amortized (O(\alpha(n))) time, which is effectively constant time ((O(1))).
Real-World Scenarios:
- Social Networks: Tracks friendship circles to instantly check if User A and User B are connected through a chain of mutual friends.
- Network Routing: Models physical connections in telecommunications to determine if a path exists between two nodes or servers.
- Image Segmentation: Clusters adjacent pixels with similar colors or intensities together to isolate objects in computer vision.
- Percolation Theory: Simulates chemistry and physics models to see if liquid can flow through a porous material or grid
| Algorithm | Time Complexity | Space Complexity | Best Used When | Practical Example |
|---|---|---|---|---|
| Kruskal's MST | O(E log E) | O(V + E) | Graph is sparse and edges are pre-sorted or easily sortable. | Laying fiber-optic cable to connect cities using the lowest total cable length. |
| Cycle Detection (Undirected Graph) | O(E · α(V)) | O(V) | Graph edges arrive dynamically or online, and quick cycle checks are needed. | Checking if adding a new flight path creates a redundant circular loop in a route network. |
| Percolation Simulation | O(N² · α(N²)) | O(N²) | Modeling fluid flow, conductivity, or threshold dynamics across grid structures. | Simulating oil flowing through porous rock layers to find continuous extraction paths. |
| Connected Components (Grid/Graph) | O(V + E · α(V)) | O(V) | Identifying distinct clusters in unstructured networks or pixel grids. | Finding friend clusters in a social network or segmenting distinct objects in an image. |
| Maze Generation (Kruskal Variant) | O(E log E) | O(V + E) | Generating uniform spanning tree mazes with no loops and guaranteed solvability. | Procedural level generation in video games to create distinct room-and-corridor maps. |
| Tarjan's Offline LCA | O(V + Q · α(V)) | O(V + Q) | Batched Least Common Ancestor queries on trees are available upfront. | Finding the lowest common manager for multiple pairs of employees in a large org chart. |
| Compiler Type Unification | O(N · α(N)) | O(N) | Inferring or checking types across equivalence classes in programming languages. | Resolving type aliases (e.g., type UserID = Int) to ensure variable compatibility. |
Note: α refers to the Inverse Ackermann Function, which runs in effective near-constant time O(1) for all practical input sizes.
Network flow algorithms main categories:
-
Maximum Flow Algorithms: These algorithms compute the maximum amount of flow that can pass from a source node
$s$ to a sink node$t$ in a directed graph without exceeding edge capacities. -
Minimum-Cost Flow Algorithms: Min-Cost Flow algorithms find a flow that satisfies supply/demand requirements while minimizing the total cost of edge traversal
-
Specialized & Related Flow Problems
-
Global Minimum Cut Algorithms: These algorithms compute the global minimum cut of an undirected graph (the smallest total edge weight to disconnect any pair of nodes) without requiring a specific
$s-t$ pair. -
Generalized Flow Algorithms (Flows with Losses / Gains): In generalized networks, edges have a gain factor
$\gamma(e)$ . If flow$f$ enters an edge,$\gamma(e) \cdot f$ leaves it (e.g., modeling financial interest, pipeline leakage, or currency exchange rates). -
Dynamic & Dynamic Flow Over Time: Standard flow models are static. Dynamic flows include time delays on edges, where flow travels along edge
$e$ with travel time$\tau(e)$ . -
Planar & Structured Graph Flow Algorithms: General max flow takes
$O(V^2 E)$ or similar bounds, but specialized algorithms exploit geometric structure
See also: bipartite matching, capacity scaling
The choice of Maximum Flow algorithm depends primarily on graph density (the ratio of edges
| Algorithm | Time Complexity (Theoretical) | Best Suited For | Real-World Performance | Key Implementation Traits |
|---|---|---|---|---|
| Ford-Fulkerson | `O(E * | f* | )` | Very small networks, integer capacities with known small upper bound. |
| Edmonds-Karp | Small-to-medium networks, sparse graphs ( |
Predictable and stable; fast enough for typical competitive programming/small graph tasks. | Uses Breadth-First Search (BFS) to find the shortest augmenting path (in terms of edge count). | |
| Dinic's Algorithm |
|
General-purpose default, bipartite matching, unit networks. | Extremely fast in practice; usually outstrips its worst-case theoretical bound. | Builds a level graph via BFS and routes multiple blocking flows using DFS in phases. |
| Push-Relabel (FIFO / Highest Label) |
|
Dense graphs ( |
Outstanding empirical speed; handles heavy network topologies well. | Operates locally using preflow, excess flow, and height functions instead of global path searches. |
| Boykov-Kolmogorov (BK) | Heuristic (Worst-case exponential) | Image segmentation, 2D/3D grid graphs, computer vision tasks. | Fastest in practice for grid-like spatial structures; slower on random/dense graphs. | Maintains two search trees (source and sink) that grow until they meet. |
Is your graph a 2D/3D Grid (e.g., Computer Vision / Image Segmentation)?
├── YES ──► Boykov-Kolmogorov (BK Algorithm)
└── NO
│
├── Is the graph very dense (E ≈ V²)?
│ └── YES ──► Push-Relabel (Highest Label)
│
└── Default Choice / Sparse Graph / Bipartite Matching
└── YES ──► Dinic's Algorithm
-
Go with Dinic’s Algorithm by default. It hits the sweet spot between code complexity and practical efficiency. For unit-capacity networks (like Bipartite Matching), Dinic runs in
$O(E \sqrt{V})$ time, outperforming most alternatives. -
Use Push-Relabel for dense networks. When edge counts approach
$V^2$ , push-relabel techniques avoid traversing long path structures and typically terminate much faster. - Use Boykov-Kolmogorov for image/spatial grids. In computer vision and grid-based graph cuts, BK tree-reuse heuristics drastically reduce search time.
Max-Flow algorithms are applied widely across engineering disciplines, leveraging either flow routing or min-cut partitioning:
- Interactive Foreground/Background Segmentation (Graph Cut): Each pixel is a vertex connected to neighboring pixels and to source/sink terminals representing foreground/background seeds. Min-cut finds the optimal boundary minimizing color/intensity disparity.
- Stereo Depth Reconstruction: Finding pixel correspondences between left and right camera images by formulating disparity selection as a multi-label graph cut problem.
- Pipeline Capacity Analysis: Finding the maximum rate crude oil can flow from production fields through a complex pipeline network to refineries with varying pipe diameters.
- Airline & Rail Crew Scheduling: Modeling duty periods and flight legs as flow networks to assign crews while respecting rest times and geographic constraints.
- Traffic Management: Determining the maximum vehicle capacity of a highway system during an emergency evacuation.
- Data Packet Routing: Maximizing total bandwidth throughput from data centers to end users across internet backbone links.
- Network Fault Tolerance & Vulnerability Analysis: inding the minimum set of router failures (edges) that would completely disconnect a branch network from the main server cluster (Min-Cut).
-
Maximum Bipartite Matching: Assigning
$N$ workers to$M$ tasks where workers only have specific skills. Connecting a source to all workers, workers to valid tasks, and tasks to a sink (all with capacity 1) allows Max-Flow to find the maximum possible number of assignments. - Sports League Elimination: Determining if a team is mathematically eliminated from winning a league title using Max-Flow network models on remaining head-to-head fixtures.
- Cost per unit flow matters: if pushing flow through a pipe incurs a financial or latency cost, use Min-Cost Max-Flow (MCMF) instead.
- Flow decays or expands: If material vanishes (e.g., electricity loss over long wires) or expands along a path, standard Max-Flow fails. You need Generalized Flow models.
- There are multiple independent sources and sinks: Unless they share the exact same commodity, this requires solving a Multi-Commodity Flow Problem (which is NP-hard and typically solved via Linear Programming).
- Dynamic edge costs / real-time updates: Consider dynamic graph algorithms or continuous flow optimization techniques.
https://gist.github.com/isidzukuri/9898896758369cc273e4b2a8ee5ca3d8
In computer programming, the process of modifying and utilizing binary representations of numbers or any other data is known as bitmasking.
See also chapter 10 "Bit manipulation", "Competitive programmer's handbook" by Antti Laaksonen
spanning tree is a subset of a connected graph that includes every vertex of the original graph using the fewest possible edges without forming any loops or cycles.
Dijkstra’s algorithm using a Binary Min-Heap (Priority Queue) is dramatically faster than using a Standard Queue (BFS) because of how they decide which node to process next.
A binary heap guarantees that once a node is popped, its shortest distance is finalized (settled). It processes nodes in order of increasing distance. A standard queue processes nodes in order of discovery, forcing it to backtrack and re-evaluate path costs constantly whenever edge weights vary.
| Approach | Finding Min Distance Node | Edge Relaxation / Decrease-Key | Overall Time Complexity |
|---|---|---|---|
| Dijkstra + Binary Heap | |||
| Dijkstra + Unsorted Array | |||
| Dijkstra + Standard Queue |
|
|
Also other Advanced Heaps & Priority Queues exists:
| Data Structure | Extract-Min | Decrease-Key | Overall Complexity | Pros & Cons |
|---|---|---|---|---|
| Fibonacci Heap |
|
Best theoretical bound for dense graphs ( |
||
|
|
Faster in practice than Binary Heap on modern CPUs due to better cache locality (nodes have more children packed closely in memory). | |||
| Pairing Heap |
|
|
A simpler, practical alternative to Fibonacci Heaps that performs extremely well in benchmarks. | |
| Radix Heap |
|
|
Specialized for integer edge weights (bounded by |
If all edge weights are small integers bounded by a maximum weight
-
Structure: An array of buckets indexed
$0$ through$W \cdot V$ , where each bucket holds a list of nodes with that exact current distance. -
Complexity:
$O(V \cdot W + E)$ -
When to use: When
$W$ is small (e.g., unit weights$W=1$ degrades to standard BFS in $O(V + E)$).
If edge weights can only be 0 or 1:
-
Structure: A standard Deque (
std::collections::VecDequein Rust). -
Logic: If an edge has weight
0, push the target node to the front of the deque. If1, push to the back. -
Complexity:
$O(V + E)$ (Strictly linear time, beating $O((V+E)\log V)$).
- For general LeetCode / competitive programming: Use the built-in Binary Heap (
std::collections::BinaryHeapin Rust). - For 0-1 edge weights: Use a
VecDeque(0-1 BFS). - For production high-performance graph engines: Use a 4-ary Heap or Radix Heap.
A Probabilistic Data Structure uses randomized algorithms to trade absolute accuracy for extreme efficiency in memory usage and time complexity (
| Data Structure | Practical Use Cases | Primary Problem / Use Case | Key Operations | Time Complexity | Memory Usage | Guarantees / Error Profile |
|---|---|---|---|---|---|---|
| Bloom Filter | Web cache filtering, malicious URL detection, avoiding unnecessary disk reads (Cassandra, RocksDB). | Set Membership Test | Insert, Lookup |
O(k) |
Constant / Bit array | False Positives possible; No False Negatives. Deletions not supported. |
| Counting Bloom Filter | Dynamic streaming applications, tracking active IP connections where items leave the set, router cache management. | Set Membership with Deletions | Insert, Lookup, Delete |
O(k) |
Higher (Counters per bucket) | False Positives possible; No False Negatives. |
| Cuckoo Filter | High-performance content delivery networks (CDNs), resource-constrained set membership, dynamic network routing tables. | Set Membership with Deletions & High Load | Insert, Lookup, Delete |
O(1) |
Compact (Fingerprints) | False Positives possible; No False Negatives. Better space than Bloom for low FPR. |
| HyperLogLog (HLL) | Tracking unique active users (DAU/MAU), SQL COUNT(DISTINCT) queries in analytical engines (Presto, BigQuery, Redis). |
Cardinality (Count-Distinct) Estimation | Add, Count |
O(1) |
Very low (~1.5 KB for millions) | Relative standard error ~ 1.04 / sqrt(m). |
| Count-Min Sketch | Detecting trending hashtags/searches in real time, DDoS / network traffic anomaly detection, API rate limiting. | Frequency Estimation (Heavy Hitters) | Update, Estimate |
O(d) |
Array (d x w) |
Overestimates frequencies; Never underestimates. |
| MinHash | Near-duplicate document detection (web crawlers, plagiarism checkers), recommendation engine similarity, gene clustering. | Jaccard Similarity Estimation | Add, Similarity |
O(k) |
Fixed signature vector | Standard error related to signature size k. |
| t-Digest / Q-Digest | SLA monitoring (P99/P99.9 response latencies), real-time financial metrics, distribution tracking (Datadog, Prometheus). | Quantile & Percentile Estimation | Add, Quantile |
O(log k) |
Small (Centroids) | High accuracy at extreme percentiles (99th, 99.9th). |
- Goal: Test if an element is in a set.
- How it works: Uses a bit array of size
mandkindependent hash functions. When inserting, set the bit at each hash index to1. When checking membership, if allkhashed bit positions are1, it might be in the set; if any bit is0, it is definitely not. - Use Cases: Web cache filtering, malicious URL checking, database indexing (reducing disk lookups).
- Goal: Extend Bloom Filter to support deletions.
- How it works: Replaces single bits in the array with small counters. Insertion increments the counter at each hash index, while deletion decrements them.
- Use Cases: Dynamic streaming applications, tracking active IP connections where items expire/leave the set.
- Goal: Alternative to Bloom Filters supporting deletions and dynamic resizing with better space efficiency at low error rates.
- How it works: Uses cuckoo hashing to store short fingerprints (small hash values) of keys in two candidate buckets. If a bucket is full, it kicks out an existing entry to its alternative location.
- Use Cases: High-performance CDNs, resource-constrained set membership, dynamic routing tables.
- Goal: Estimate the number of unique elements (cardinality) in a stream.
- How it works: Tracks the maximum number of leading zeros in the binary representation of hashed elements. Elements are split into buckets to reduce variance (harmonic mean of estimates).
- Use Cases: Counting unique website visitors (DAU/MAU), SQL
COUNT(DISTINCT)queries in databases like Redis, BigQuery, and Presto.
- Goal: Estimate frequency of items in a stream.
- How it works: Maintains a 2D array of counters with
drows andwcolumns. Each row uses a different hash function. When an item arrives, increment the counter at(row, hash_i(item)). The estimated frequency is the minimum value across alldrows for that item. - Use Cases: Detecting top trends, heavy hitters in network traffic, frequency-based rate limiting.
- Goal: Estimate the Jaccard similarity between two large sets without storing full sets.
- How it works: Hashes elements of a set using
kdifferent hash functions and tracks the minimum hash value for each function. The proportion of matching minimum hash values between two sets estimates their overlap. - Use Cases: Near-duplicate document detection, recommendation systems, genomic sequence clustering.
- Goal: Estimate quantiles and percentiles over streaming numeric data.
- How it works: Groups data points into flexible centroids.
t-Digestadjusts centroid sizes dynamically so that extreme percentiles (e.g., 99th or 99.9th percentile) have high precision. - Use Cases: SLA monitoring (P99/P99.9 latencies), real-time financial risk metrics, observability platforms.
- Space vs. Error Rate: Lowering the acceptable error rate (e.g., false positive probability) requires increasing memory allocated to bit arrays, hashes, or counters.
- No Reversibility: These structures store summaries or bit representations; you cannot retrieve the original inserted items from them.
Comprehensive collection of knowledge: videos, pdfs, implementations
Datastructure cheat sheet short
Datastructure cheat sheet with explenations
Data structures, Algorithms mindmap
Graph data structure and algorithms
Visualising data structures and algorithms through animation
https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
https://www.cs.usfca.edu/~galles/visualization/RedBlack.html
https://en.wikipedia.org/wiki/List_of_algorithms
Competitive Programmer’s Handbook. Antti Laaksonen
The Algorithm Design Manual. Steven S. Skiena











