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.
EasyTechnical
149 practiced
Compare adjacency list and adjacency matrix as graph representations. For each, analyze memory usage in terms of V and E, describe operation costs for check-edge(u,v), iterate-neighbors(u), BFS/DFS traversal time, and discuss suitability for sparse vs dense graphs and for weighted graphs. Mention practical cache and memory-layout considerations.
Sample Answer
**Memory usage**- Adjacency list: O(V + E) (store one list per vertex, edges once for directed; twice for undirected).- Adjacency matrix: O(V^2) (dense V×V table; can store booleans or weights).**Operation costs**- check-edge(u,v) - List: O(deg(u)) linear scan; O(1) average if neighbors stored in a hash set/bitset. - Matrix: O(1) direct index access.- iterate-neighbors(u) - List: O(deg(u)) — optimal, visits only actual neighbors. - Matrix: O(V) — scan whole row even if few neighbors.- BFS/DFS traversal - List: O(V + E) time (each vertex and edge processed once). - Matrix: O(V^2) time (row scans dominate).**Suitability**- Sparse graphs (E << V^2): adjacency list is usually best (lower memory, faster traversals).- Dense graphs (E ≈ V^2): adjacency matrix is acceptable and simpler; constant-time edge queries helpful.- Weighted graphs: both can store weights. Lists store (neighbor, weight) pairs — efficient for sparse weighted graphs; matrices store weight or ∞ — convenient for algorithms requiring random access (Floyd–Warshall, dense linear algebra).**Practical cache / memory-layout considerations**- Matrix: contiguous rows give excellent spatial locality and SIMD/GPU friendliness; faster for batched edge checks and linear-algebraic operations.- Pointer-based lists: suffer pointer-chasing and cache misses; higher overhead per edge.- Compact alternatives: CSR/CSC (compressed sparse row/column) keep O(V+E) memory with much better locality and are preferred in high-performance research code and GPU implementations.- Choice depends on algorithmic needs (random edge queries vs streaming traversals), hardware (CPU vs GPU), and scale (memory capacity).I prefer adjacency lists/CSR for large sparse graphs in research experiments; use matrices for dense problems or where constant-time random access simplifies algorithms.
EasyTechnical
99 practiced
Implement a Trie (prefix tree) in Python supporting insert(word), search(word), and starts_with(prefix) for lowercase English letters. Provide code or clear pseudocode and analyze time and space per operation. Discuss memory trade-offs between using a fixed-size array of 26 children versus a dict/map per node, and how each choice affects cache behavior.
Sample Answer
**Approach (brief)** Use a TrieNode with 26 children; implement insert, search, starts_with by traversing characters. For Research Scientist perspective, note tries are useful for lexicon lookup, prefix-based pruning in beam search, or subword vocab indexing.**Code (Python)**
python
class TrieNode:
def __init__(self):
# fixed array for 'a'..'z'
self.children = [None] * 26
self.is_word = False
class Trie:
def __init__(self):
self.root = TrieNode()
def _idx(self, ch):
return ord(ch) - ord('a')
def insert(self, word: str) -> None:
node = self.root
for ch in word:
i = self._idx(ch)
if node.children[i] is None:
node.children[i] = TrieNode()
node = node.children[i]
node.is_word = True
def _walk(self, s: str):
node = self.root
for ch in s:
i = self._idx(ch)
node = node.children[i]
if node is None:
return None
return node
def search(self, word: str) -> bool:
node = self._walk(word)
return node.is_word if node else False
def starts_with(self, prefix: str) -> bool:
return self._walk(prefix) is not None
**Time & Space Complexity** - insert/search/starts_with: O(L) time where L = length of word/prefix. - Space: worst-case O(N * L * alphabet) if many branches; more precisely, number of nodes times node size.**Memory trade-offs & cache behavior** - Fixed-size array (26 slots): faster constant-time child access (indexing), good spatial locality; better cache prefetching and predictable memory layout—beneficial when doing many short traversals (e.g., autocomplete, beam search). However uses 26 references per node even if sparse → higher memory usage. - dict/map per node: memory efficient for sparse branching (only store present children) and flexible for larger alphabets; extra overhead per entry (hashing, pointers) and worse cache locality — lookups more expensive and unpredictable branch behavior. Choose array if alphabet small and throughput matters; choose dict if memory is tight or alphabet large (Unicode/subword). For research prototypes, prefer dict for simplicity; for production or speed-critical components, use arrays or compact representations (packed bitsets, DAWG, or radix/compressed tries).
EasyTechnical
99 practiced
Explain the two-pointer technique used on sorted arrays. Write pseudocode or describe an algorithm to find a pair that sums to a target s in a sorted array, analyze time/space complexity, and describe how to adapt the approach if the input is unsorted or if duplicates must be handled.
Sample Answer
**Brief idea (two-pointer on sorted array)** Use two indices left at start and right at end. If sum < s advance left; if sum > s decrement right; if equal return pair. Works because sorted order gives monotonic behavior.**Pseudocode**
pseudo
function find_pair_sorted(A[0..n-1], s):
left = 0
right = n-1
while left < right:
cur = A[left] + A[right]
if cur == s: return (left, right) // or values A[left], A[right]
if cur < s: left = left + 1
else: right = right - 1
return null
**Complexity**- Time: O(n)- Space: O(1)**Adapting if input is unsorted**- Option A (stable/simple): sort array then run above → Time O(n log n), Space O(1) or O(n) if stable copy.- Option B (hash-based): single pass using hash set to check (s - a_i) → Time O(n), Space O(n). Useful when original order must be preserved.**Handling duplicates**- To return a single valid pair duplicates need no special treatment.- To enumerate all unique pairs: while advancing pointers, skip equal values to avoid duplicate pairs: - after finding match, record it, then increment left while A[left]==prev_left and decrement right while A[right]==prev_right.- For hash-based enumeration, use map counts to ensure multiplicity (e.g., for pair x+x require count[x] >= 2).As a researcher, choose the variant based on constraints (preserve order, memory budget, need to enumerate all pairs).
EasyTechnical
85 practiced
As a research scientist, explain and show the amortized cost analysis of a dynamic array that doubles its capacity when full. Derive the amortized cost per append over a sequence of n appends, discuss memory behavior and cache implications for contiguous storage, and describe what changes when the array halves capacity when load factor drops below 1/4.
Sample Answer
**Answer (overview & claim)** I would explain that appending to a dynamic array that doubles when full has amortized O(1) cost: occasional expensive resizes are rare enough that averaged over n appends the cost per append is constant.**Amortized cost derivation** - Every element is moved only when a resize copies the whole array. If capacity doubles, sizes copied follow 1 + 2 + 4 + ... ≤ 2n.
text
Total copy cost ≤ 2n => amortized copy cost ≤ 2 per append
- Add the O(1) bookkeeping for each append; total cost ≤ 3n so amortized cost = O(1).**Memory behavior & cache implications** - Contiguous storage gives excellent spatial locality: sequential scans and appends benefit from prefetching and fewer cache misses. - Doubling maintains amortized low reallocations but uses at most ~2× live data capacity, so worst-case wasted memory ≲ 50%.**When halving at load < 1/4** - If we shrink only when size < capacity/4 and halve capacity, we avoid oscillation (thrashing). The same aggregate-copy argument applies: each element participates in O(1) copies across expansions and contractions, so amortized cost remains O(1). Shrinking reduces memory overhead while preserving cache-friendly contiguous layout.
MediumTechnical
81 practiced
Explain why B-trees (or B+trees) are commonly used for on-disk indexes compared to red-black trees. Provide complexity analysis in terms of disk I/O (block transfers), and discuss how block size and node fanout affect lookup, insert, and update performance plus space utilization.
Sample Answer
**Brief answer / intuition**B-trees and B+trees are optimized for disk by maximizing data per node so each disk I/O yields many key comparisons. Red‑black trees (binary) have fanout 2, causing O(log N) node accesses; B-trees use large fanout f ≈ B / key_size giving O(log_f N) disk reads, far fewer I/Os.**Complexity in block transfers**- Let f be average branching factor (fanout).- Let h be tree height.
text
h ≈ log_f N
Lookup, insert, update I/Os ≈ h (plus 1 for leaf access). So cost ~ O(log_f N) block transfers.**Why this matters vs red‑black**- Red‑black: fanout = 2 ⇒ O(log_2 N) disk I/Os (many).- B-tree: large f (e.g., 100–1000) ⇒ much smaller height ⇒ orders-of-magnitude fewer disk reads.- Sequential range scans: B+tree leaves are linked → sequential I/O (very efficient); RB tree in-order needs many random reads.**Effect of block size & fanout**- Larger block size B → larger f → smaller h → fewer I/Os but larger in-memory read per I/O.- Diminishing returns when node size exceeds cache or prefetch limits.- Fanout trade-offs: higher f improves lookup I/O but increases per-node CPU for searching (binary or interpolation search inside node mitigates).**Insert/update and space utilization**- Inserts/updates: may cause node splits or merges; cost amortized O(1) extra writes per operation but worst-case O(h) splits. Write amplification reduced by larger nodes (fewer structural changes).- Space utilization: B-tree nodes usually kept 50% full amortized (due to splits/merges). Larger nodes reduce relative pointer/key overhead so better space efficiency.**Practical notes for research context**- Model disk or SSD I/O and cache effects when designing variants (e.g., cache-aware/oblivious B-trees).- For ML-scale indexing, consider I/O parallelism, compression inside nodes, and write-optimized structures (LSM-trees) as alternatives depending on workload.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
