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
142 practiced
Provide concise pseudocode for the two-pointer sliding-window technique to find the maximum-length subarray with sum ≤ S for an array of positive integers:left = 0curr_sum = 0max_len = 0for right in 0..n-1: curr_sum += A[right] while curr_sum > S: curr_sum -= A[left] left += 1 max_len = max(max_len, right - left + 1)Explain why this is O(n) and how the approach changes if array elements can be negative.
Sample Answer
**Pseudocode (concise, review-ready)**
pseudo
# A: array of positive ints, S: target sum
left = 0
curr_sum = 0
max_len = 0
for right = 0 to n-1:
curr_sum += A[right]
while curr_sum > S and left <= right:
curr_sum -= A[left]
left += 1
max_len = max(max_len, right - left + 1)
return max_len
**Why this is O(n)**- Each element is added once by the right pointer and removed at most once by the left pointer.- Total pointer movements ≤ 2n, so time is linear O(n). Space O(1).- Useful interview talking points: prove by accounting method and mention invariant (curr_sum ≤ S after inner loop).**If elements can be negative**- Window sum is no longer monotonic: shrinking may increase sum, expanding may decrease it.- Two-pointer greedy fails; need alternatives: - Use prefix sums + hash/map (for longest subarray with sum ≤ S you can use a balanced BST or monotonic deque of prefix sums) — O(n log n) or O(n) with advanced monotonic structures. - Or use Kadane-like variants only for exact sums; otherwise switch to prefix + ordered structure.- As an engineering manager, emphasize design trade-offs to the team: correctness over micro-optimizations, test coverage for negative values, and clear documentation for algorithm choice.
EasyTechnical
77 practiced
Your team needs an in-memory FIFO queue for background tasks and an undo stack for operations in a web service. For each use-case, choose the simplest standard-library data structure(s). Justify your choice with time/space complexity for push/pop/peek, and mention concurrency considerations when there are multiple producers and consumers.
Sample Answer
**Answer (Engineering Manager perspective)****Chosen structures**- FIFO background tasks: use a standard library queue (e.g., Java ConcurrentLinkedQueue or Python collections.deque used as queue).- Undo stack: use a dynamic array/stack (e.g., Java ArrayDeque or Python list used with append/pop).**Justification & complexity**- Queue (deque/linked queue): push/enqueue O(1) amortized, pop/dequeue O(1), peek O(1). Space O(n).- Stack (dynamic array/ArrayDeque/list): push O(1) amortized, pop O(1), peek O(1). Space O(n).**Concurrency considerations**- For multiple producers/consumers prefer thread-safe variants: - Java: use ConcurrentLinkedQueue or ArrayBlockingQueue for bounded buffers; for blocking semantics use LinkedBlockingQueue. - Python: use queue.Queue (thread-safe) instead of raw deque when threads share it.- For undo stack, typically single-threaded per user/session — keep it non-concurrent and confined to request/session state. If shared across threads, protect with a mutex or use a concurrent stack implementation.- Also consider backpressure, bounded capacity, and persistence for durability in high-load systems.**Managerial note**Standard libs minimize bugs and speed up delivery; pick blocking vs non-blocking variants based on latency and throughput requirements.
MediumTechnical
87 practiced
Design a data structure that supports insert(x), delete(x), and getRandom() each in expected O(1) time. Describe the combination of structures, how each operation works in detail (including edge cases), and discuss concurrency and failure modes if multiple threads perform operations concurrently.
Sample Answer
**Approach (high-level)** Use a dynamic array (list) and a hash map (value -> index in array). This combination gives O(1) expected operations.**Data structures**- Array A of elements (supports O(1) append and swap-pop).- HashMap H: value -> index in A.**Operations**- insert(x): if x in H return false/ignore; append x to A, set H[x] = A.length-1. O(1).- delete(x): if x not in H return false; idx = H[x]; last = A[-1]; swap A[idx] = last; update H[last] = idx; pop last element; remove H[x]. O(1). Edge: deleting last element does swap with itself — still correct.- getRandom(): pick random index r in [0, A.length-1] and return A[r]. O(1).**Concurrency & failure modes (as Eng Manager)**- Concurrency: make H and A atomic together — use a single coarse-grained lock for correctness, or fine-grained: use a mutex per structure with careful ordering (always lock A then H) or use a read-write lock: concurrent getRandom under shared lock; insert/delete under exclusive lock.- Lock-free option: use concurrent vector and concurrent hash with CAS-based index updates — complex and error-prone; only justify if throughput demands it.- Failure modes: partial failure during delete (crash between swap and H update) can leave inconsistent index mapping. Mitigate with transactional updates (two-phase commit), write-ahead log, or perform operations under lock so they're atomic. Also consider resizing array — ensure resizing updates are synchronized.- Testing & monitoring: add unit tests for race conditions, use stress tests, metrics for lock contention, and timeouts to detect deadlocks.This design balances simplicity and predictable correctness; for high throughput, invest in concurrent data structures and robust atomicity mechanisms.
EasyTechnical
145 practiced
List typical time and (auxiliary) space complexities, average and worst where applicable, for the following structures and operations: dynamic array (access/append/insert/delete), singly/doubly linked list (access/insert/delete), hash table (lookup/insert/delete), binary search tree and balanced BST (lookup/insert/delete), binary heap (insert/delete-min/build). Provide one example where worst-case differs from average-case.
Sample Answer
**Context (Engineering Manager view)** As an EM I expect candidates to state typical time/aux space and note average vs worst where relevant, plus one concrete example of divergence.**Dynamic array (amortized over resizes)** - Access: Time O(1) avg/worst, Aux space O(1) - Append: Time O(1) amortized, worst O(n) (resize), Aux O(1) - Insert/Delete (middle): Time O(n) avg/worst, Aux O(1)**Singly/Doubly linked list** - Access (by index): Time O(n) avg/worst, Aux O(1) - Insert/Delete (given node): Time O(1) avg/worst, Aux O(1) - Insert/Delete (by value/search): Time O(n) avg/worst**Hash table (with chaining; open addressing similar but different constants)** - Lookup/Insert/Delete: Avg O(1), Worst O(n) (all keys collide), Aux space O(n) for table + chains**Binary Search Tree (unbalanced)** - Lookup/Insert/Delete: Avg O(log n) if random, Worst O(n) (degenerate), Aux O(1) or O(h) recursion stack**Balanced BST (AVL/Red‑Black)** - Lookup/Insert/Delete: Time O(log n) avg/worst, Aux O(1) or O(log n) recursion**Binary heap (min-heap)** - Insert: Time O(log n) worst/avg, Aux O(1) - Delete-min: Time O(log n) worst/avg, Aux O(1) - Build-heap (Floyd): Time O(n) worst/avg, Aux O(1)**Concrete example where worst ≠ average** Hash table: average O(1) lookup, worst-case O(n) when many collisions (e.g., adversarial keys or poor hash causing single chain).
HardTechnical
92 practiced
Compare red-black trees, AVL trees, and B-trees for on-disk versus in-memory database use. Discuss balancing costs, typical rotation counts on updates, cache behavior, node fanout, and why many storage engines prefer B-trees. As a manager, advise which tree variant your team should pick for a new storage engine and why.
Sample Answer
**Overview & requirements clarified**For a storage engine we care about: write/read throughput, latency, durable on-disk layout, cache friendliness, and predictable compaction/repair costs.**Comparison — high level**- Red‑Black Trees (RB) - Balanced BST with ~O(log n) ops, fewer rotations than AVL on average. - Rotation cost: typically ≤2 rotations per insert/delete amortized. - In-memory: good for pointer-heavy workloads; moderate cache locality. - On-disk: poor — one key per node causes many random I/O, high pointer overhead.- AVL Trees - Strict balance → smaller height (~1.44 log2 n) → slightly fewer comparisons. - Rotation cost: may need up to O(log n) rotations in worst-case rebalance on deletes; inserts usually 1–2 rotations. - In-memory: better lookup latency than RB for CPU-bound workloads. - On-disk: still poor due to pointer-chasing and tiny nodes.- B-Trees (and variants: B+Tree) - Multi-way nodes (high fanout) pack many keys per node → shallow tree. - Rotation/merge cost: node splits/merges are heavier but rare; updates typically affect one node and occasional split/merge. - Cache & I/O: excellent — each node maps to a disk block/page, minimizes disk seeks and leverages sequential I/O. - Ideal for large datasets and disk-backed storage.**Cache behavior & node fanout**- RB/AVL: fanout = 2 → deep trees, poor spatial locality; CPU cache misses high.- B-Tree: fanout = page_size / key_entry_size → shallow, high spatial locality, better L1/L2 use through prefetching.**Why storage engines prefer B-trees**- Aligns with block-device semantics: minimize disk seeks, maximize throughput.- Easier to implement range scans, write-ahead logging, and page caching.- Concurrency-friendly (lock-coupling, latch-free variants) and tunable by page size.**Manager recommendation**I would choose a B+Tree variant as default for the new engine. Rationale:- Matches on-disk page model and OS/hardware caches.- Predictable I/O patterns and excellent range/scan performance.- Team trade-offs: invest in robust page cache, WAL, and concurrency; leverage well-understood libraries (or borrow design from LMDB/LevelDB) to accelerate delivery.For in-memory specialized indexes (e.g., latency-critical, CPU-bound hot paths) allow an RB/AVL in-memory index layer or adaptive log-structured skiplist, but core storage must be B+Tree-backed.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
