Comprehensive coverage of fundamental data structures, their operations, implementation trade offs, and algorithmic uses. Candidates should know arrays and strings including dynamic array amortized behavior and memory layout differences, linked lists, stacks, queues, hash tables and collision handling, sets, trees including binary search trees and balanced trees, tries, heaps as priority queues, and graph representations such as adjacency lists and adjacency matrices. Understand typical operations and costs for access, insertion, deletion, lookup, and traversal and be able to analyze asymptotic time and auxiliary space complexity using Big O notation including constant, logarithmic, linear, linearithmic, quadratic, and exponential classes as well as average case, worst case, and amortized behaviors. Be able to read code or pseudocode and derive time and space complexity, identify performance bottlenecks, and propose alternative data structures or algorithmic approaches to improve performance. Know common algorithmic patterns that interact with these structures such as traversal strategies, searching and sorting, two pointer and sliding window techniques, divide and conquer, recursion, dynamic programming, greedy methods, and priority processing, and when to combine structures for efficiency for example using a heap with a hash map for index tracking. Implementation focused skills include writing or partially implementing core operations, discussing language specific considerations such as contiguous versus non contiguous memory and pointer or manual memory management when applicable, and explaining space time trade offs and cache or memory behavior. Interview expectations vary by level from selecting and implementing appropriate structures for routine problems at junior levels to optimizing naive solutions, designing custom structures for constraints, and reasoning about amortized, average case, and concurrency implications at senior levels.
HardTechnical
94 practiced
Explain cache-oblivious vs cache-aware data structure design. Give an example where designing a cache-oblivious algorithm benefits performance without tuning to specific block sizes and compare to a cache-aware B-tree tuned for disk block size.
Sample Answer
Cache-aware vs cache-oblivious — short definitions- Cache-aware: data structures/algorithms explicitly tuned to a known block/cache size B (or cache-line / disk-page). Example: B-tree with node size ≈ B so each node access brings many keys per I/O; search cost O(log_B N) memory transfers.- Cache-oblivious: designs that do not know B but still achieve asymptotically optimal locality across all levels of a multilevel memory hierarchy. They exploit divide-and-conquer layouts to minimize memory transfers for any B.Concrete example where cache-oblivious helps- Van Emde Boas (vEB) layout for a binary search tree: store tree nodes in array using recursive subtree placement so that nodes of small subtrees are contiguous. Search in this layout incurs O(log_B N) memory transfers (optimal) for any block size B without tuning.- Benefit: a single binary-search-tree implementation performs well on CPU caches, large pages, and even SSD/HDD levels — you don’t need to retune node sizes when deployment hardware changes.Compare to a cache-aware B-tree tuned for disk block size- Cache-aware B-tree: - Pros: Simple concept, minimal indirection, excellent constants when B is known and node size chosen well; optimized for a specific layer (e.g., disk). - Cons: If B changes (different SSD, or running in-memory vs on-disk), you must retune node size; not optimal simultaneously across multiple levels.- Cache-oblivious (vEB tree): - Pros: Provably near-optimal across all B simultaneously; portable performance across caches and storage tiers; fewer platform-specific knobs. - Cons: Often more complex to implement; higher constant factors (extra pointer arithmetic, layout management); harder to support efficient updates (insert/delete may need reorganization or complex buffering like funnels). - Practical trade-off: For read-heavy workloads and multi-level hierarchies, cache-oblivious wins portability and robustness. For write-heavy or single-layered deployments where B is stable (e.g., DB tuned for specific disk page), a cache-aware B-tree usually gives better real-world throughput due to lower constants and simpler updates.When to choose which- Use cache-aware when you can control and fix the target layer (DB engines tuned to page size) and need the best constants.- Use cache-oblivious when you need a single implementation to perform well across CPUs, big-memory machines, and external storage, or when target block sizes vary or are unknown.Key takeaway: cache-oblivious designs give asymptotic, multi-level locality guarantees without tuning; cache-aware designs can outperform in practice when you can tune for a known level because of lower constants and simpler update paths.
MediumTechnical
78 practiced
Given an undirected unweighted graph, implement an algorithm to find the shortest path (in number of edges) between two nodes. Provide BFS-based code or pseudocode, analyze complexity, and describe memory requirements for storing the predecessor chain to reconstruct the path.
Sample Answer
To find the shortest path (fewest edges) in an unweighted undirected graph, use BFS from the source to explore level-by-level and maintain a predecessor map to reconstruct the path.
python
from collections import deque
def shortest_path_bfs(adj, src, dst):
"""
adj: dict[node] -> list(neighbor nodes) (adjacency list)
src, dst: nodes (hashable)
Returns: list of nodes from src to dst (inclusive) or [] if no path
"""
if src == dst:
return [src]
q = deque([src])
visited = {src}
pred = {} # predecessor map: node -> previous node on shortest path
while q:
u = q.popleft()
for v in adj.get(u, []):
if v not in visited:
visited.add(v)
pred[v] = u
if v == dst:
# reconstruct path
path = [dst]
while path[-1] != src:
path.append(pred[path[-1]])
return path[::-1]
q.append(v)
return [] # no path
Key points:- BFS guarantees shortest path in unweighted graphs.- pred stores for each discovered node its immediate predecessor on the shortest path; reconstruct by backtracking from dst to src.Time complexity: O(V + E) — each node and edge visited once.Space complexity: O(V) for visited, queue, and pred.Memory for predecessor chain: pred stores at most one pointer per discovered node (O(V) pointers). To minimize memory, store predecessors only for nodes at or beyond src or stop storing when destination found if you don't need all. Edge cases: src or dst missing, disconnected graph, large degree nodes. Alternative: bidirectional BFS to reduce explored nodes when graph is large; same predecessor logic but two maps for each direction.
MediumTechnical
85 practiced
Explain union-find (disjoint set union) with two optimizations: union by rank and path compression. Implement union and find operations in pseudocode and analyze their amortized time complexity for m operations on n elements.
Sample Answer
Union-Find (Disjoint Set Union) maintains a partition of n elements into disjoint sets supporting two operations: find(x) returns the representative (root) of x’s set; union(x,y) merges the sets. Two standard optimizations:- Union by rank: attach the shallower tree under the deeper to keep height small (rank approximates height/upper bound).- Path compression: during find, make every visited node point directly to the root.Approach: keep parent[] and rank[] arrays.
python
# Pseudocode-like Python
def make_set(n):
parent = [i for i in range(n)]
rank = [0]*n
return parent, rank
def find(parent, x):
# iterative path compression
while parent[x] != x:
parent[x] = parent[parent[x]] # compress one level
x = parent[x]
return x
def union(parent, rank, x, y):
rx = find(parent, x)
ry = find(parent, y)
if rx == ry:
return False # already in same set
# union by rank
if rank[rx] < rank[ry]:
parent[rx] = ry
elif rank[ry] < rank[rx]:
parent[ry] = rx
else:
parent[ry] = rx
rank[rx] += 1
return True
Key points:- Path compression flattens trees; union by rank keeps heights low.- Amortized complexity for m operations on n elements is O(m · α(n)), where α(n) is the inverse Ackermann function (extremely slow-growing, ≤ 4 for all practical n), effectively near-constant per operation.Edge cases:- Repeated unions on same pair (handled), large chains without compression (fixed by compression).Alternatives:- Union by size instead of rank (equivalent in complexity).
EasyTechnical
94 practiced
Design an API for a simple stack data structure supporting push, pop, peek, and isEmpty operations. Specify complexity guarantees, preconditions, and postconditions for each method. Also describe basic unit tests you would write for correctness.
Sample Answer
API design (language-agnostic signatures):- push(item): void - Preconditions: item != null (if disallowing nulls) or documented behavior for null - Postconditions: size increases by 1; top() == item - Complexity: O(1) amortized for dynamic array implementation; O(1) for linked-list- pop(): Item - Preconditions: not isEmpty() - Postconditions: returns previous top; size decreases by 1; new top is next element or undefined if empty - Complexity: O(1)- peek(): Item - Preconditions: not isEmpty() - Postconditions: returns top without modifying stack - Complexity: O(1)- isEmpty(): bool - Preconditions: none - Postconditions: returns true iff size == 0 - Complexity: O(1)- size(): int (optional) - Complexity: O(1)Implementation notes:- Back the stack with either dynamic array (ArrayList) or singly linked list. Array gives better cache locality; linked list avoids resize cost.Basic unit tests (examples):1. New stack is empty: isEmpty() == true, size() == 0; peek/pop throws or returns error per contract.2. Single push: push(x) -> isEmpty()==false, size()==1, peek()==x.3. Push-pop sequence: push(a), push(b), pop() == b, pop() == a, then isEmpty()==true.4. LIFO property with many elements: push 1..N, pop yields N..1.5. Null handling: pushing null either allowed (and peek/pop returns null) or throws; verify documented behavior.6. Underflow: pop/peek on empty stack raises correct exception.7. Concurrency (if supported): concurrent pushes/pops maintain consistency or document not thread-safe.Edge cases:- Large number of pushes to trigger resize (if array-backed).- Mutable objects pushed: ensure references behave as expected.
EasyTechnical
89 practiced
Implement a function in Python that returns true if an array contains any duplicates and false otherwise. Provide two solutions: one using sorting and one using a hash set. Compare their time and space complexities and discuss implications for very large inputs and stability.
Sample Answer
Approach: Two straightforward methods — (A) sort the array and check adjacent elements; (B) scan with a hash set to detect repeats.
python
# Method A: Sorting
def contains_duplicate_sort(nums):
if not nums:
return False
nums_sorted = sorted(nums) # creates a new list; in-place: nums.sort()
for i in range(1, len(nums_sorted)):
if nums_sorted[i] == nums_sorted[i-1]:
return True
return False
python
# Method B: Hash set
def contains_duplicate_set(nums):
seen = set()
for x in nums:
if x in seen:
return True
seen.add(x)
return False
Key points:- Sorting approach: simple, works for any comparable items. If you sort in-place (nums.sort()) you mutate input which may be undesirable.- Hash-set approach: single pass, stops early when a duplicate is found.Time & space complexity:- Sorting: Time O(n log n), Space O(n) if sort returns new list (Timsort uses O(n) worst-case extra); in-place sort uses O(1) extra for some implementations but Python's Timsort uses O(n) worst-case auxiliary.- Hash set: Time O(n) average, O(n^2) worst-case with pathological hash collisions (rare); Space O(n) for the set.Implications for very large inputs:- If memory is limited and you can afford to mutate input, in-place sort reduces auxiliary memory but still O(n log n) time.- Hash set is usually faster for large inputs when enough memory is available because it’s linear time and can early exit.- For streaming or external-memory data, consider external sorting or hashing with probabilistic structures (Bloom filter) to reduce memory at the cost of false positives.Stability:- Stability (preserving equal-element order) is irrelevant for duplicate detection; stable vs unstable sort doesn't affect correctness.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
