Data Structures Interview Questions (2026)

A data The technical sequence is a way of organizing data in memory so that specific operations run efficiently. The same data stored as an array, a hash table, or a tree gives completely different speeds for search, insert, and delete.

It matters because the structure you pick decides whether a feature is fast or slow. Looking up a user by ID in a list is O(n); in a hash table it's O(1). Choosing well is often the difference between a millisecond and a second, which is why interviews lead with this.

An array stores elements in one contiguous block of memory, so accessing element i is O(1) by direct address math. But inserting or deleting in the middle is O(n) because every later element shifts.

A linked list stores each element in a node that points to the next one. There's no contiguous block, so access by position is O(n), but inserting or deleting at a known node is O(1) because you just relink pointers. Arrays also iterate faster in practice because contiguous memory is cache-friendly.

Big-O describes how an algorithm's running time or memory grows as the input size grows, ignoring constants and lower-order terms. It answers 'does this still work when n gets large?' rather than 'how many milliseconds?'.

The common ladder from fast to slow is O(1) constant, O(log n) logarithmic, O(n) linear, O(n log n), O(n squared) quadratic, and O(2^n) exponential. Interviewers care because it's the shared language for comparing solutions: naming your solution's Big-O and improving it is the core skill a coding round measures.

A stack is a Last-In-First-Out (LIFO) structure: the last item pushed is the first popped. It supports push, pop, and peek, all O(1). Think of a stack of plates: you take from the top.

Stacks appear everywhere: the call stack that tracks function calls, undo/redo features, matching brackets in a parser, and depth-first traversal. When a problem needs 'the most recent unmatched thing,' a stack is usually the answer.

A queue is First-In-First-Out (FIFO): the first item enqueued is the first dequeued, like a line at a checkout. A stack is LIFO. That single difference decides which one fits a problem.

Use a deque (double-ended queue) for an efficient queue in Python, because popping from the front of a plain list is O(n). Queues drive breadth-first search, task scheduling, and any 'process in arrival order' workflow.

A hash table stores key-value pairs and gives average O(1) lookup, insert, and delete. It runs each key through a hash function that maps it to a slot in an underlying array, so finding a key means computing its hash and going straight to that slot, no scanning.

In Python the built-in dict and set are hash tables. The O(1) is an average: with a good hash function and a reasonable load factor, keys spread out evenly. Bad hashing or too many collisions can degrade it toward O(n).

A collision happens when two different keys hash to the same slot. It's unavoidable because there are more possible keys than slots, so every real hash table needs a resolution strategy.

Two main strategies: separate chaining stores a small list (or tree) of entries at each slot, so colliding keys live together and you scan that short list. Open addressing (used by CPython's dict) probes for the next free slot instead. Both keep average operations O(1) as long as the load factor stays controlled.

The load factor is the ratio of stored entries to available slots (n / capacity). As it climbs, collisions become more frequent and lookups slow down, because more keys share slots.

When the load factor crosses a threshold (often around 0.66 to 0.75), the table resizes: it allocates a larger array and rehashes every key into it. That single insert is O(n), but it's rare, so the amortized cost of insertion stays O(1). This is why dict insertion is fast on average despite the occasional expensive resize.

Use a set when you need fast membership tests or automatic deduplication and don't care about order or duplicates. Checking 'x in list' is O(n), but 'x in set' is O(1) average, because a set is a hash table.

The single cheapest optimization in many programs is converting a lookup list to a set. Sets also give O(1) add and remove, plus union, intersection, and difference operations that would be loops on a list.

A binary tree is a hierarchy where each node has at most two children, a left and a right. It's the base for many structures. A binary search tree (BST) adds one rule: for every node, all values in the left subtree are smaller and all in the right subtree are larger.

That ordering rule makes search, insert, and delete O(log n) in a balanced BST, because each comparison lets you discard half the remaining tree, just like binary search. An unbalanced BST can degrade to O(n), which is why self-balancing trees exist.

Depth-first traversals visit a subtree fully before moving on: inorder (left, node, right), preorder (node, left, right), and postorder (left, right, node). Breadth-first (level order) visits the tree level by level using a queue.

Inorder on a BST yields sorted values, the most-tested fact. Preorder is used to copy or serialize a tree. Postorder is used to delete a tree or evaluate expressions bottom-up. Level order handles 'process by depth' problems.

A binary heap is a complete binary tree stored in an array where every parent is smaller than its children (min-heap) or larger (max-heap). That property means the min or max is always at the root, so peeking it is O(1), while insert and extract are O(log n).

A priority queue is the abstract idea 'always give me the highest-priority item next,' and a heap is the standard way to implement it. Python's heapq module is a min-heap. Use it for scheduling, Dijkstra's algorithm, and 'top k' problems.

The two standard representations are an adjacency list and an adjacency matrix. An adjacency list maps each node to its neighbors, usually a dict of lists, and uses O(V + E) space. An adjacency matrix is a V-by-V grid where cell [i][j] marks an edge, using O(V squared) space.

Prefer an adjacency list for sparse graphs (most real graphs), because it only stores edges that exist. Use a matrix when the graph is dense or when you need O(1) edge-existence checks. The representation you pick affects the Big-O of your traversal.

Breadth-first search (BFS) explores a graph level by level using a queue: it visits all neighbors at the current distance before going deeper. Depth-first search (DFS) goes as deep as possible down one path before backtracking, using a stack or recursion.

BFS finds the shortest path in an unweighted graph, because the first time it reaches a node is via the fewest edges. DFS uses less memory on deep graphs and naturally fits problems like cycle detection, topological sort, and exploring all paths. Both are O(V + E).

Binary search finds a target in a sorted array by repeatedly halving the search range. It checks the middle element: if it matches, done; if the target is larger, search the right half; if smaller, the left half. Each step throws away half the remaining elements.

That halving gives O(log n) time, dramatically faster than a linear O(n) scan for large inputs. The two hard requirements: the data must be sorted, and you must compute the midpoint without integer overflow (in Python that's a non-issue, but it matters in other languages).

Recursion is when a function calls itself to solve a smaller version of the same problem. Every recursive function needs two parts: a base case that stops the recursion, and a recursive case that moves toward the base case.

Without a correct base case, recursion runs until it exhausts the call stack and raises a RecursionError. Recursion shines on naturally nested problems: tree traversals, divide-and-conquer sorts, and anything with self-similar structure. It trades clarity for the memory cost of the call stack.

Walk the list once, reversing each node's next pointer to point at the previous node instead. Keep three references: previous (starts as None), current (starts at head), and a temporary to remember the next node before you overwrite the pointer.

It's O(n) time and O(1) space, and it's one of the most common warm-up questions in a coding round because it tests whether you can manipulate pointers carefully without losing the rest of the list.

Access by index and updating an element are O(1). Appending to the end of a dynamic array is amortized O(1). Inserting or deleting in the middle is O(n) because elements shift. Searching an unsorted array is O(n); a sorted array supports O(log n) binary search.

Knowing these cold lets you spot when a nested loop over an array is secretly O(n squared), which is the most common performance mistake in coding interviews.

A string is a sequence of characters, essentially an array you can index and slice. In many languages including Python, strings are immutable: any operation that seems to modify a string actually creates a new one.

That immutability matters for performance. Building a large string by repeatedly concatenating with += in a loop is O(n squared) because each step copies the whole string so far. Collect the pieces in a list and join once for O(n). This is a frequent gotcha interviewers plant.

Use a hash table when your keys aren't small contiguous integers. Arrays index by position, so they're perfect for 'the 5th element,' but useless for 'the record for user email X.' A hash table maps arbitrary hashable keys to values with O(1) average access.

The other trigger is counting and grouping. Counting word frequencies, grouping items by category, or checking 'have I seen this key?' all map cleanly to a dict, where an array would force you to search.

A circular buffer (ring buffer) is a fixed-size array where the end wraps around to the beginning. Two indices track the head and tail, and when they reach the end they wrap to index 0 using modulo. It gives O(1) enqueue and dequeue in constant memory.

It's useful when you want the most recent N items and don't want memory to grow: streaming logs, audio buffers, sliding-window metrics, and producer-consumer queues. Old data is overwritten as new data arrives, which is exactly the behavior you want for a rolling window.

An abstract data type (ADT) is a specification: it defines what operations a type supports and their behavior, without saying how they're implemented. A stack ADT promises push, pop, and peek. A data The technical sequence is the concrete implementation that fulfills that contract.

A stack ADT can be built on an array or a linked list; both satisfy the contract with different performance. Separating the two is why interviewers ask 'implement a queue using two stacks': you're implementing one ADT with another structure.

A plain binary search tree gives O(log n) operations only when it stays balanced. Insert sorted data into a naive BST and it degrades into a linked list, making every operation O(n). Balanced trees prevent that.

AVL trees and red-black trees rebalance themselves after each insert or delete using rotations, guaranteeing O(log n) height no matter the input order. Red-black trees are the more common choice in libraries (they rebalance less aggressively), and they back structures like Java's TreeMap and C++'s std::map.

Space complexity measures how much extra memory an algorithm uses as the input grows, in the same Big-O terms as time. It counts memory you allocate beyond the input: recursion stack frames, a hash set of seen items, a result array.

The two often trade off. You can speed up a repeated computation by caching results (memoization), spending O(n) space to save time. Interviewers ask for both because a solution that's fast but uses O(n squared) memory can be as unusable as a slow one.

A deque (double-ended queue, pronounced 'deck') lets you add and remove from both ends in O(1). A stack only touches one end (LIFO) and a queue adds at one end and removes at the other (FIFO). A deque generalizes both: use one end and it's a stack, use both ends the FIFO way and it's a queue.

In Python, collections.deque is the go-to for both stacks and queues because appending and popping from either end is O(1), while a plain list is O(n) to pop from the front. Deques also power sliding-window problems where you add on the right and drop stale items from the left.

All three sort in O(n log n) on average, but the trade-offs differ. Quicksort is usually the fastest in O(log n) space, but it's O(n squared) worst case and not stable is the practice path. Merge sort is always O(n log n) and stable, but needs O(n) extra space. Heap sort is always O(n log n) with O(1) space, but it's not stable and has poor cache behavior.

Pick quicksort as the default for in-memory sorting where average speed matters. Pick merge sort when you need stability or you're sorting linked lists or data too big for memory (external sort). Pick heap sort when you need guaranteed O(n log n) with minimal memory and don't need stability.

A stable sort preserves the relative order of elements that compare equal. If two records have the same key, they stay in their original order after sorting. Merge sort and Python's Timsort are stable; quicksort and heap sort are not.

It matters for multi-level sorting. To sort employees by department, then by name within each department, you sort by name first, then by department with a stable sort, and the name order survives. Without stability that second sort would scramble the first. Python's sorted() and list.sort() are stable, which is why this pattern works.

Keep a second stack that tracks the minimum so far. Each time you push a value, also push the current minimum (the smaller of the new value and the previous minimum) onto the min-stack. Each pop removes from both. The top of the min-stack is always the current minimum.

This gives O(1) push, pop, top, and getMin, at the cost of O(n) extra space. It's a classic because the naive approach (scanning for the min on each call) is O(n), and the question needs to see you trade space for time with a second stack.

Two pointers use two indices moving through a data structure, often from opposite ends or at different speeds, to solve a problem in one pass instead of nested loops. It typically turns an O(n squared) brute force into O(n).

Use it on sorted arrays for pair-sum problems (move the pointers inward based on whether the sum is too big or small), on linked lists for cycle detection (slow and fast pointers), and for in-place operations like removing duplicates. The prerequisite is often sorted input or a structure you can traverse with two coordinated positions.

A sliding window maintains a contiguous range (the window) over an array or string and slides it forward, expanding and shrinking to satisfy a condition, so you compute answers for all subarrays or substrings in one O(n) pass instead of re-scanning.

Fixed-size windows solve 'maximum sum of any k consecutive elements' by adding the new element and subtracting the one that left. Variable-size windows solve 'longest substring without repeating characters' by growing the right edge and shrinking the left when the condition breaks. Both avoid the O(n squared) of recomputing each window from scratch.

For a directed graph, run DFS and track three states per node: unvisited, in-progress (on the current path), and done. If DFS reaches a node that's already in-progress, you've found a back edge, which means a cycle. For an undirected graph, DFS and check whether you reach a visited node that isn't the parent you came from.

The alternative for directed graphs is Kahn's algorithm (BFS-based topological sort): if you can't remove all nodes because some always have incoming edges, a cycle exists. Both are O(V + E). Cycle detection underlies dependency resolution, deadlock detection, and validating build graphs.

A topological sort orders the nodes of a directed acyclic graph (DAG) so every edge points forward: if A must come before B, A appears first. It only exists when the graph has no cycles.

Two standard approaches: Kahn's algorithm repeatedly removes nodes with no incoming edges (in-degree zero) using a queue, and DFS-based sort pushes nodes onto a stack as their DFS finishes and reverses it. Both are O(V + E). It powers build systems, task scheduling with dependencies, course prerequisites, and package managers.

A trie (prefix tree) stores strings by their characters: each node represents one character, and a path from the root spells a prefix. Words that share a prefix share the same path, and a flag marks where a complete word ends. Lookup and insert are O(m) where m is the word length, independent of how many words are stored.

It beats a hash table for prefix queries. Autocomplete, 'find all words starting with pre,' and spell-checking are natural on a trie because all words with a given prefix live under one subtree. A hash table can check exact membership in O(1) but can't answer 'which keys this' without scanning everything comes first.

Memoization caches the result of each subproblem the first time you compute it, so repeated calls return instantly instead of recomputing. It's the top-down form of dynamic programming: write the natural recursion, then add a cache keyed by the arguments.

Dynamic programming applies when a problem has overlapping subproblems and optimal substructure. Naive recursive Fibonacci recomputes the same values exponentially; memoizing it makes each value compute once, turning O(2^n) into O(n). The bottom-up (tabulation) form fills a table iteratively instead of recursing.

Naive recursion is O(2^n) time because it recomputes the same subproblems exponentially, and it can blow the stack. Memoized (top-down) recursion caches each value for O(n) time and O(n) space. Bottom-up tabulation fills an array iteratively, also O(n) time, and can drop to O(1) space by keeping only the last two values.

This is a favorite because it demonstrates the whole DP progression on one problem: recognize the overlapping subproblems, add a cache, then optimize the space. The O(1)-space iterative version is the answer that closes the loop.

For the minimum-coins version, use bottom-up DP. Build an array dp where dp[amount] is the fewest coins to make that amount. Start dp[0] = 0, and for each amount from 1 up to the target, try every coin and take the best: dp[a] = min over coins c of dp[a - c] + 1. It's O(amount * number of coins).

The greedy 'take the largest coin first' approach fails for arbitrary coin sets (it works for standard currency by design, but not for something like coins of 1, 3, and 4 making 6). Interviewers use this specifically to see whether you reach for DP over a tempting but wrong greedy.

Use recursion when the problem is naturally self-similar: tree and graph traversal, divide-and-conquer, and backtracking all read cleanly as recursion. Use iteration when the problem is a simple sequential process, or when recursion depth would risk a stack overflow.

The trade-off is clarity versus the call-stack cost. Recursion uses O(depth) stack space and, in languages without tail-call optimization (Python included), can hit a recursion limit on deep inputs. Any recursion can be rewritten as iteration with an explicit stack, which is exactly what you do when depth is a concern.

Use Floyd's tortoise-and-hare algorithm: two pointers, one moving one node at a time (slow) and one moving two (fast). If there's a cycle, the fast pointer eventually laps the slow one and they meet. If the fast pointer hits the end (None), there's no cycle.

It's O(n) time and O(1) space, better than the naive approach of storing every visited node in a set, which is O(n) space. The same two-speed idea also finds the cycle's start and the middle of a list, which is why interviewers like it.

Choose a hash table when you only need exact key lookup, insert, and delete, and you want O(1) average. Choose a balanced BST when you need the data kept in sorted order or you need range queries, ordered iteration, or the nearest key to a value.

A hash table can't answer 'give me all keys between 10 and 50' or 'what's the smallest key larger than x' without scanning everything. A balanced BST (or a structure like a skip list) does those in O(log n) because it maintains order. The trade is O(log n) operations versus the hash table's O(1) average.

An in-place algorithm transforms its input using O(1) extra space (or O(log n) for the recursion stack), modifying the data directly instead of allocating a separate copy. Reversing an array by swapping ends inward is in-place; building a new reversed array is not.

It matters when memory is tight or the data is huge. In-place quicksort sorts without a second array; the two-pointer 'remove duplicates from a sorted array' runs in O(1) space. Interviewers often add 'do it in-place' as a constraint precisely to see whether you can avoid the easy extra-space solution.

For non-negative weights, use Dijkstra's algorithm: keep a min-heap (priority queue) of nodes by their tentative distance, repeatedly pop the closest unfinished node, and relax its neighbors. With a heap it's O((V + E) log V). For unweighted graphs, plain BFS already gives the shortest path in O(V + E).

If the graph has negative edge weights, Dijkstra breaks; use Bellman-Ford (O(V * E)), which also detects negative cycles. For all-pairs shortest paths on a small dense graph, Floyd-Warshall is O(V cubed). Naming the right algorithm for the weight condition is the whole point of the question.

Amortized analysis measures the average cost of an operation over a sequence, so occasional expensive operations are spread across many cheap ones. It's not the same as average-case (which is about random inputs); amortized is a guarantee over any sequence.

The classic example is appending to a dynamic array. Most appends are O(1), but when the array fills, it doubles its capacity and copies everything, an O(n) operation. Because doublings are rare and each copies roughly what all the cheap appends since the last doubling added, the amortized cost per append is O(1).

Combine a hash table with a doubly linked list. The hash table maps keys to nodes for O(1) lookup. The doubly linked list keeps nodes in usage order: most-recently-used at the front, least-recently-used at the back. On access, move the node to the front; on insert past capacity, evict the tail.

Both get and put are O(1) because the hash table finds the node instantly and the doubly linked list lets you unlink and re-insert in constant time. In Python, collections.OrderedDict (or a plain dict since 3.7, using move_to_end) gives this for free, which is worth mentioning after you've shown you know the underlying design.

The reliable way is to pass down a valid range for each node. The root can be anything; a left child must be less than its parent and within the parent's lower bound; a right child must be greater and within the upper bound. Recurse with tightening bounds and check each node falls inside its range.

The common wrong answer only compares each node to its immediate children, which misses violations deeper in the tree. An alternative correct method is an inorder traversal: a valid BST produces strictly increasing values, so you check that each visited value is greater than the previous one.

Backtracking builds a solution incrementally and abandons a partial candidate the moment it can't lead to a valid answer, then undoes the last choice and tries another. It's a smarter brute force that prunes dead branches instead of enumerating every full combination.

It fits constraint problems: generating permutations and subsets, solving Sudoku or N-queens, and word searches. The The technical sequence is a recursive 'choose, explore, un-choose' loop. Pruning early is what makes it feasible where naive brute force would be hopelessly slow.

The building blocks: x & 1 tests the lowest bit (odd/even), x << k multiplies by 2^k, x >> k divides, x & (x - 1) clears the lowest set bit, and XOR (^) toggles bits. XOR has a useful property: a ^ a is 0 and a ^ 0 is a.

That XOR property solves the 'find the single number where every other appears twice' problem in O(n) time and O(1) space: XOR all numbers and the pairs cancel, leaving the unique one. Bit manipulation shows up in problems about sets of flags, counting set bits, and space-tight uniqueness checks.

A prefix sum array stores, at each index, the running total of all elements up to that point. Once built in O(n), it answers 'what's the sum of the range from i to j?' in O(1) by subtracting prefix[i] from prefix[j+1], instead of re-adding the range each time.

It turns repeated range-sum queries from O(n) each into O(1) each, a big win when you have many queries on a static array. The same idea extends to 2D grids for rectangle sums, and pairs with a hash table to solve 'count subarrays that sum to k' in one pass.

Start from the access pattern, not the data. Profile which operation dominates (read-heavy, write-heavy, range scans, point lookups) and its required latency, then pick the structure whose Big-O matches, and only then consider memory and cache behavior. A structure that's theoretically optimal but cache-hostile can lose to a simpler contiguous one.

At scale the answer often stops being a single in-memory structure and becomes a system: a hash index for point lookups, a B-tree or LSM-tree for on-disk sorted access (why databases use them), a bloom filter to skip disk reads for absent keys. The production signal is reasoning from workload to structure, and knowing when the structure lives on disk, not just in RAM.

A B-tree is a balanced tree where each node holds many keys and has many children, keeping the tree very shallow. Databases store data on disk, and disk reads happen in blocks (pages). A B-tree node is sized to one page, so a single disk read loads many keys at once, minimizing the number of slow disk seeks.

A binary search tree has only two children per node, so its height is much larger and every step down the tree could be a separate disk read. For n keys, a B-tree of order m has height around log_m(n) versus log_2(n) for a BST, a big difference in disk I/O. The whole design optimizes for the fact that disk access dominates cost.

A bloom filter is a space-efficient probabilistic structure that answers 'is this element possibly in the set?' with two possible replies: definitely not, or probably yes. It uses a bit array and several hash functions; adding an element sets several bits, and a query checks whether all those bits are set.

The trade-off: it can produce false positives (says 'probably yes' when the element is absent) but never false negatives. That's acceptable when a false positive just triggers a cheap fallback check. Uses include skipping disk lookups for keys that definitely aren't stored, deduplicating a massive stream, and CDN cache checks. You spend a little accuracy to save enormous memory.

Consistent hashing maps both keys and servers onto a ring (a hash space). A key belongs to the first server clockwise from its position. When a server is added or removed, only the keys in its arc move; the rest stay put.

It solves the rehashing storm of naive hash-mod-N sharding. With hash(key) % N, changing the number of servers remaps almost every key, which is catastrophic for a distributed cache or database. Consistent hashing limits movement to roughly 1/N of keys per change, and virtual nodes smooth out the load distribution. It's foundational to systems like distributed caches and sharded stores.

Union-find tracks a collection of disjoint sets and supports two operations: find (which set is this element in?) and union (merge two sets). It's built as a forest where each element points toward its set's representative root.

Two optimizations make it near-constant time: path compression flattens the tree during find, and union by rank attaches the smaller tree under the larger. Together they give nearly O(1) amortized (inverse Ackermann) per operation. It powers Kruskal's minimum spanning tree, detecting whether adding an edge creates a cycle, and grouping connected components, like counting islands or friend circles.

A log-structured merge-tree buffers writes in memory (a memtable, often a balanced tree or skip list), then flushes them as sorted immutable files (SSTables) to disk. Background compaction merges those files to keep read cost bounded and reclaim space from overwritten or deleted keys.

It's chosen for write-heavy workloads because writes are sequential appends, which disks and SSDs handle far faster than the random writes a B-tree makes when updating pages in place. The cost is slower reads (a key might live in several SSTables) and write amplification from compaction, which bloom filters and tiered compaction mitigate. It backs many modern stores; the B-tree-versus-LSM choice is a read-optimized-versus-write-optimized trade.

A skip list is a layered linked list: the bottom layer holds all elements in order, and higher layers hold progressively sparser 'express lanes' that let you skip ahead. Searching drops down levels, giving O(log n) expected search, insert, and delete, the same as a balanced tree.

The appeal is simplicity and concurrency. Skip lists are far easier to implement correctly than a red-black tree, and they lend themselves to lock-free concurrent implementations because operations touch localized pointers. That's why Redis uses them for sorted sets and Java's ConcurrentSkipListMap exists. The trade is probabilistic balance (based on random levels) rather than a strict guarantee.

Modern CPUs are far faster than main memory, so they cache recently and nearby data in lines of about 64 bytes. Structures with contiguous memory (arrays, vectors) get many useful elements per cache line and iterate fast. Pointer-chasing structures (linked lists, node-based trees) scatter data, causing cache misses that can dominate runtime.

This is why an O(n) linear scan over an array often beats an O(log n) search over a scattered tree for small-to-medium n, and why a hash table with open addressing can outperform one with chaining. The senior point: Big-O ignores constants, but cache misses are a huge constant, so on real hardware the memory layout can matter as much as the asymptotic complexity.

The core difficulty is that operations which look atomic (read-modify-write) aren't, so two threads can interleave and corrupt shared state or see torn reads. Coarse locking (one lock for the whole structure) is correct but kills throughput; fine-grained locking (per-node or per-bucket) scales better but invites deadlock and is hard to reason about.

Lock-free structures use atomic compare-and-swap to make progress without locks, avoiding deadlock but battling the ABA problem and subtle memory-ordering rules. The pragmatic answer for most systems: reach for battle-tested concurrent structures from the standard library (concurrent maps, queues) before hand-rolling one, because correct lock-free code is genuinely expert territory.

A count-min sketch is a probabilistic structure that estimates the frequency of elements in a stream using sublinear memory. It's a 2D array of counters with several hash functions; each element increments one counter per row, and a query returns the minimum across those rows to reduce overcounting.

You reach for it when exact counts are too memory-expensive: finding heavy hitters in a huge traffic stream, tracking approximate frequencies for rate limiting, or trending-item detection. Like a bloom filter, it trades accuracy for space, it can overestimate but never underestimate, which is acceptable when an approximate top-k is enough.

A persistent data structure preserves previous versions when modified: updating it returns a new version while the old one stays valid and unchanged. Naively that means copying everything, which is too slow. The trick is structural sharing: the new version reuses most of the old one and only creates the nodes along the path that changed.

A persistent tree update copies just the O(log n) nodes from the changed leaf to the root and shares the rest. This backs functional languages' immutable collections, version control's history, undo systems, and Clojure's data structures. The payoff is cheap versioning and thread-safety by default, because nothing is ever mutated in place.

Use external merge sort. Read the data in chunks that fit in memory, sort each chunk, and write it back to disk as a sorted run. Then merge the sorted runs together with a k-way merge using a min-heap, reading a little from each run at a time and writing the merged output sequentially.

It's O(n log n) comparisons like in-memory sorting, but the design minimizes disk I/O by doing sequential reads and writes rather than random access. The number of merge passes depends on how many runs fit in memory at once. This is how databases and big-data tools sort terabytes on machines with gigabytes of RAM.

First, store it compactly: an adjacency list (or compressed formats like CSR, compressed sparse row) rather than a matrix, since real graphs are sparse. If it still won't fit, partition it across machines and process with a vertex-centric model (like Pregel or GraphX) where each vertex computes based on messages from its neighbors, iterating in supersteps.

The design pressure is minimizing cross-partition edges, because messages crossing machines are the bottleneck, so graph partitioning quality drives performance. For streaming-scale problems you may accept approximate answers (sampling, sketches) instead of exact traversals. The production signal is recognizing that at scale the algorithm choice bends around the memory and network layout, not the other way around.

A rolling hash computes the hash of a fixed-size window over a sequence, and when the window slides by one, updates the hash in O(1) by removing the outgoing element's contribution and adding the incoming one, instead of rehashing the whole window.

It powers the Rabin-Karp string search: to find a pattern in text, hash the pattern once and roll a same-size hash across the text, comparing full strings only when hashes match. Average O(n + m). Rolling hashes also drive content-defined chunking in deduplication and rsync-style diffing. The trade is handling hash collisions with a verification step.

A monotonic stack keeps its elements in sorted order (increasing or decreasing) by popping any element that would violate the order before pushing a new one. Because each element is pushed and popped at most once, a whole class of problems drops from O(n squared) to O(n).

It solves 'next greater element,' 'largest rectangle in a histogram,' 'daily temperatures,' and 'trapping rain water.' The pattern: as you scan, the stack holds candidates still waiting for their answer, and you resolve them the moment a qualifying element arrives. Recognizing that a problem asks for the nearest larger or smaller element in a sequence is the cue to reach for it.

A segment tree is a binary tree over an array where each node stores an aggregate (sum, min, max) of a range, so you can query the aggregate of any range and update any element, both in O(log n). Building it is O(n).

It's worth it when you have many interleaved range queries and point updates on the same array. A prefix-sum array answers range sums in O(1) but can't handle updates without an O(n) rebuild; a segment tree keeps both operations O(log n). Fenwick trees (binary indexed trees) do the same for simpler aggregates with less code and memory, so mention them as the lighter alternative when the aggregate is a sum.

Clarify first: how many queries per second, do results need ranking (by popularity), is the dataset static or updated live, and what latency budget? Those answers change the design. Then propose: a trie or compressed trie (radix tree) for prefix matching, with each node caching its top-k completions so a lookup returns ranked results without traversing the whole subtree.

The closing step is scale and operations: the trie can be sharded by prefix across machines, popularity scores feed the ranking, and for fuzzy matching you'd add edit-distance handling or an n-gram index. The technical sequence, clarify then core structure then ranking then scale, is what a advanced round is really scoring, not any single data structure.

Amortized O(1) means the average cost over many operations is constant, but individual operations can spike. A dynamic array's occasional doubling copies the whole array in one O(n) step, and a hash table's resize rehashes everything at once. That's fine for throughput but bad for latency-sensitive systems, where one request unluckily eats the full resize and blows the tail latency (p99).

The fix is to spread the expensive work out. Incremental resizing rehashes a few entries per operation instead of all at once, keeping every operation bounded, which is what low-latency stores and real-time systems do. The production insight is that amortized analysis optimizes total work, but tail latency cares about the worst single operation, so the two goals can conflict.