Data structure interviews reveal whether candidates can turn a problem into a clear representation, maintain its invariants and explain the cost of each operation. Recruiters should look beyond memorized complexity tables: strong candidates identify assumptions about input size, ordering, duplicates, memory and latency, then show how their choices behave when those assumptions change.
This guide to 100+ Data Structure Interview Questions and Answers covers 120 questions across beginner, intermediate and experienced levels. It moves from arrays, lists, hashing, trees and graphs to implementation exercises, augmented indexes, probabilistic structures, persistence and concurrency. Select questions that reflect the role: implementing a bounded work queue calls for different evidence than designing a storage index.
How can recruiters distinguish genuine data structure reasoning from a rehearsed explanation of a familiar coding problem?
Ask candidates to trace an operation, identify the invariant it preserves and adapt their solution to a changed constraint, such as duplicate values or a strict memory limit. A correct final answer is only one signal; the explanation should connect each update to the structure’s contract. Follow-up changes can reveal whether a candidate understands why the algorithm works or is repeating a memorized solution.
Sherlock AI helps hiring teams assess signals of potential AI cheating, deepfakes, impersonation and unauthorized assistance during remote interviews. Combine those signals with practical exercises and structured technical discussion when assessing independent ability. Signals should inform a fair review, rather than serve as conclusive proof of misconduct.
Data Structure Interview Questions
Use this bank to build an interview sequence appropriate to the role. Start with representations and operation costs, then explore implementation or workload trade-offs. Each question has an identically numbered answer below; select a relevant subset rather than attempting all 120 in one interview.
Data Structure Interview Questions for Beginners
Check whether candidates can distinguish an interface from its implementation and explain common structures with a small example. Follow up on the assumptions behind a claimed operation cost.
What is a data structure?
How does an abstract data type differ from its implementation?
How do linear and nonlinear data structures differ?
What does Big O notation describe?
How do Big Omega and Big Theta complement Big O?
What is the difference between time and auxiliary space complexity?
How do worst-case, average-case and amortized bounds differ?
Why is indexed array access constant time?
How does a dynamic array grow?
Why can inserting into the middle of an array be expensive?
When would you choose an array instead of a linked list?
What information does a singly linked list node contain?
How does a doubly linked list change the trade-offs?
What is a sentinel node used for?
What is a stack, and where is it useful?
What is a queue, and where is it useful?
How does a deque differ from a queue?
How does a circular buffer reuse storage?
What happens when a stack or queue is empty?
How is a priority queue different from a FIFO queue?
What is a hash table?
What is a hash collision?
How do chaining and open addressing handle collisions?
What is a hash table's load factor?
How do sets and maps differ?
Why must a hash key obey equality and hash rules?
What are the main parts of a rooted tree?
How do depth and height differ in a tree?
How do a binary tree and a binary search tree differ?
How does a balanced search tree improve lookup?
What is the min-heap invariant?
How is a binary heap represented in an array?
What are graph vertices and edges?
How do directed and undirected graphs differ?
How do adjacency lists and adjacency matrices compare?
What is breadth-first search?
What is depth-first search?
What does a trie store?
What is a sparse matrix representation?
How should you choose a data structure for a new problem?
Data Structure Interview Questions for Intermediate
Use implementation questions to probe update order, boundary cases and invariant preservation. A short hand trace often exposes a misunderstanding more clearly than a large coding exercise.
How would you reverse a singly linked list iteratively?
How can you detect a cycle in a linked list?
How would you find the middle of a linked list?
How would you merge two sorted linked lists?
How can a stack support constant-time minimum queries?
How can two stacks implement a queue?
How can a stack check balanced brackets?
Why is a deque useful for a sliding-window maximum?
What are lower bound and upper bound searches?
How can prefix sums accelerate range-sum queries?
How does a hash set help detect duplicate values?
How would you solve two-sum with a hash map?
How do you build a frequency table?
Why does open-addressing deletion need special handling?
Why must a double-hashing probe step be coprime to the table capacity?
How can you find the kth largest value efficiently?
Why can bottom-up heap construction run in linear time?
How would you merge k sorted streams?
How do preorder, inorder and postorder traversals differ?
How would you validate a binary search tree?
How do you delete a node with two children from a binary search tree?
What does a tree rotation preserve?
How would you return tree values level by level?
How would you serialize and deserialize a binary tree?
How does trie autocomplete work?
How do you reconstruct a shortest path found by BFS?
How can DFS detect a cycle in a directed graph?
What is topological ordering, and when does it exist?
How do you find connected components in an undirected graph?
What problem does disjoint-set union solve?
Why does Dijkstra's algorithm require nonnegative edge weights?
What is an indexed priority queue?
How can a Fenwick tree support dynamic prefix sums?
When would you use a segment tree?
What is coordinate compression?
How can a hash map and doubly linked list implement an LRU cache?
How can two heaps maintain a running median?
How do shallow and deep copies affect nested data structures?
Why can mutation invalidate an iterator?
What edge cases belong in data structure tests?
Data Structure Interview Questions for Experienced
Explore workload-driven design, memory behavior, concurrency and operational change. Ask what evidence would justify a more complex structure and what failure would invalidate the choice.
How would you evaluate a structure for a read-heavy, update-light workload?
Why might a theoretically faster structure run slower in practice?
How would you protect a hash-based service against adversarial collisions?
How can incremental rehashing reduce latency spikes?
When is a worst-case bound more important than an amortized bound?
How do AVL and red-black trees differ as engineering choices?
What does randomization buy in a treap or skip list?
How would you augment a tree for rank and select queries?
What invariant supports an interval tree for overlap queries?
Why do B-trees suit external storage?
How does a B+ tree differ from a typical B-tree?
When might a log-structured merge design beat an in-place tree index?
What guarantees does a Bloom filter provide?
How would you size a Bloom filter for a target false-positive rate?
When is a counting Bloom filter appropriate?
How does structural sharing support persistent data structures?
How can a hash array mapped trie implement an immutable map?
What is the ABA problem in a lock-free structure?
Why is memory reclamation difficult in lock-free linked structures?
What does linearizability mean for a concurrent queue?
How do lock-free and wait-free progress guarantees differ?
How would you make an LRU cache safe under concurrency?
How do snapshot reads trade memory for simpler concurrency?
When would you use a bounded ring buffer in production?
How would you design exact deduplication for an unbounded stream?
How should a streaming top-k design handle ties and updates?
How would you maintain a median over a sliding window?
When do compressed sparse row and coordinate formats fit different workloads?
How would you choose a graph representation for a very large sparse graph?
What is the trade-off in bidirectional BFS?
How do you choose a structure for range queries with frequent updates?
What can go wrong with lazy propagation in a segment tree?
When is rollback disjoint-set union useful?
How would you test a custom structure against a reference model?
What should a reliable data structure benchmark measure?
How would you investigate unexpected memory growth in a container?
How does key normalization affect correctness in an index?
How would you migrate from one index structure to another safely?
How do cache eviction and admission policies differ?
How would you review a data structure proposal before implementation?
Data Structure Interview Questions and Answers
The answers explain the representation, the invariant behind its behavior and the conditions under which its cost claims hold. Python examples use Python 3.13-compatible standard-library features. Unless a question says otherwise, complexity assumes conventional in-memory operations; expensive comparisons, hashing or storage access can change the practical cost.
Data Structure Interview Questions and Answers for Beginners
These answers connect basic definitions to concrete operations. Pay particular attention to the difference between worst-case, expected and amortized bounds and to what an interface actually promises.
1. What is a data structure?
A data structure organizes information so that required operations can be performed efficiently and correctly. An array supports direct indexed access; a search tree supports ordered lookup. Choosing a structure means choosing costs for reads, updates, memory, ordering and maintenance; there is no universally fastest container.
For example, storing customer records in a list makes it easy to preserve arrival order, but finding a customer by ID may require a scan. A hash map adds efficient key lookup, while a balanced search tree can also support ID ranges. The choice starts with the questions the application must answer, then accounts for the cost of keeping that representation up to date.
2. How does an abstract data type differ from its implementation?
An abstract data type specifies behavior, while a data structure implements that behavior. A queue promises first-in, first-out removal; an array-backed ring buffer and a linked queue can both satisfy it. Clients should depend on the queue contract, while implementers select storage according to capacity limits, allocation costs and concurrency requirements.
Suppose a task dispatcher uses only enqueue(task) and dequeue(). Its callers should continue to work if linked nodes are replaced with a ring buffer, provided the documented behavior remains the same. A fixed-capacity ring buffer introduces a full-buffer case, however; it cannot silently drop tasks if the original contract promised to retain them. Representation changes must preserve semantics, not just method names.
3. How do linear and nonlinear data structures differ?
A linear structure arranges elements into a sequence, such as an array or linked list. A nonlinear structure expresses branching or arbitrary relationships, such as a tree or graph. This distinction concerns logical relationships rather than physical memory: a heap is logically a tree even when stored in one contiguous array.
An employee reporting hierarchy is naturally a tree because each employee has one manager in that model. A dependency network with shared prerequisites is better represented as a graph: several tasks can point to the same prerequisite. Flattening either into an array can be useful for storage or traversal, but the relationships still need to be encoded and preserved.
4. What does Big O notation describe?
Big O gives an asymptotic upper bound on growth under a stated computational model. Saying a lookup is O(log n) describes how its work scales with input size, not an exact duration. Also identify whether the bound is worst-case, expected or amortized; those qualifiers answer different performance questions and should not be silently interchanged.
If doubling the input roughly doubles a full scan's comparisons, linear growth is a useful model. Binary search instead adds roughly one comparison when a sorted input doubles. Neither statement predicts milliseconds without considering implementation and hardware. Also, an O(n) upper bound does not by itself say that every execution examines all n entries; a successful scan may stop early.
5. How do Big Omega and Big Theta complement Big O?
Big Omega supplies an asymptotic lower bound, and Big Theta supplies matching upper and lower bounds. A full scan of n fixed-size entries takes Theta(n) work when each entry must be inspected. Although O(n squared) is also a valid upper bound, it is loose and hides useful information about the algorithm's actual growth.
For a search in an unsorted array, a match at the first position gives a best-case constant number of comparisons, while an absent key requires a linear scan. A worst-case Θ(n) statement and a best-case Θ(1) statement can therefore both be correct. Big Omega is not another name for best case, and Big O is not another name for worst case: the bound and the case are separate choices.
6. What is the difference between time and auxiliary space complexity?
Time complexity measures operations as input grows; auxiliary space measures additional storage beyond the input representation. An iterative array scan can take O(n) time and O(1) auxiliary space. A recursive traversal may need a call stack, so counting only explicitly allocated arrays understates memory use. State whether output storage is included in your analysis.
Consider copying an array of n values. Producing the copy needs linear output storage even if only a loop index is additional working state. Conversely, reversing the array by swapping its ends can use constant auxiliary space. In an interview, I would explicitly count recursion frames, temporary slices and output buffers so the complexity claim matches the actual code rather than an idealized algorithm.
7. How do worst-case, average-case and amortized bounds differ?
Worst-case analysis considers the most expensive input or operation of a given size. Average-case analysis depends on a specified input distribution. Amortized analysis bounds the total cost of a sequence without requiring random inputs. A growing array can have O(1) amortized append while an individual append still copies O(n) entries during expansion.
For dynamic-array appends, most operations write into a free slot, but occasionally an append triggers allocation and copying. Charging a small amount of that copying cost to each earlier append explains the constant amortized bound. It does not make the expensive append disappear: a latency-sensitive system may reserve capacity or choose a bounded buffer because one long pause still matters even when total throughput is good.
8. Why is indexed array access constant time?
For fixed-width elements, an array computes an address from its base address, index and element width using constant work. This assumes a valid index and a conventional random-access memory model. It does not imply every access has equal wall-clock latency: cache misses and page faults can make particular accesses much slower.
For an array of four-byte integers, element i begins at base + 4 * i; locating element 900 does not require visiting the preceding 900 elements. An array of references has the same constant-time slot lookup, but reading the referenced object may require another memory access. A linked list lacks that address formula because each next node must be found through the preceding node.
9. How does a dynamic array grow?
A typical dynamic array allocates a larger backing region when capacity is exhausted, copies existing entries and appends the new entry. Geometric growth keeps total copying linear across a long append sequence, yielding amortized constant-time append. Growing by one slot each time instead causes quadratic total copying. Exact growth factors are implementation-specific.
If capacities double from 1 to 2 to 4 to 8, the elements copied during expansion form a geometric series rather than a sum of every previous size. That is why geometric growth works. The trade-off is unused capacity and occasional allocation pauses. Knowing an approximate final size can justify reserving storage, but reserving an enormous upper bound wastes memory and may fail unnecessarily.
10. Why can inserting into the middle of an array be expensive?
A contiguous array must shift later elements to create a gap while preserving sequence order. Inserting at position i therefore moves up to n minus i entries, even if spare capacity exists. A resize can add another linear copy. If order is unnecessary, some deletion workloads can replace a removed entry with the last element.
Inserting X at index 1 of [A, B, C, D] requires moving B, C and D before writing X. Having an unused slot at the end avoids allocation, but not these shifts. For frequent ordered insertions, I would consider a different representation or batch changes; if insertions are rare and reads dominate, the array can still be the better overall choice.
11. When would you choose an array instead of a linked list?
Choose an array when indexed reads, compact storage and sequential iteration dominate. Contiguous entries generally improve locality and avoid a pointer per element. A linked list can make certain updates cheap when the relevant node is already known, but finding that node still costs time. Compare whole operations, including lookup, rather than isolated pointer rewiring.
For a million numeric readings that are scanned repeatedly, an array is usually a stronger starting point than individually allocated nodes. For an LRU cache, a doubly linked list can be useful because a map already provides the node to move or remove. That extra lookup mechanism is what makes the constant-time list update practically accessible; a bare linked list still has to search for the target.
12. What information does a singly linked list node contain?
A singly linked node contains a value and a reference to its successor. The list retains a head reference and may also retain a tail and size. A null successor marks the end in a conventional representation. Any operation that replaces the first node must update the head; forgetting that update can lose access to valid elements.
To prepend X to A → B, first make X.next refer to A, then move head to X. When removing the only node, both head and any retained tail must become empty. Keeping these ownership and boundary updates explicit prevents a list whose traversal appears correct but whose next append follows a stale tail.
13. How does a doubly linked list change the trade-offs?
A doubly linked node stores both previous and next references. With a node handle, unlinking it can update its neighbors in constant time without searching for its predecessor. The price is extra memory and more invariants during updates. Head, tail and singleton cases require care unless sentinel nodes deliberately simplify those boundaries.
For A ⇄ B ⇄ C, removing a known node B reconnects A.next to C and C.prev to A. Updating only one direction leaves a structure that behaves differently depending on traversal direction. This representation is useful for browser-history navigation or cache eviction lists, but it does not make searching for an unknown value constant time.
14. What is a sentinel node used for?
A sentinel is a structural placeholder that reduces special cases at boundaries. In a doubly linked list, permanent head and tail sentinels let insertion and removal follow the same neighbor-update pattern for many positions. Sentinels are not user data and must be excluded from counts and iteration. They simplify logic rather than changing asymptotic complexity.
With head and tail sentinels, an empty list is represented by head.next == tail and tail.prev == head. Inserting the first real node then resembles inserting between any two neighbors. The implementation still needs to protect the sentinels from removal and keep them out of results; exposing a dummy value to callers would turn an internal simplification into an API bug.
15. What is a stack, and where is it useful?
A stack removes the most recently inserted element first. Its push, pop and peek operations suit nested parsing, undo histories and explicit traversal state. The storage can be an array or linked nodes. Define empty-stack behavior explicitly, and distinguish a bounded stack's capacity overflow from a programming language's recursive call-stack exhaustion.
When checking nested brackets, an opening bracket is pushed and a closing bracket must match the current top. For ([ ]), the square bracket must close before the parenthesis; a queue would remove the wrong opening symbol. This illustrates why last-in, first-out behavior matters. A stack also needs a defined failure result when pop or peek is called with no elements.
16. What is a queue, and where is it useful?
A queue removes the earliest inserted remaining element first. It suits breadth-first exploration and ordered work buffering. Efficient implementations avoid shifting all elements on each removal by using links, a deque or a ring buffer. A queue's ordering contract alone does not define thread safety, capacity handling, persistence or delivery guarantees.
If jobs arrive as A, B, then C, a single consumer removes them in that order. With multiple workers, removal order does not guarantee completion order: B may finish while A is still running. I would distinguish that application-level requirement from FIFO storage, and avoid an array implementation that shifts every remaining job after each dequeue.
17. How does a deque differ from a queue?
A deque allows insertion and removal at both ends, whereas a conventional queue exposes enqueue at one end and dequeue at the other. This flexibility supports sliding-window algorithms and work scheduling. Efficient endpoint operations do not imply efficient random indexing; a deque's internal representation and API determine the costs of middle access and insertion.
The example below uses Python's deque as a FIFO queue: append at the right and remove from the left. It can also behave as a stack or accept urgent work at the other end. In Python, indexing is fast near either end but becomes linear toward the middle, so a deque should not be substituted for a list when frequent arbitrary indexed reads are the main operation.
18. How does a circular buffer reuse storage?
A circular buffer treats the end of a fixed-size backing array as adjacent to its beginning. Read and write positions advance modulo capacity, so consumed slots can be reused without shifting elements. Distinguish full from empty using a size counter, an extra state bit or an unused slot. Define whether a full buffer rejects, blocks or overwrites writes.
For capacity four, positions advance 0, 1, 2, 3, 0. If read and write positions are equal, they can mean either empty or full unless the design records additional information. A telemetry history may deliberately overwrite its oldest sample, whereas a work queue should generally reject or wait when full. The wraparound arithmetic is the same; the correctness contract is different.
19. What happens when a stack or queue is empty?
The API must report the absence of an element through an exception, optional result or explicit status. Returning an ordinary data value as a sentinel is unsafe if that value is also valid input. Test empty and singleton transitions because they expose head/tail mistakes. In concurrent code, an earlier emptiness check may become stale before removal.
If 0 is a valid queued value, returning 0 to mean “empty” makes the result ambiguous. An optional value, a success flag plus value, or an exception avoids that ambiguity. For a concurrent queue, prefer the API's atomic try-remove operation to if not empty: remove(); another consumer can remove the last item between those two separate calls.
20. How is a priority queue different from a FIFO queue?
A priority queue selects the next item according to priority, not arrival time. A scheduler might choose the earliest deadline or smallest cost. Equal priorities need a defined tie policy if stable behavior matters. A binary heap is a common implementation, but the abstract contract does not require a heap or provide fast arbitrary-key searches.
Suppose jobs have priorities 5, 1 and 3, where a smaller number means more urgent. A min-priority queue returns priority 1 first, even if it arrived last. When two jobs share priority 1, adding a monotonically increasing sequence number can provide FIFO tie-breaking. That explicit rule avoids relying on incidental heap layout and, in tuple-based implementations, avoids comparing payload objects that have no ordering.
21. What is a hash table?
A hash table maps a key through a hash function to a storage location or search starting point. It resolves collisions because different keys can map to the same place. Under suitable hashing and occupancy assumptions, operations can have expected constant cost. Hashing long keys and comparing colliding keys add costs that a simple O(1) statement can conceal.
For a user lookup keyed by integer ID, the table computes a hash, selects a bucket or probe sequence, and checks equality to find the exact key. Looking up an absent key follows the same resolution rules until absence is established. The expected constant-time claim normally treats key processing as constant cost; hashing a newly supplied long string can still require work proportional to its length.
22. What is a hash collision?
A collision occurs when distinct keys map to the same hash value or table bucket, depending on the terminology being used. It is an ordinary condition, not proof of corruption. The table must compare keys and use a collision-resolution scheme. A good hash function distributes typical keys well, but cannot eliminate collisions over a larger key domain.
If a toy table uses key % 8, keys 10 and 18 both start at slot 2. A correct lookup for 18 must distinguish it from 10 using equality rather than returning the first occupant. More buckets or a better hash distribution can reduce collision work, but correctness must hold even when collisions occur. Confusing a hash with a unique identifier is therefore a fundamental design mistake.
23. How do chaining and open addressing handle collisions?
Chaining stores multiple entries within a bucket, often through a linked or compact collection. Open addressing keeps entries in the table itself and probes other positions on collision. Chaining tolerates occupancy above one entry per bucket; open addressing requires spare slots. Their memory, locality, deletion and resizing behavior differ, so workload and implementation details matter.
With linear probing, deleting an entry cannot simply turn its slot into “never occupied”: doing so may cause a later lookup to stop before reaching another displaced key. Implementations use a suitable deletion strategy, such as tombstones or backward shifting. Chaining removes an entry from its bucket instead. These differences matter when comparing update-heavy workloads, not just successful lookup speed.
24. What is a hash table's load factor?
Load factor measures entries relative to available buckets or slots. Higher occupancy generally increases collision work, particularly for open addressing as the table approaches full. An implementation may resize at a threshold to control this cost. The appropriate threshold depends on the probing scheme and workload; there is no single universal value for all hash tables.
If 75 entries occupy a table with 100 buckets, the load factor is 0.75. That ratio does not reveal whether entries are evenly distributed or concentrated in a few buckets. I would inspect both occupancy and collision behavior when diagnosing a slowdown. Resizing creates more space, but it does not repair a hash function that systematically gives the same hash to the application's keys.
25. How do sets and maps differ?
A set stores distinct keys and answers membership questions; a map associates keys with values. Both may use hashing or ordered trees. For example, a set can track visited graph vertices, while a map stores each vertex's distance. Neither abstraction alone guarantees insertion order, sorted iteration or a particular complexity bound; those are implementation or API properties.
For deduplication, a set of seen email addresses is sufficient when the only question is whether an address has appeared. Counting occurrences requires a map from address to count. If results must be shown alphabetically, a hash-based representation may need a separate sorting step. Matching the abstraction to the required result avoids storing unused values or assuming an ordering the API never promised.
26. Why must a hash key obey equality and hash rules?
Keys that compare equal must produce equal hashes so the table can find the bucket where an equivalent key belongs. The reverse is unnecessary because collisions are valid. A key's equality-relevant state should remain stable while stored. Mutating that state can make an entry effectively unreachable even though the underlying object still exists in the table.
Imagine a key whose equality depends on an employee's department. If the department changes after insertion, a fresh lookup may compute a different hash and search a different bucket. The record can then be present but unfindable through normal lookup. Immutable key fields, stable surrogate IDs, or removing the entry before changing key state and reinserting it afterward are safer designs. Equal keys must hash equally; unequal keys may still share a hash.
27. What are the main parts of a rooted tree?
A rooted tree has one root and parent-child relationships leading to every other node, without cycles. Leaves have no children, and a subtree contains a node and its descendants. Except for the root, each node has one parent. Clarify whether the problem uses rooted or unrooted trees before applying terms such as ancestor or depth.
In a folder tree, the top-level folder is the root, each nested folder has one parent, and a file can be represented as a leaf. Moving a folder must not attach it beneath one of its own descendants, because that creates a cycle. If one object can have multiple parents, the model is no longer a tree even if the user interface displays it with indentation.
28. How do depth and height differ in a tree?
Depth measures distance from the root to a node; height measures the longest downward path from a node to a leaf. With edge-based counting, a leaf has height zero and the root has depth zero. Some sources count nodes instead, so state the convention before writing recurrence relations or asserting an exact height.
In the chain A → B → C, using edge counts, B has depth 1 and height 1; A has height 2 and C has height 0. Depth answers “how far from the root?”, while height answers “how far to the deepest leaf?”. The height assigned to an empty tree must also be stated, especially when implementing balancing rules or recursive base cases.
29. How do a binary tree and a binary search tree differ?
A binary tree limits each node to at most two children. A binary search tree adds an ordering invariant across entire subtrees, usually smaller keys on the left and larger keys on the right under a defined duplicate policy. A binary tree need not be ordered, and a binary search tree need not be balanced.
For a root key 10, placing 5 as its left child and 15 as its right child is not enough to prove the whole tree is a BST. A value 12 deeper inside the left subtree violates the root's ordering constraint even if its immediate parent relationship looks valid. Validation must carry allowed bounds through the traversal, and duplicate handling must agree with insertion and search.
30. How does a balanced search tree improve lookup?
A balanced search tree maintains height proportional to log n, so searching along one root-to-leaf path has logarithmic worst-case length. An ordinary unbalanced tree can degrade into a chain after ordered insertions. Balancing requires extra metadata and updates; the benefit is predictable path length rather than a guarantee of lower latency for every tiny dataset.
Inserting sorted keys 1, 2, 3, 4 into a naive BST can produce a right-leaning chain, so finding 4 visits every node. A self-balancing tree restores a height bound through operations such as rotations while preserving key order. This is valuable for predictable lookup and range traversal under changing data, but maintaining balance adds work that a static sorted array avoids.
31. What is the min-heap invariant?
In a min-heap, each parent's priority is no greater than its children's priorities, so the minimum is at the root. The heap need not be globally sorted, and siblings need no particular ordering. A binary heap additionally maintains a complete-tree shape, which supports compact array storage and logarithmic insertion and removal by repairing one path.
The array [1, 4, 2, 9, 7, 3] is a valid min-heap even though 4 appears before 2: every parent is at most its children. Reading the root gives the minimum in constant time; removing it requires repairing the heap. Searching for an arbitrary value can still require scanning many entries because heap order does not identify a single left-or-right search path as a BST does.
32. How is a binary heap represented in an array?
With zero-based indexing, node i has children at 2i plus 1 and 2i plus 2 when those indices exist, and a nonroot parent at floor((i minus 1) divided by 2). The complete-tree shape avoids holes. These formulas are representation rules; they do not by themselves establish the priority-order invariant, which updates must preserve.
In [2, 5, 4, 9, 7], index 1 holds 5, with children at indices 3 and 4 holding 9 and 7. Appending a new item preserves the complete shape, after which it may need to move upward to restore heap order. Removing the root commonly moves the last item to index 0, then moves it downward. Shape maintenance and priority maintenance are separate steps.
33. What are graph vertices and edges?
Vertices represent entities and edges represent relationships between them. A graph can model dependencies, routes or social connections. Specify whether edges are directed, weighted and possibly parallel, and whether self-loops are allowed. Those choices change valid representations and algorithms; a simple undirected graph model cannot express every problem without losing information.
For a build system, a vertex can represent a target and an edge can represent a prerequisite relationship. I would define the edge direction explicitly before computing an order: “target points to prerequisite” and “prerequisite points to dependent” require different interpretations. An isolated target must still be represented even though it has no edges, otherwise a traversal based only on relationships could silently omit it.
34. How do directed and undirected graphs differ?
A directed edge connects an ordered pair, so an edge from A to B does not imply travel from B to A. An undirected edge represents a symmetric connection. Directed graphs distinguish incoming and outgoing neighbors and degrees. For adjacency-list storage, an undirected edge is commonly represented in both endpoint lists, which must stay consistent during updates.
A road network with one-way streets needs directed edges; friendship may be modeled as undirected if the relationship is mutual. For an undirected edge A—B, storing B in A's neighbor list but forgetting A in B's list produces inconsistent reachability. A directed graph instead permits that asymmetry intentionally, so algorithms and validation must use the declared model.
35. How do adjacency lists and adjacency matrices compare?
Adjacency lists usually use O(V plus E) storage and make neighbor iteration proportional to degree. A full adjacency matrix uses O(V squared) entries and supports constant-time edge-presence checks. Lists usually suit sparse graphs; matrices can suit dense graphs or matrix operations. A weighted matrix needs an unambiguous representation for a missing edge versus a zero-weight edge.
For a graph with one million vertices and only a few neighbors per vertex, allocating a full matrix is usually impractical even though checking a single edge would be simple. An adjacency list stores only the present connections. Conversely, a compact matrix or bitset can be useful for dense graphs with many edge-existence queries. The table summarizes typical costs; the container used for each neighbor list can change lookup cost.
Operation or property | Adjacency list | Full adjacency matrix |
|---|---|---|
Storage | O(V + E) | O(V²) |
Iterate neighbors of v | O(degree(v)) | O(V) |
Check an edge | O(degree(v)) for an unsorted list | O(1) |
36. What is breadth-first search?
Breadth-first search explores vertices in increasing number of edges from its starting point, using a FIFO frontier. On an unweighted graph, first-discovery distances are shortest path lengths in edges. Mark vertices when enqueuing to avoid repeated work. With adjacency lists, a traversal over the reachable region is linear in its vertices and edges.
Starting at A with neighbors B and C, BFS processes both distance-one vertices before their distance-two neighbors. Recording each vertex's parent on discovery allows reconstruction of a shortest path. The shortest-path guarantee is about edge count, not arbitrary weighted cost: a one-edge route costing 100 can be more expensive than a two-edge route costing 2. Weighted problems need an appropriate different algorithm.
37. What is depth-first search?
Depth-first search follows a path as far as possible before backtracking, using recursion or an explicit stack. It is useful for connectivity, cycle detection and ordering tasks. A visited structure prevents endless revisits in cyclic graphs. The exact traversal order depends on neighbor order, and a naive recursive implementation can exhaust the call stack on deep inputs.
In a dependency graph, DFS can remember which vertices are on the active recursion path as well as which were previously visited. An edge back to an active ancestor reveals a directed cycle; an edge to any previously visited vertex alone does not. For very deep graphs, an explicit stack avoids recursion-depth failure, though it still needs enough memory to represent the pending traversal state.
38. What does a trie store?
A trie organizes keys by successive symbols, sharing common prefixes. Searching a key follows one edge per symbol when child lookup is constant-time under the chosen representation. A terminal marker distinguishes a stored word from a prefix. Tries support prefix searches naturally but may consume substantial memory through sparse child containers and per-node overhead.
Storing car and cart shares the path for c, a and r. The node after r must mark the end of car, even though it also has a child for t. A prefix query for car then starts at that node and enumerates descendants. Unicode normalization and what counts as a symbol must be defined if the keys are user-entered text.
39. What is a sparse matrix representation?
A sparse representation stores primarily the nonzero entries and their positions, saving space when most values are zero. Coordinate triples are easy to build; compressed row formats make row-oriented computation efficient. Insertions and random updates may be expensive after compression. The best format depends on the operations, not just the fraction of entries that are nonzero.
For a 1,000-by-1,000 matrix with only ten nonzero values per row, storing every zero is unnecessary. A compressed sparse row representation groups each row's values and column indices, with offsets marking row boundaries. This makes row scans efficient, but inserting a new entry into the middle can require rebuilding packed arrays. Building coordinate triples first and converting after construction is often a better fit for batch workloads.
40. How should you choose a data structure for a new problem?
List the required operations, their frequencies, input sizes and correctness constraints before choosing storage. Ask whether ordering, duplicates, range queries, stable references or bounded latency matter. Compare candidate costs including memory and maintenance, then test representative workloads. A simpler structure can outperform a sophisticated one when constants, locality or a small input dominate.
For example, a leaderboard that needs only the current top ten differs from one that must answer every player's exact rank and arbitrary score ranges. A small heap may suit the first requirement, while an ordered structure with additional rank information may suit the second. I would describe the expected workload, justify the operation costs, and test the cases that could invalidate the choice, such as skewed keys or sudden growth.
Data Structure Interview Questions and Answers for Intermediate
The examples develop algorithmic choices step by step, including why an update is safe and what information must be retained. Ask candidates to explain the edge case before changing the input or operation contract.
41. How would you reverse a singly linked list iteratively?
I would reverse the links in place using three references: the already reversed prefix, the current node, and its original successor. Saving the successor before overwriting current.next is the critical step; otherwise the rest of the list becomes unreachable through the traversal.
For 1 → 2 → 3, the first iteration produces 1 → None while the unprocessed suffix still begins at 2. Each iteration extends that reversed prefix by one node. The final previous reference is the new head:
The assertions cover a normal list and an empty input. The algorithm visits each node once, taking O(n) time and O(1) auxiliary space. It mutates the original nodes, so other references to them observe the changed links. The input must be acyclic; detecting or accepting cycles requires a different contract.
42. How can you detect a cycle in a linked list?
Floyd's cycle-detection algorithm moves a slow pointer one link and a fast pointer two links at a time. If the fast pointer reaches None, the list ends. If the pointers refer to the same node, there is a cycle. Compare node identity, not stored values: two separate nodes containing 7 do not form a cycle.
Once both pointers enter a cycle, the faster pointer gains one position per iteration relative to the slower one, so it must eventually catch it. This gives O(n) time and O(1) additional space. For A → B → C → B, the pointers meet inside the B–C cycle rather than reaching a null link.
If the interviewer also wants the cycle's entry, reset one pointer to the head after the meeting and advance both one step at a time; their next meeting identifies the entry. Keep detection and repair separate, since breaking a link changes shared structure.
43. How would you find the middle of a linked list?
Use a slow pointer advancing one node and a fast pointer advancing two. With both starting at the head and a loop that continues while fast and fast.next exist, the slow pointer ends at the middle for odd lengths and the second middle for even lengths.
For 1 → 2 → 3 → 4, that convention returns node 3. If splitting the list into two halves requires the first middle, start the fast pointer one node ahead or adjust the loop condition. State this choice before coding because both conventions are reasonable and produce different boundary results.
The method takes O(n) time without a preliminary length pass and O(1) extra space. An empty list returns no node; a singleton returns its head. It assumes an acyclic list, since neither pointer is guaranteed to reach an end in a cycle.
44. How would you merge two sorted linked lists?
Maintain a tail for the result and repeatedly link the smaller current input node after it. A dummy head removes the special case for the first attachment. When either input ends, attach the other list's remaining suffix; it is already sorted and needs no further comparisons.
Merging 1 → 4 with 2 → 3 selects 1, then 2, then 3, and finally appends 4. Choosing the left input on equal keys preserves the relative order of equal nodes within a stable merge. For lengths m and n, the operation takes O(m + n) time and O(1) auxiliary pointer storage when nodes are reused.
Relinking consumes the original list structure. If callers need the originals unchanged, allocate result nodes instead. Also establish that the inputs do not share a tail: treating a shared node as two independent inputs can create incorrect links or cycles.
45. How can a stack support constant-time minimum queries?
Store each stack entry together with the minimum at that depth. On push, record min(value, previous_minimum); on pop, remove the pair. The current minimum is simply the second component of the top entry, so push, pop and minimum lookup all take O(1) time.
Pushing 5, 2 and 2 produces (5,5), (2,2), (2,2). Popping one 2 leaves a minimum of 2; popping the second restores 5. This is why keeping only a single mutable minimum is insufficient: it loses the earlier state when the minimum is removed.
A separate minima stack is another design, but it must record duplicate minima or maintain their counts. The paired representation is simpler to verify and uses O(n) extra storage. Define the response to a minimum query on an empty stack, such as an exception or an explicit optional result.
46. How can two stacks implement a queue?
Use an input stack for enqueues and an output stack for dequeues. When the output stack is empty, move every input item onto it. This reversal puts the oldest item on top. Do not transfer merely because a new item arrived; existing output items must leave first to preserve FIFO order.
Enqueueing A, B and C gives an input stack with C on top. The first dequeue transfers them and returns A. If D is then enqueued, subsequent dequeues still return B and C before D. Each element is pushed onto the input stack, transferred at most once, and eventually popped from the output stack.
That accounting gives amortized O(1) work per operation, with O(n) storage. The dequeue that triggers a transfer can take O(n), however. For a system with strict per-request latency bounds, the amortized result alone does not establish that this implementation is suitable.
47. How can a stack check balanced brackets?
A stack records unmatched opening brackets. Each closing bracket must match the most recent opener, because nested expressions close from the inside out. Reject a closing bracket when the stack is empty or its type differs from the top; after the scan, reject any remaining openers.
The following implementation ignores nonbracket characters. It correctly rejects ([)], even though the total counts of each bracket type match, because the closing order violates nesting:
Each character is examined once, so time is O(n); stack space is O(d), where d is the maximum nesting depth. This is a bracket checker, not a parser for a programming language: it does not understand quoted strings or comments. A language-aware checker would first distinguish syntax brackets from bracket characters inside those constructs.
48. Why is a deque useful for a sliding-window maximum?
Maintain a deque of candidate indices, ordered so their values decrease from front to back. Before processing a new value, remove expired indices from the front. Then remove indices from the back whose values are no greater than the new value: the new candidate is at least as good and will expire later.
For [2, 2, 1, 3, 0] with a window of three, the maxima are [2, 3, 3]. Keeping indices makes expiration unambiguous even when values repeat:
Each index is appended once and removed at most once, giving O(n) total time and O(k) candidate storage, excluding the result. Using <= in the back-removal condition keeps the newest equal candidate; retaining older equal values can also work if expiration remains correct. The function explicitly rejects empty or oversized windows rather than inventing a result.
49. What are lower bound and upper bound searches?
A lower bound is the first position whose value is at least the target; an upper bound is the first position whose value is greater. In a sorted sequence, their difference counts the target's occurrences. Python exposes these insertion positions through bisect_left and bisect_right.
For [1, 3, 3, 3, 8], the bounds for 3 are 1 and 4, so there are three matches. Searching for 9 returns position 5, just beyond the last element:
An insertion position is not proof of membership. Check i < len(values) and values[i] == target before reporting a match. Binary search takes O(log n) comparisons on this list, but insertion into the list still costs O(n) because later elements move. Keep the ordering consistent and do not mutate the sequence concurrently with the search.
50. How can prefix sums accelerate range-sum queries?
Build a cumulative-sum array with an initial zero: prefix[i] is the sum of the first i input values. The sum of the half-open range [left, right) is then prefix[right] - prefix[left], because subtracting removes exactly the prefix before the requested range.
The leading zero makes a range starting at index zero and an empty range use the same formula. In this example, indices 1 and 2 contain −1 and 7, so their sum is 6:
Construction takes O(n) time and space, followed by O(1) range queries. A point change can invalidate every later prefix, making ordinary prefix sums a poor fit for frequent updates; a Fenwick tree trades logarithmic queries for efficient updates. Fixed-width numeric types may overflow, and floating-point prefix subtraction can lose precision when two large totals are close.
51. How does a hash set help detect duplicate values?
Scan the sequence while storing previously encountered values in a hash set. If a value is already present, return that a duplicate exists; otherwise insert it. With suitable hashing and bounded-cost key operations, this requires expected O(n) time and O(n) additional space in the no-duplicate case.
For [8, 3, 8], the set becomes {8}, then {8, 3}; the final lookup detects the repeated 8. Unlike comparing only adjacent elements, this works without sorting the original sequence. It also allows an early answer as soon as any duplicate appears.
The keys must have stable equality and hashing semantics. If memory is tight and input mutation is allowed, sorting and checking neighboring values may be preferable. If the requirement is to report every duplicate with its count, a frequency map is more appropriate than an early-return set scan.
52. How would you solve two-sum with a hash map?
For each value, look up its complement, target - value, in a map of earlier values to indices. If found, the two indices form a valid pair. Only then insert the current value. Checking first prevents the same position from being used twice.
The distinction matters for target 6: [3] has no pair, while [3, 3] does. The second 3 finds the first one's index:
This returns one pair in expected O(n) time and O(n) space under ordinary hashing assumptions. Overwriting an earlier index is acceptable for this one-pair contract, but returning all index pairs requires retaining multiplicities and may produce quadratic output. Also define no-match behavior explicitly; this implementation returns None.
53. How do you build a frequency table?
A frequency table maps each distinct value to its number of occurrences. Increment the relevant entry while scanning the input. Unlike a set, it preserves multiplicity: the sequence [red, blue, red] becomes counts of two for red and one for blue.
This supports tasks such as comparing multisets, identifying the most common event type, or decrementing counts as a sliding window moves. For a small fixed domain, such as byte values 0–255, an array of 256 counters avoids hashing overhead and provides direct indexing. A map is more flexible for sparse or unknown keys.
Decide whether zero-count entries should remain after removals and reject invalid decrements if negative counts have no meaning. Counts may overflow fixed-width integers in long-running systems. For a streaming workload with many distinct keys, memory grows with the number of distinct values, even if processing each event is inexpensive.
54. Why does open-addressing deletion need special handling?
In open addressing, a lookup follows a probe sequence until it finds the key or a slot that has never been occupied. Simply marking a deleted slot as never used can break that search path and hide keys inserted farther along it.
Suppose two colliding keys A and B occupy consecutive positions. After deleting A, a search for B still needs to pass through A's former slot. A tombstone marks that position as deleted while telling lookup to continue. Insertion may reuse it, but must still follow the scheme's rules for detecting an already-present key.
Tombstones preserve correctness but accumulate probe overhead, so a table may rebuild even when the live-key count is modest. Backward-shift deletion can repair clusters in suitable linear-probing implementations, but is not a universal replacement for tombstones. The deletion algorithm must be derived from the actual probing strategy.
55. Why must a double-hashing probe step be coprime to the table capacity?
With double hashing, successive slots have the form (start + i * step) % capacity. The step must be coprime to the capacity so the sequence can visit every slot before returning to its starting point. Otherwise, insertion can fail while reachable-by-other-probes slots remain empty.
For capacity 10 and step 2, a probe starting at zero visits only 0, 2, 4, 6, 8. Step 3 instead visits all ten slots. A prime capacity with a step between 1 and capacity minus one is one way to satisfy the condition; a power-of-two capacity requires an odd step.
The second hash must never produce a zero step. Even with a valid step, stop after a bounded number of probes so a full table terminates cleanly. Good coverage does not remove the need for an appropriate load factor or well-distributed hash functions.
56. How can you find the kth largest value efficiently?
Keep a min-heap of the largest k values seen so far. While it has fewer than k entries, insert values. Once full, discard an incoming value unless it exceeds the root; if it does, replace the root. The root is the smallest of the retained top k values, hence the kth largest.
This version counts repeated values as separate ranks. Therefore the second-largest element of [5, 1, 5, 3] is 5, not 3:
The scan uses O(n log(k + 1)) time and O(k) storage. It is useful when k is small or values arrive incrementally, whereas selection algorithms may be preferable for a complete mutable array. Distinct-value ranking is a different requirement and needs deduplication. Reject k outside the available input length rather than returning a partial rank.
57. Why can bottom-up heap construction run in linear time?
Bottom-up heap construction calls sift-down on internal nodes from the last parent back to the root. Its total work is O(n) because most nodes are near the leaves and can move only a small distance. Charging every node the root's O(log n) repair cost overestimates the work.
Roughly half the nodes are leaves and need no repair; about a quarter can move one level, about an eighth two levels, and so on. Summing those weighted heights gives a linear bound. Python's heapq.heapify uses a linear-time construction rather than repeatedly inserting into an initially empty heap.
A heap is only partially ordered. After heapification, the root is the minimum, but neighboring array positions are not necessarily sorted. Extracting every item to obtain sorted output still takes O(n log n) overall, so linear heap construction does not imply a linear-time comparison sort.
58. How would you merge k sorted streams?
Place the first item from each nonempty sorted stream in a min-heap. Repeatedly emit the smallest entry and replace it with the next item from the same stream, removing that stream's entry when it ends. The heap holds only the current frontier, not every input item.
Merging [1, 4], [2, 5] and [3, 6] begins with heads 1, 2 and 3. Emitting 1 exposes 4, so the next minimum remains 2. A tuple such as (sort_key, unique_counter, payload) avoids comparing incompatible payloads when keys tie; choose a tie-breaker consistent with any required stability.
For N items across k streams, heap initialization and merging take O(k + N log(k + 1)) time and O(k) frontier space. Every stream must already be ordered by the same comparator. If remote streams can block, ordering and backpressure need explicit coordination rather than assuming the heap solves delivery latency.
59. How do preorder, inorder and postorder traversals differ?
Preorder visits a node before its children, inorder visits between the left and right subtrees, and postorder visits after its children. The choice depends on when the parent can be processed relative to its descendants.
For a root 2 with left child 1 and right child 3, preorder is 2, 1, 3, inorder is 1, 2, 3, and postorder is 1, 3, 2. Inorder produces sorted keys only if the tree satisfies the binary-search-tree invariant. An arbitrary binary tree offers no such guarantee.
Preorder is useful for writing a structural representation when null markers are included; postorder suits computing subtree sizes because child results are ready before their parent. Recursive traversal takes O(h) call-stack space for height h, which can become O(n) on a skewed tree. Inorder requires a defined extension if the tree has more than two children.
60. How would you validate a binary search tree?
Validate each node against the range allowed by all its ancestors, then narrow that range when descending left or right. Checking only that a node exceeds its left child and is below its right child is insufficient.
For example, a root 10 may have a left child 5 whose right child is 12. The local relationship between 5 and 12 is valid, but 12 violates the requirement that every value in 10's left subtree be below 10. Passing an upper bound of 10 down that entire subtree catches the error.
Define duplicate handling first: strict unique keys require strict bounds, while a duplicate policy changes permitted comparisons. Represent missing bounds explicitly rather than inventing numeric sentinels that may exclude valid extreme or nonnumeric keys. Validation is O(n) time and O(h) traversal space; an iterative stack avoids language recursion-depth limits.
61. How do you delete a node with two children from a binary search tree?
For a node with two children, choose its inorder successor—the minimum node in its right subtree—or its predecessor from the left subtree. Move that replacement's key and associated value into the target, then remove the replacement from its original location, where it has at most one child.
If deleting 10 and its successor is 12, replacing 10 with 12 preserves ordering because no remaining key in the right subtree is smaller than 12. Removing the original successor then reconnects its possible right child. The search and structural deletion take O(h) time before any balancing work.
Update parent pointers and augmented values such as subtree sizes along affected paths. AVL or red-black trees also require their balancing rules. If callers hold references to nodes, copying payloads changes what the target node represents; physically transplanting nodes may better match the API's identity guarantees.
62. What does a tree rotation preserve?
A rotation changes a small part of the tree's shape while preserving its inorder sequence. In a left rotation around x, x's right child y moves up, x becomes y's left child, and y's former left subtree becomes x's right subtree.
That middle subtree fits in its new location because all its keys lie between x and y. The transformation therefore preserves binary-search ordering while changing subtree heights. AVL and red-black balancing algorithms use rotations as local repair operations, sometimes combining two rotations to address a particular shape.
The implementation must reconnect the rotated subtree to its former parent, update the root when necessary, and repair parent links. Recompute augmented metadata in dependency order, usually the demoted node before the promoted node. A correct rotation alone does not establish a balanced tree; the surrounding algorithm must choose the right case and maintain its other invariants.
63. How would you return tree values level by level?
Use breadth-first traversal with a queue. At the beginning of each level, record the queue's current length and process exactly that many nodes into one result list. Enqueue their children for the next level. This separates levels without embedding artificial marker nodes in the queue.
For a root A with children B and C, and D below B, the output is [[A], [B, C], [D]]. Capturing the queue length before the inner loop matters: children appended during that loop belong to the next level, even though they are already in the queue.
The traversal takes O(n) time and O(w) auxiliary queue space, where w is the tree's maximum width, excluding the output. An empty tree returns an empty list. A wide shallow tree can require much more queue memory than its height suggests, which is the opposite of a depth-first traversal's stack trade-off.
64. How would you serialize and deserialize a binary tree?
Serialize both node values and structure. One straightforward format is preorder traversal with a reserved marker for every missing child. For example, [1, 2, null, null, 3, null, null] records a root 1 with children 2 and 3; the nulls tell the decoder exactly where each subtree ends.
A plain sequence of values cannot uniquely reconstruct an arbitrary binary tree. Deserialization of the marked format consumes one value, then recursively constructs its left and right children unless that value is a null marker. A structured encoding must distinguish an actual null payload from the structural marker if null payloads are legal.
Reject missing and trailing tokens rather than silently accepting partial data. Specify value types and escaping, and limit input size and depth for untrusted data. Both operations are O(n), but recursive implementations can overflow the call stack on deeply skewed trees, so an explicit stack may be appropriate.
65. How does trie autocomplete work?
First follow the prefix through the trie. If that path does not exist, there are no completions. Otherwise, traverse descendants and emit keys at terminal nodes, retaining the accumulated characters. A terminal marker matters because a key such as car can end at a node that also leads to cart.
For prefix ca, a trie containing car, cart and cat can enumerate all three without examining an unrelated dog branch. Prefix navigation depends on prefix length and child-lookup cost; producing completions also costs time proportional to the visited subtree and output size.
A common prefix may still expose millions of candidates. Limit results or maintain ranking information when the product needs the most popular suggestions, because ordinary traversal order is not popularity order. Unicode normalization and case-folding choices must also match how keys were inserted.
66. How do you reconstruct a shortest path found by BFS?
When BFS first discovers a vertex, record which vertex discovered it. Once the target is reached, follow those predecessor links backward to the source and reverse the resulting list. Mark discovery when enqueueing so another incoming edge does not overwrite the predecessor or repeatedly queue the same vertex.
In this unweighted graph, A reaches D through B or C in two edges. Neighbor order selects the B route; both have minimum edge count:
BFS visits vertices in nondecreasing distance from the source, which makes the first-discovery predecessor chain a shortest path. With adjacency lists, traversal is O(V + E), plus O(L) to reconstruct a path of L vertices. The fixture reserves None as the root marker and uses string vertices. Weighted edges require a different shortest-path method unless all weights are equal.
67. How can DFS detect a cycle in a directed graph?
Use three states: unvisited, active in the current DFS path, and completely processed. An edge to an active vertex is a back edge to an ancestor, proving a directed cycle. An edge to a completed vertex is not enough, because two independent paths may legitimately converge on the same destination.
For edges A → B, A → C and C → B, B may already be completed when C reaches it, yet the graph is acyclic. By contrast, adding B → A reaches an active ancestor while exploring B and closes a cycle.
Mark a vertex completed only after all its outgoing edges are examined. In iterative DFS, represent entry and exit events or retain an iterator for each active frame; a plain visited set loses the active-path distinction. Process every unvisited starting vertex to detect cycles in disconnected regions. The adjacency-list algorithm runs in O(V + E) time.
68. What is topological ordering, and when does it exist?
A topological ordering places every directed edge's source before its destination. Such an ordering exists exactly when the graph is acyclic. Kahn's algorithm repeatedly selects a zero-indegree vertex, emits it, and removes its outgoing edges by decrementing the affected indegrees.
In a build pipeline, build → test → release means each prerequisite must precede its dependent. The implementation also includes vertices that appear only as neighbors:
If fewer vertices are emitted than exist, a cycle prevents the remaining dependencies from being resolved; the code rejects that input. Several zero-indegree choices can produce different valid orders, so tests should verify every edge's ordering rather than require one arbitrary sequence. Time is O(V + E) with a queue. Using a heap to enforce a particular tie order adds priority-queue overhead.
69. How do you find connected components in an undirected graph?
For each unvisited vertex, start BFS or DFS and label every reachable vertex with the same component identifier. Then choose another unvisited vertex and repeat. In an undirected graph, reachability partitions the vertices into disjoint connected components.
If edges connect A–B and C–D while E has no edges, there are three components: {A, B}, {C, D} and {E}. Include isolated vertices in the graph's vertex collection; an edge-only representation can otherwise make them disappear from the result.
Across all traversals, an adjacency-list implementation takes O(V + E) time and O(V) visited storage. For a directed graph, clarify the intended definition before reusing this algorithm. Weak components ignore direction, while strongly connected components require mutual directed reachability and need an algorithm such as Tarjan's or Kosaraju's.
70. What problem does disjoint-set union solve?
Disjoint-set union maintains a partition of elements into nonoverlapping sets. find returns a representative, and union combines two sets. It answers whether two vertices are connected as undirected edges are added, without repeatedly traversing the whole graph.
Union by size attaches the smaller tree under the larger. Path compression shortens later searches; this implementation uses path halving:
The assertions show that adding edges 0–1 and 1–2 connects 0 to 2, while 3 remains separate. Combining these heuristics gives O(α(n)) amortized cost per operation, where α grows extremely slowly; it is not a strict constant-time worst-case claim. Basic DSU does not support arbitrary edge deletions or return an actual path. The representative is an internal choice, not necessarily the smallest element or a stable business identifier.
71. Why does Dijkstra's algorithm require nonnegative edge weights?
Dijkstra finalizes the unsettled vertex with the smallest tentative distance. With nonnegative weights, extending any other path cannot make it shorter than that finalized distance. A negative edge breaks this argument, so a later route can improve a vertex that the algorithm has already treated as complete.
Consider S → A with weight 2, S → B with weight 5, and B → A with weight −10. A standard settling implementation finalizes A at 2 before processing B, even though the path through B costs −5. Zero-weight edges are allowed; negative ones are the problem.
Use an appropriate algorithm such as Bellman–Ford when negative weights are possible. Distinguish an unreachable target from a target with no finite minimum: the latter occurs when a negative cycle is reachable from the source and can also reach that target. A negative cycle elsewhere need not affect every destination.
72. What is an indexed priority queue?
An indexed priority queue maintains both a heap and a mapping from item IDs to their heap positions. This permits finding a known item's slot directly, changing its priority, and restoring heap order in O(log n). Every heap swap must update the mapping as well as the array.
For a scheduler, a job ID can identify a pending task whose priority changes without searching all queued tasks. After decreasing a key in a min-heap, sift it upward; an increased key may need to move downward. Removing a known item typically replaces it with the final heap element and repairs the affected position.
Without the index, locating an arbitrary item can cost O(n). A simpler alternative is to push a new priority entry and discard obsolete entries when popped. That avoids position bookkeeping but grows the heap and requires a reliable way to recognize stale entries. Choose based on update frequency, memory limits and implementation complexity.
73. How can a Fenwick tree support dynamic prefix sums?
A Fenwick tree stores partial sums so both a point update and a prefix query visit O(log n) array positions. Its one-based internal indexing uses the least significant set bit: updates add i & -i, while queries subtract it. A range sum is the difference between two prefix sums.
This interface accepts zero-based point indices and half-open prefix endpoints, converting indices internally. Updating index 1 by 5 changes the queried range sum from 6 to 11:
The structure uses O(n) storage. Its purpose is to handle interleaved updates and queries more efficiently than rebuilding ordinary prefix sums. Starting the internal update loop at zero would never advance, so the index conversion is part of correctness. This sum implementation accepts deltas; assigning an absolute value requires knowing the old value and applying the difference.
74. When would you use a segment tree?
A segment tree stores an aggregate for each interval and combines child intervals to answer range queries. It supports O(log n) point updates and range queries with O(n) storage when the combination operation is associative and has a suitable identity value.
For a range-minimum query, combine children with min and use positive infinity for an empty contribution. For sums, use addition and zero. The tree is useful when values change frequently or the aggregate does not fit a simpler prefix-difference approach; minimum, for example, cannot generally be recovered by subtracting two prefix minima.
Lazy propagation extends some implementations to range updates by postponing work on descendants. The tag must correctly transform the stored aggregate and compose with earlier tags: adding d to every element changes a segment sum by d times its length. Range assignment and range addition require carefully ordered tag composition rather than a generic reusable flag.
75. What is coordinate compression?
Coordinate compression maps sorted distinct values to consecutive ranks. For values [100, 1000000, 100], the distinct ordering is [100, 1000000], so the compressed sequence is [0, 1, 0]. Equal values remain equal and relative ordering is preserved.
This makes array-based structures such as Fenwick trees practical for sparse, large identifiers or coordinates. Sorting typically costs O(n log n), after which a value-to-rank map supports lookup. It works naturally when all relevant coordinates are known before processing; an online stream of unseen values may need a different indexing strategy.
Compression does not preserve distance. The rank difference between 100 and 1000000 is one, but their numeric gap is 999900. Keep the original sorted coordinates when computing geometric lengths, interval coverage or distance-based results. Compressing endpoints alone is insufficient if the aggregate depends on the width between neighboring coordinates.
76. How can a hash map and doubly linked list implement an LRU cache?
Use a hash map from keys to list nodes and a doubly linked list ordered by recency. A cache hit moves its node to the most-recent end. When inserting beyond capacity, remove the least-recent node from the opposite end and delete its map entry. The map locates a node; the list changes its position without a search.
With capacity two, inserting A and B, reading A, then inserting C must evict B. Updating A's existing value should move the same logical entry rather than create a duplicate list node. Sentinel head and tail nodes can simplify unlinking at the ends.
Operations are expected O(1) under ordinary hashing assumptions. Maintain the invariant that the map and list contain exactly the same live keys. Define zero-capacity behavior and synchronize compound operations under concurrency; a thread-safe map alone does not make the list update and eviction atomic.
77. How can two heaps maintain a running median?
Maintain the lower half of the values in a max-heap and the upper half in a min-heap. Every lower-half value must be no greater than every upper-half value, and heap sizes differ by at most one. Insert into the appropriate half, then move a root across if rebalancing is needed.
After values 2, 8, 3, the lower half can contain 2 and 3 while the upper half contains 8; the median is 3. Adding 9 produces two equally sized halves, so the usual numeric median is (3 + 8) / 2 = 5.5. In Python 3.13, negated numeric values can implement the lower max-heap using heapq.
Insertion takes O(log n), median lookup O(1), and storage O(n). Agree whether even-sized inputs require an average or a lower/upper median. Fixed-width arithmetic needs overflow-safe averaging. Efficient deletion for a sliding-window median requires additional bookkeeping beyond these insertion-only heaps.
78. How do shallow and deep copies affect nested data structures?
A shallow copy creates a new outer container but keeps references to the same nested objects. A deep copy recursively duplicates supported referenced objects, usually using memoization to handle cycles and preserve sharing relationships within the copied graph.
For original = [[1], [2]], copy = original.copy() creates a different outer list. Appending a new row to copy does not change original, but copy[0].append(9) changes the shared first row seen through both containers. That distinction explains many apparently surprising state leaks.
Deep copying is not automatically the right repair. It may be expensive, and resources such as locks, sockets or external handles have no simple independent-copy meaning. Decide which objects should be owned exclusively and which are intentionally shared. For immutable children, a shallow copy can provide the desired independence without duplicating the entire graph.
79. Why can mutation invalidate an iterator?
An iterator relies on assumptions about storage and traversal order. Structural mutation may shift elements, reallocate backing storage, remove the current node or change a hash table's layout, invalidating those assumptions. The exact effect is defined by the container and language API, not by a universal iterator rule.
For example, removing the current item from an array-backed list shifts later items left. An index-based loop that then advances may skip the item shifted into the current position. Other containers detect structural mutation and fail fast, while some concurrent containers explicitly offer weakly consistent iteration.
Use an iterator's documented removal operation when available, collect changes for a later pass, or traverse a snapshot. Snapshotting adds memory and intentionally omits later updates; it is not equivalent to observing a live collection. A test that happens to work for one size or implementation does not establish a supported mutation contract.
80. What edge cases belong in data structure tests?
Test both individual boundary operations and sequences that can break structural invariants. Empty and singleton cases catch missing head or root handling; duplicates expose equality-policy mistakes; capacity transitions exercise resizing, eviction and rehashing. Invalid indices and removals need explicit expected outcomes.
Useful structure-specific cases include:
Trees: skewed shapes, root deletion, duplicate-policy boundaries and rebalancing after updates.
Hash tables: deliberate collisions, deletion inside a probe chain and growth with tombstones.
Graphs: isolated vertices, cycles, disconnected components and multiple valid shortest paths.
Queues and caches: repeated empty-to-nonempty transitions, wraparound, zero capacity and updates of existing keys.
A strong sequence test checks invariants after every operation, not just the final result. For an LRU cache, compare both returned values and eviction order against a simple reference model. For a randomized heap test, compare each popped result with a sorted-list model. Keep generated sequences reproducible so a failure can be reduced to the smallest transition that corrupts the structure.
Data Structure Interview Questions and Answers for Experienced
Strong experienced answers tie guarantees to a specific model and workload. These scenarios examine diagnosis, ownership, approximation and migration, including costs that a simple complexity table does not capture.
81. How would you evaluate a structure for a read-heavy, update-light workload?
I would choose around the kind of reads, not the read-to-write ratio alone. Exact lookup favors a hash index; ordered ranges and sequential scans can favor a sorted array; a balanced tree supports ordered reads with incremental updates. For a catalog rebuilt nightly and queried throughout the day, a sorted immutable array may give compact storage and predictable iteration without maintaining a tree on every change.
The important comparison is the complete update lifecycle. A new array can be built separately and atomically published, but both versions may coexist while old readers finish. I would compare rebuild duration, peak memory and acceptable staleness against a tree's ongoing allocation and synchronization costs. A rare update that must become visible immediately can change the decision even when almost every operation is a read.
82. Why might a theoretically faster structure run slower in practice?
A better asymptotic bound does not guarantee lower elapsed time at the sizes we actually use. Cache misses, allocation, pointer chasing, branch prediction and synchronization can outweigh a reduction in logical operations. Searching a small contiguous array can beat following pointers through a tree because the processor can fetch nearby values efficiently.
I would separate construction from querying and identify the crossover point across realistic collection sizes. If a structure is rebuilt for every request, a fast lookup may never repay its construction cost. Profiling should connect the observed result to a mechanism, such as fewer cache misses or less allocation, rather than only produce a timing ranking. I would also inspect latency variation: an excellent average can conceal resize or reclamation pauses that matter to the application.
83. How would you protect a hash-based service against adversarial collisions?
I would first establish whether clients control the indexed keys and whether the hash function permits them to create many collisions. A collision-heavy table can turn normally efficient operations into long bucket searches. Resizing changes capacity, but does not repair a hash function that gives attacker-selected keys the same hash value.
A suitable keyed or randomized hash makes collision sets harder to predict; request-size limits and per-client resource budgets limit the damage of expensive inputs. Where a deterministic bound is required, an ordered structure or an implementation with a documented collision fallback may be preferable. I would test long keys as well as colliding keys, because hashing and equality checks themselves consume work. A useful operational signal is rising lookup latency at stable table size, investigated alongside bucket distribution and key lengths.
84. How can incremental rehashing reduce latency spikes?
Incremental rehashing spreads a resize across later operations instead of copying the entire table in one request. During migration, the implementation retains old and new tables and moves a bounded amount of work at each step. Lookups must know which locations can still contain a key, and inserts normally target the new table under a defined ownership rule.
Deletion illustrates the correctness risk: removing a key only from the new table can leave an old copy that reappears during migration. Progress also needs an explicit policy if traffic becomes read-only. A background worker or reads that help migrate can finish the transition, depending on the concurrency model. Finally, moving one bucket is not necessarily bounded work if that bucket contains thousands of colliding entries; a latency-oriented design may need an entry-level migration budget.
85. When is a worst-case bound more important than an amortized bound?
A worst-case bound matters when one expensive operation can break the contract, even if the average sequence is cheap. Dynamic-array append is amortized constant time, but an append that reallocates and copies a large buffer can violate a request deadline. A fixed-capacity buffer or a design that performs bounded migration work may be a better fit for that path.
I would distinguish an algorithmic step bound from a wall-clock guarantee. Allocation, garbage collection, page faults, lock contention and storage access can still delay an operation with good asymptotic behavior. For a deadline-sensitive queue, I would examine the full enqueue path, including what happens when capacity is exhausted. Preallocation helps only if the chosen full-buffer policy is also compatible with the deadline; waiting indefinitely for space defeats the intended guarantee.
86. How do AVL and red-black trees differ as engineering choices?
AVL and red-black trees both keep search, insertion and deletion logarithmic, but enforce different balance invariants. AVL requires the heights of each node's child subtrees to differ by at most one. Red-black trees use coloring and black-height rules that permit a looser shape. That can change search depth and the balancing work performed during updates.
I would not select one solely by repeating that AVL is for reads and red-black is for writes. For a rank index, the implementation must also maintain subtree counts through every rotation; a well-tested augmented implementation may be more valuable than a small theoretical height advantage. Key comparison cost, node layout, allocator behavior and iteration needs can dominate. I would compare the actual available implementations under the expected update pattern, including deletion, rather than infer their performance from the names.
87. What does randomization buy in a treap or skip list?
Randomization makes the expected shape independent of ordinary key insertion order. A treap combines search-tree key ordering with random heap priorities; a skip list promotes nodes to randomly chosen levels. With suitable independent choices, both provide expected logarithmic operations without the same deterministic rebalancing rules used by AVL or red-black trees.
For example, inserting already sorted keys degenerates an ordinary unbalanced search tree, but does not by itself force a treap into a chain when priorities are independently generated. The qualification is important: expected bounds are not deterministic limits on each request. Predictable or attacker-controlled choices can undermine the assumptions. I would use deterministic seeds to reproduce tests while separately considering whether production randomness must resist adversarial prediction, and choose a deterministic balanced structure when a hard per-operation bound is essential.
88. How would you augment a tree for rank and select queries?
An order-statistic tree stores the size of each node's subtree. For zero-based select(r), compare r with the left subtree's size: descend left when it is smaller, return the current node when equal, or descend right after subtracting the left size and current node. Rank makes the complementary calculation by accumulating nodes skipped while searching.
If a node has three values in its left subtree, that node occupies rank three and its right subtree begins at rank four. In a balanced tree, following one search path takes logarithmic time. The engineering obligation is to recompute sizes after insertion, deletion and rotations, not just after ordinary links change. Duplicate handling must be defined too: a node with multiplicity five contributes five positions if ranks refer to individual values, but only one if ranks refer to distinct keys.
89. What invariant supports an interval tree for overlap queries?
A common interval-search tree orders nodes by interval start and stores the maximum endpoint reachable in each subtree. A search can reject a subtree whose intervals all end before the query begins. This pruning metadata must remain correct after insertions, deletions and rotations, because a stale maximum can either waste work or incorrectly hide a match.
Endpoint semantics determine the actual comparisons. Closed intervals [1, 3] and [3, 5] overlap at three; half-open intervals [1, 3) and [3, 5) do not. For half-open nonempty intervals, overlap requires each start to be less than the other interval's end. I would settle that contract before implementing pruning or empty-interval behavior. Finding one overlap and reporting all overlaps are different operations; an all-results query must include the cost of producing its matches.
90. Why do B-trees suit external storage?
B-trees organize many keys and child pointers in each node so a search traverses relatively few storage pages. Their high fan-out makes tree height much smaller than a binary tree with the same number of keys. Splits, redistribution and merges preserve occupancy and ordering as records change, keeping the index useful after many updates.
The benefit comes from matching the layout to block-oriented storage, not simply from calling a tree a disk index. If a page can guide the search toward hundreds of children, one page read resolves much more routing information than a binary node. Actual performance depends on key size, page utilization and whether upper levels are cached. Wider keys can reduce fan-out, while frequent splits can increase write work, so page layout and update behavior belong in the design discussion alongside lookup complexity.
91. How does a B+ tree differ from a typical B-tree?
In a typical B+ tree, internal pages contain routing keys and child pointers, while leaf pages contain records or record pointers. Leaves are commonly linked, allowing a range query to find its starting point and then scan adjacent leaves. A typical B-tree can also store associated records in internal nodes, although product terminology and layouts vary.
For a query such as all orders between two timestamps, the B+ layout makes the ordered leaf scan a natural operation. Keeping large payloads out of internal pages can also improve their fan-out. The trade-off is that a successful point lookup still reaches the leaf level; encountering a matching separator does not necessarily retrieve the record. I would inspect whether the implementation stores complete records, primary-key references or other payloads at the leaves before predicting its I/O cost.
92. When might a log-structured merge design beat an in-place tree index?
A log-structured merge design can be attractive when batching updates into sorted runs is more efficient than repeatedly modifying individual index pages. An in-memory component absorbs writes and is flushed to storage; compaction later merges runs. This shifts work into the background but does not eliminate it: reads may consult multiple components, and compaction rewrites data.
For example, a RocksDB workload with growing overlapping level-zero files may show worsening reads as more candidate files need attention. Increasing compaction throughput can reduce that overlap, but consumes I/O and CPU and can interfere with foreground traffic. I would inspect compaction backlog, write stalls, read amplification and deletion-marker retention before changing the structure. A B-tree may be preferable for a different balance of point reads, ranges and update locality; sequential writes alone are not evidence that an LSM design is universally faster.
93. What guarantees does a Bloom filter provide?
A standard Bloom filter answers either 'definitely absent' or 'possibly present.' Under correct insertion-only operation with consistent hashing and intact state, it has no false negatives, but it can have false positives because different keys share bits. A positive answer must therefore be checked against the authoritative data if correctness requires exact membership.
A storage engine can use a negative result to avoid reading a file that cannot contain the key. A false positive costs an unnecessary lookup, rather than losing a valid record. This is very different from rejecting a payment as a duplicate solely because the filter says 'present': that would discard some legitimate payments. Ordinary deletion by clearing a key's bits is unsafe because those bits may also support other keys. Synchronization and persistence must preserve the filter's insertion guarantees as well.
94. How would you size a Bloom filter for a target false-positive rate?
For n expected entries and desired false-positive probability p, classical sizing approximations give m = -n ln(p) / (ln(2))² bits and an ideal probe count near k = (m/n) ln(2). The calculation estimates the space/error trade-off; it is not an exact guarantee for every hash scheme or blocked-filter implementation.
For 100,000 entries at a one-percent target, this calculation produces 958,506 bits and seven probes, roughly 117 KiB before allocation overhead. The code rounds storage upward and chooses an integer probe count:
I would provision for the expected distinct-key count over the filter's lifetime, not just today's count. As additional insertions set more bits, the false-positive rate rises. Hash quality, probe-generation strategy and actual occupancy should be checked against the chosen implementation's documented model before treating the estimate as a capacity commitment.
95. When is a counting Bloom filter appropriate?
A counting Bloom filter is useful when approximate membership must support legitimate deletions. It replaces each bit with a counter: insertion increments the selected counters, and deletion decrements them. A location remains represented while other inserted keys still contribute to its count. The additional counters require more memory and introduce overflow and underflow concerns.
The difficult part is establishing that a deletion is valid. A positive filter result is not sufficient evidence that a key was inserted, because it may be a false positive. Decrementing counters for such a key can remove evidence for real keys and create false negatives. I would define ownership of insert/delete events and how duplicate insertions are balanced with deletions, using an authoritative membership record or reliable lifecycle protocol. Counter saturation also needs a deliberate policy; silently wrapping counters invalidates the guarantees.
96. How does structural sharing support persistent data structures?
Structural sharing lets an immutable update produce a new version without copying the entire structure. Updating one leaf in a persistent tree copies the nodes on the affected root-to-leaf path and reuses unchanged subtrees. Both the old and new roots remain valid, which is useful for undo history, snapshots and readers that need a consistent view.
For example, changing one configuration entry can publish a new root while an in-flight request continues using the previous configuration. The old version cannot observe a partially applied change because its reachable nodes are not mutated. The cost is retention: keeping an old root keeps everything reachable from it alive, even when newer versions no longer use those nodes. Persistent here means previous versions remain accessible; it does not mean that memory survives a crash or has been durably written to disk.
97. How can a hash array mapped trie implement an immutable map?
A hash array mapped trie, or HAMT, routes a key through successive groups of its hash bits. Compact node representations avoid allocating a full array of children for every sparsely populated branch. To update an immutable map, the implementation copies the affected path and shares the untouched nodes with the previous version.
Two keys that share their first hash-bit group initially follow the same branch and separate when a later group differs. If their complete hashes coincide, a collision representation must still compare the actual keys. This gives shallow typical paths and efficient persistent updates, but does not remove hashing, equality or allocation costs. For a very small map, a simpler flat representation can be cheaper. I would also check how retained snapshots affect memory, because shared nodes remain live as long as any reachable version needs them.
98. What is the ABA problem in a lock-free structure?
ABA occurs when a thread observes a value A, another thread changes it to B and then back to A, and a compare-and-swap succeeds despite that intervening history. Equality of the current pointer value does not establish that the object or links behind it are unchanged. This matters in algorithms that derive a new pointer from an earlier observation.
Consider a stack pop that reads head A and remembers A's next node. Another thread removes A, changes the stack and later reuses A's address. The delayed thread may successfully compare the head with A while installing a next pointer derived from an obsolete state. Version tags can detect some histories, and safe reclamation can prevent premature address reuse, but neither is a universal patch. The proof must cover tag wraparound, node reuse rules, memory ordering and the complete update sequence.
99. Why is memory reclamation difficult in lock-free linked structures?
Logical removal and safe reclamation are separate events. A node can be unreachable from the current head while another thread still holds a pointer obtained earlier. Freeing or reusing it immediately can cause a use-after-free even if the compare-and-swap that removed it was correct.
Hazard pointers let readers announce nodes they may access; reclamation waits until a retired node is no longer protected. Epoch-based methods defer reclamation until readers have moved beyond an earlier access period. Their operational trade-offs differ: a stalled participant can delay reclamation and retain memory, with the details depending on the scheme. I would examine a paused-reader scenario, shutdown behavior and retired-node growth as part of the design. A reclamation method's progress property does not establish that every operation of the containing data structure is wait-free.
100. What does linearizability mean for a concurrent queue?
A linearizable concurrent queue behaves as if each operation took effect at one instant between its invocation and response. The resulting sequential order must also respect real-time order: if enqueue A completes before enqueue B begins, a later dequeue cannot return B ahead of A in an otherwise ordinary FIFO queue.
Overlapping calls allow more than one legal order. If two producers enqueue simultaneously, either item can be first provided the observed history has a valid sequential explanation. That distinction is important when testing: comparing only final queue contents misses ordering and duplicate-delivery errors. I would record invocation times, responses and returned values and check whether a legal FIFO history exists. Linearizability is a correctness contract, not a promise of fairness, starvation freedom or low latency under contention.
101. How do lock-free and wait-free progress guarantees differ?
Lock-free progress means that the system continues completing operations even when individual threads repeatedly lose contention. Wait-free progress is stronger: each operation completes within a bounded number of its own steps under the algorithm's model. A compare-and-swap retry loop may be lock-free while a particular unlucky thread retries indefinitely.
For a shared counter, repeated interference can force one caller to retry while other callers successfully increment. That is system-wide progress, but not a per-caller completion bound. I would ask whether the claim covers allocation and reclamation as well as the central update loop; calling a potentially blocking allocator can change the overall guarantee. Neither property alone gives a wall-clock deadline, because the scheduler can pause a thread. Fairness and end-to-end latency therefore need separate analysis.
102. How would you make an LRU cache safe under concurrency?
An LRU cache must update its key map and recency list as one coherent operation. A simple lock around lookup, promotion and eviction is often the clearest correct starting point. A cache hit is usually a write to recency metadata, so treating hits as read-only operations under a reader-writer lock can be misleading.
For example, one thread must not return a list node that another thread has just evicted and reused while the map still points to it. Loading a missing value introduces another policy choice: hold the lock during a slow load, allow duplicate loads, or coordinate an in-flight load separately. Sharding reduces contention but usually changes global capacity and eviction semantics. I would decide whether exact global LRU is a requirement before introducing approximate recency, and define how failures and cancelled loads remove their temporary state.
103. How do snapshot reads trade memory for simpler concurrency?
Snapshot reads let a reader hold one immutable version while a writer builds and publishes a replacement. The reader sees a consistent set of invariants without coordinating every individual field access with the writer. Publication still needs the language's appropriate synchronization so the fully initialized version becomes visible safely.
For a routing table, a request can capture one root and use it for its entire decision even if a new route set is published halfway through. That gives consistency but may return an answer from an older version, so the contract must permit that staleness. The memory trade-off appears when a long-running reader retains an old root while many updates occur. I would monitor retained versions and define reader lifetimes or reclamation rules rather than assume that immutable snapshots make concurrent access cost-free.
104. When would you use a bounded ring buffer in production?
A bounded ring buffer is useful when memory must remain fixed and producers and consumers exchange a stream of items. Indices wrap around a preallocated array, avoiding an allocation per enqueue. Its behavior at capacity is part of the interface: block, reject, overwrite or drop are different contracts, not interchangeable implementation details.
Dropping an old telemetry sample may be acceptable; silently overwriting an unprocessed payment instruction is not. A single-producer/single-consumer buffer can use a simpler ownership and synchronization scheme than a multi-producer queue. In either case, publication must ensure consumers do not read a slot before its payload is ready. I would test empty/full transitions and index wraparound, and track occupancy and dropped or rejected items in operation. Counter widths and memory-ordering assumptions deserve explicit treatment because short happy-path tests rarely exercise them.
105. How would you design exact deduplication for an unbounded stream?
Exact all-time deduplication over an unrestricted key domain needs information about every distinct key seen so far, so its state cannot remain bounded indefinitely without additional constraints. Moving that state to a durable index changes where the cost is paid; it does not eliminate the need to remember prior keys.
I would first negotiate the actual requirement. 'Suppress duplicates for 24 hours' permits an expiry policy, while a fixed small identifier domain might permit a bitmap. A Bloom filter can reduce memory if false positives are acceptable, but using it alone means some genuinely new events will be rejected. For exact acceptance, it can only help avoid authoritative lookups on definite negatives. Expiration also changes semantics: after a key leaves the retention window, the system must be allowed to accept it again.
106. How should a streaming top-k design handle ties and updates?
I would define the ranking before choosing the structure: top scores, top distinct entities and most frequent entities require different state. A size-k min-heap handles insertion-only scores by keeping the weakest retained score at the root. Ties need a stable rule, such as score followed by entity ID, so results do not change unpredictably with arrival order.
Changing an entity's score makes a plain heap insufficient because finding its old entry is not efficient. An indexed heap can support position-aware updates; alternatively, a map of current versions and lazy invalidation can mark stale heap entries. The latter needs pruning and a bound or rebuild policy to prevent stale entries accumulating indefinitely. Exact top-k after deletions may require retaining candidates outside the current winners. Approximate heavy-hitter summaries solve another contract and must expose their error and frequency assumptions.
107. How would you maintain a median over a sliding window?
Two heaps can partition a window into a lower half and an upper half, with the median at their boundary. Sliding expiration is harder than insertion: the outgoing value may be buried inside a heap, where ordinary heap operations cannot efficiently remove it. An indexed heap, an ordered multiset or carefully managed delayed deletions can solve that problem.
With delayed deletion, record the expired value's count and discard stale entries whenever they reach a root. Track logical active sizes separately from physical heap lengths when rebalancing; otherwise expired entries distort the partition. Duplicate values require counts rather than a Boolean stale flag. I would also test a long monotone stream, because buried stale entries can grow even while the active window stays fixed. A rebuilding policy or an explicitly deletable structure is needed if bounded memory is part of the requirement.
108. When do compressed sparse row and coordinate formats fit different workloads?
Coordinate format stores explicit (row, column, value) triples and is convenient while assembling a sparse matrix. Compressed sparse row, or CSR, groups values by row and uses row offsets to locate each row's entries. CSR favors compact traversal and row-oriented arithmetic, while adding a new nonzero can require shifting storage and updating offsets.
For example, a data-ingestion stage can append coordinate triples cheaply, then convert once to CSR before repeated matrix-vector multiplication. Conversion must define what duplicate coordinates mean: combine them, reject them or keep them under a documented rule. The logical matrix can be wrong even when the compressed arrays have valid lengths if duplicates were handled incorrectly. I would choose based on whether the workload is still changing the sparsity pattern or repeatedly computing over a mostly fixed pattern.
109. How would you choose a graph representation for a very large sparse graph?
For a large sparse graph, per-edge overhead often matters as much as the asymptotic storage bound. Compact adjacency arrays or CSR-like layouts avoid allocating a separate object for every edge and give sequential neighbor scans. Hash maps of neighbor objects are more flexible for frequent structural updates, but their pointers, unused capacity and allocator metadata can consume substantial memory.
I would estimate the cost of the complete representation, including vertex-label mapping, edge attributes and reverse adjacency. If the algorithm frequently asks for incoming neighbors, a forward-only representation can force expensive scans or a second index. Degree skew matters too: a few very high-degree vertices can dominate traversal and temporary buffers. A static analytics graph and a continuously edited network may therefore need different layouts even when their vertex and edge counts are identical.
110. What is the trade-off in bidirectional BFS?
Bidirectional BFS searches outward from both endpoints and joins the two search trees. When frontiers grow quickly, meeting near the middle can explore far fewer vertices than expanding from one side to the full shortest-path distance. It applies naturally when both endpoints are known; the reverse traversal in a directed graph must follow incoming edges.
Correctness depends on the expansion and stopping rule. I would process complete distance layers, track distances on both sides and keep the best connection length found. An arbitrary intersection discovered while unevenly exploring partial layers is not sufficient evidence that no shorter connection remains. Parent links from each search reconstruct the two path halves, with the reverse half interpreted in the original edge direction. Memory and degree imbalance can reduce the advantage, so expanding the smaller current frontier is a useful strategy only within a sound shortest-path procedure.
111. How do you choose a structure for range queries with frequent updates?
I would first specify both the query aggregate and the update operation. Point increments with prefix or range sums are a natural fit for a Fenwick tree. A segment tree supports more general associative aggregates and, when suitable tag rules exist, range updates. An augmented ordered tree may fit keys that are sparse and change dynamically rather than occupy a fixed index range.
The algebra determines what is legal. Range sums can be obtained by subtracting two prefix sums; range minimum cannot generally be recovered by subtracting or otherwise undoing prefix minima. For a sum segment tree, adding a value to every element in a range changes a node's aggregate by the value times its covered length. I would use those concrete operations to justify the representation, rather than assume that every range-query problem is interchangeable.
112. What can go wrong with lazy propagation in a segment tree?
Lazy propagation fails when a deferred tag does not describe the complete effect of an update or when tags compose in the wrong order. The stored aggregate must already reflect a pending update even if the children have not yet received it. Before descending, the implementation must pass down the necessary state without applying it twice.
Range assignment and addition make the ordering visible. Assigning every value to five and then adding two produces sevens; adding two and then assigning five produces fives. A later assignment must replace older pending value updates, while a later addition must modify the pending assignment when one exists. For range sums, the transformation also depends on the node's interval length. I would compare random overlapping updates and queries against a plain array, especially nested assignments, empty ranges and updates that touch exactly one boundary.
113. When is rollback disjoint-set union useful?
Rollback DSU is useful when connectivity changes must be explored and then undone, such as offline dynamic connectivity or backtracking through possible edge sets. It records the parent and size changes made by a union, then restores them when returning to an earlier checkpoint. Union by size keeps trees shallow without requiring unrestricted path compression.
For example, an offline algorithm can assign each edge to the time intervals where it exists, add the relevant unions while traversing a tree of intervals and roll them back on exit. Ordinary path compression would introduce extra parent changes during finds; those changes would also need logging, complicating rollback. A clean interface records the history length as a checkpoint and reverses all later changes. Unions whose endpoints are already connected must fit that checkpoint convention so an undo never removes an unrelated successful union.
114. How would you test a custom structure against a reference model?
I would compare operation histories against a simpler model, checking both returned results and internal invariants after each step. For a custom ordered set, a sorted list can serve as a slow but understandable oracle. Random sequences should mix insertion, deletion, lookup and iteration, including duplicates and operations on an empty structure.
When a failure appears, retain the seed and reduce the sequence to the smallest reproducing example. A three-operation failure is much more useful than a million-operation log. Invariants such as ordering, subtree counts or map/list agreement localize the corruption before it affects a later result. Invalid inputs belong in separate tests of the documented error contract. Concurrent structures additionally require history-aware checks; identical final contents do not prove that intermediate results obeyed linearizability or that items were returned only once.
115. What should a reliable data structure benchmark measure?
A useful benchmark measures the operation mix the application will actually perform, including construction, updates, reads, memory use and latency distribution. A lookup-only benchmark on an already built index answers a different question from the cost of rebuilding that index for every request. Key sizes, hit/miss ratio and input order can materially change the result.
I would keep setup outside the timed region unless setup is part of the workload, consume results so optimized runtimes cannot discard the work, and account for warm-up and allocation. Repeated runs should reveal variability rather than report one best number. For a cache, a uniform random stream and a skewed hot-key stream can favor different policies. Reporting environment, dataset and tail behavior makes the conclusion actionable: it identifies the workload where the structure wins and the conditions that could reverse that decision.
116. How would you investigate unexpected memory growth in a container?
I would distinguish more live data from memory retained after data is removed. A container can have a stable logical size while its backing capacity, stale heap entries, free-node cache or references to old snapshots keep growing. Allocator fragmentation can also keep process memory high after objects become unreachable.
The first diagnostic is to compare logical element count, allocated capacity and process memory across the same operation history. If a queue's length stays near one hundred while retained entries increase, I would inspect tombstones or delayed deletion rather than blame incoming volume. A heap profile or retention graph can show whether removed payloads remain referenced. The fix should match that cause: clear ownership references, bound caches or rebuild stale-entry structures. Periodic rebuilding may relieve symptoms but does not explain a lifecycle leak or guarantee that memory returns to the operating system.
117. How does key normalization affect correctness in an index?
Normalization defines key identity, so it is part of the index's correctness contract. Insertion, lookup and deletion must use the same policy. A case-insensitive username index might store a canonical lookup key while retaining the original spelling for display, but that policy should not automatically be reused for file paths or URLs whose identity rules differ.
Unicode makes seemingly simple transformations subtle: visually similar strings are not necessarily equal, and lowercasing is not a universal substitute for an agreed case-folding and normalization policy. Over-normalization can merge two legitimate entities; under-normalization can allow duplicates that the product considers identical. I would test equivalent and deliberately distinct examples from the actual domain. Changing the policy later is a migration, because previously separate records may collide under the new canonical form and need an explicit conflict-resolution rule.
118. How would you migrate from one index structure to another safely?
I would build the replacement from a consistent snapshot and capture updates that happen during the build. Before switching readers, the new representation must have applied all changes through a known cutover point. This avoids losing a delete or update that occurred after its initial data was copied.
A typical sequence is backfill, replay an ordered change log, compare old and new query results, then switch the read path while retaining a rollback option. Dual writes require a failure policy: an update that succeeds in one index and fails in the other must be retried or reconciled. Counts alone are weak validation because one missing key and one extra key can cancel out. I would compare exact semantics for duplicates, normalization, ranges and deletion, and plan temporary memory and write capacity for running both representations.
119. How do cache eviction and admission policies differ?
Eviction selects a resident item to remove; admission decides whether a newly requested item deserves space at all. Pure LRU normally admits every miss, so a one-time sequential scan can push out a frequently reused working set. An admission policy can reject low-value newcomers even when they have just been requested.
Imagine a small hot set followed by a scan of thousands of unique records. LRU promotes each scan record and can leave the hot set absent when normal traffic resumes. Frequency-aware admission can reduce that pollution, but requires metadata and a way to adapt when popularity changes. I would evaluate hit rate together with lookup overhead and adaptation speed. A sophisticated policy that preserves yesterday's popular items for too long can perform poorly after a workload shift despite looking strong on a fixed historical trace.
120. How would you review a data structure proposal before implementation?
I would start with the operation contract and invariants, then ask whether the simplest available representation satisfies them. The proposal should define duplicate behavior, ordering, ownership, error handling and concurrency semantics before quoting complexity. A priority queue that cannot efficiently cancel tasks may be unsuitable for a scheduler even when insertion and minimum lookup are fast.
Next I would walk through representative operations, including partial failure, and identify exactly which links, counts and indexes change. That exposes hidden coupled invariants and rollback obligations. I would require evidence for the expected benefit over a baseline: a relevant benchmark, a bound the product needs or a simpler correctness argument. The review should end with explicit trade-offs and validation criteria, such as bounded memory under cancellation-heavy traffic, rather than approval based on the sophistication of the chosen structure.
Data Structure Documentation and Further Reading
These primary references cover implementations, algorithmic bounds and the concurrency or storage assumptions behind advanced choices. Python links target the version family used in the examples. Research papers establish their own models; library behavior and guarantees should be checked against the implementation being deployed.
Similar Posts
