Data Structures and Complexity Questions

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

90 practiced

Explain common collision-resolution strategies for hash tables used in backend services: separate chaining, open addressing (linear probing, quadratic probing), and double hashing. For each approach describe average-case and worst-case time for lookup/insert/delete, memory overhead, cache behavior, and practical considerations when handling millions of keys.

Sample Answer

**Separate chaining** - Approach: buckets with linked lists or dynamic arrays per hash index. - Time (avg/worst): Lookup/Insert/Delete average O(1 + load factor α), worst O(n) if one bucket degenerates. - Memory: extra pointers per entry (high overhead if linked lists); using vectors reduces pointer cost but needs resizing. - Cache: poor if linked lists (pointer chasing); better if buckets store contiguous arrays. - Practical: choose load factor ~0.75–1.5, preallocate bucket arrays, consider using small-vector or pooled allocations to reduce GC/allocator overhead when millions of keys.

**Open addressing — linear probing** - Approach: on collision probe next slot sequentially. - Time: average O(1 / (1 − α)) (cost rises sharply as α → 1); worst O(n). Insert/delete (use tombstones) similar. - Memory: compact (no pointers), lower overhead. - Cache: excellent due to locality (good for CPU caches). - Practical: keep load factor ≤ 0.7, prefer power-of-two table sizes with proper hash scrambling, handle clustering (primary clustering can hurt).

**Open addressing — quadratic probing** - Approach: probe sequence using quadratic offsets (i + c1·k + c2·k^2). - Time: average O(1 / (1 − α)) but better than linear for clustering; worst O(n). - Memory/cache: compact; slightly worse locality than linear but better clustering behavior. - Practical: needs careful choice of constants and table size (often prime or power-of-two with algorithm tweaks) to ensure full probe coverage.

**Double hashing** - Approach: second hash gives step size; probe i + k·h2(key). - Time: average O(1 / (1 − α)), best at avoiding clustering; worst O(n). - Memory/cache: compact; probes more spread out so cache locality worse than linear but better overall probe count. - Practical: strong choice when low probe counts and space-efficiency required; ensure h2(key) is coprime to table size.

**Summary / Recommendations for millions of keys** - If memory tight and cache performance critical: open addressing (linear or double hashing) with low load factor. - If deletions are frequent or hash distribution unpredictable: separate chaining with pooled/contiguous buckets. - Always: use high-quality hash, reserve capacity up-front, benchmark with realistic workloads, and monitor resize/GC impact in production.

EasyTechnical

71 practiced

Explain the conceptual difference between a set and a map/dictionary. Give three backend use cases where a set is the better choice and three where a map is necessary. Discuss implementation variants (hash-set, tree-set) and when you might use a Bloom filter as an approximate set.

MediumTechnical

101 practiced

Given the following pseudocode, derive a tight asymptotic time complexity (Theta notation) as n grows:

for i = 1 to n: j = i while j <= n: j = j * 2

Explain your steps and reasoning. How does the result change if j is multiplied by 3 each iteration instead of 2?

Sample Answer

**Answer (brief)**

1) Approach & per-iteration cost- For a fixed i the inner loop multiplies j by 2 until j>n. Starting j=i, number of inner iterations t is smallest t with i * 2^t > n, so

t = ⌈ log_2 (n / i) ⌉ + 1

(plus constant for initial assignment).

2) Total cost- Sum t over i = 1..n:

T(n) = Σ_{i=1}^n Θ(1 + log_2 (n / i)) = Θ( n + Σ_{i=1}^n log_2 (n / i) )

- Rewrite sum:

Σ_{i=1}^n log_2 (n / i) = Σ_{i=1}^n (log_2 n - log_2 i) = n log_2 n - log_2(n!)

- Using Stirling, log_2(n!) = Θ(n log n), so the difference = Θ(n log n). Thus

T(n) = Θ(n log n)

3) If multiply by 3 instead of 2- Inner iterations become Θ(log_3 (n / i)) = Θ(log_2 (n / i)) up to constant factor 1 / log_2 3. Summation still gives Θ(n log n). Only constant changes.

Notes for backend context: This means the nested loop scales quasi-linear — acceptable for moderate n but problematic for very large inputs; consider restructuring (e.g., amortized analyses, skipping ranges) if this appears in request processing or batch jobs.

EasyTechnical

70 practiced

Compare arrays (contiguous memory) and singly-linked lists (node-based) for the following backend scenarios: (a) frequent indexed reads by position; (b) frequent insertions/removals in the middle given a pointer; (c) iterating over all elements to compute aggregates. For each scenario state typical time complexities for access/insertion/deletion and discuss memory layout, pointer overhead, cache locality, and practical trade-offs in garbage-collected vs manual-memory environments.

Sample Answer

**(a) Frequent indexed reads by position**

- Arrays: O(1) access, O(n) insertion/deletion at arbitrary positions (shifting). Contiguous memory, excellent spatial locality and CPU-cache friendliness. Low per-element overhead.- Singly-linked list: O(n) access (must traverse), O(1) insertion/deletion given previous node pointer. Node-based, pointer overhead (next reference) increases memory and hurts locality; many pointer-chasing cache misses.- Practical trade-off: For backend tasks needing random reads (e.g., routing tables, arrays of config), use arrays or dynamic arrays (ArrayList/vector). Linked lists rarely win here.

**(b) Frequent insertions/removals in the middle given a pointer**

- Arrays: O(n) for shifting; amortized O(1) only at end (push/pop). Not suitable if many middle edits.- Singly-linked list: O(1) insertion/deletion if you have the node (or previous). Good when order matters and you only move local pointers.- Memory/layout: lists use more heap allocations and pointer overhead; fragmentation can increase GC workload.- Trade-off: If locality and iteration matter, consider indexed structures (gap buffer, rope, B-tree) or chunked lists.

**(c) Iterating over all elements to compute aggregates**

- Arrays: O(n) iteration, best cache locality -> fastest in practice.- Singly-linked list: O(n) but pointer chasing makes it significantly slower in real-world due to cache misses and branch prediction penalties.- Memory and GC: In garbage-collected languages, many small node objects increase GC pressure (more roots, scanning, promotions). In manual-memory (C/C++), you pay allocation overhead but can use pooled allocations to reduce fragmentation and improve locality (object pools, arena allocators).

Overall practical guidance for backend developers:- Use arrays/dynamic arrays for indexed access and iteration-heavy workloads.- Use linked lists only when you truly need O(1) splicing with existing node pointers and can tolerate higher memory and worse iteration performance.- Consider hybrid/modern alternatives (deques, chunked arrays, trees) when you need both fast random access and frequent middle edits.

HardTechnical

73 practiced

Prove that append operations on a dynamic array that doubles capacity when full have amortized O(1) time per append. Provide an aggregate or accounting proof and compute an upper bound on the amortized number of element copies per insertion when starting from capacity 1. Also discuss how the bound changes for a growth factor c>1 or for additive growth.

Sample Answer

**Approach summary (why this matters for backend systems)** Resizing-cost guarantees let you choose dynamic arrays (vectors) for buffers, request queues, or in-memory caches with predictable throughput. I give both an aggregate proof and an accounting (potential) argument, compute a tight upper bound for doubling from capacity 1, then generalize to multiplicative factor c>1 and to additive growth.

**Aggregate proof (doubling, start cap = 1)** When capacity doubles, each element that exists at some point is copied only when its containing array is resized. Track total element copies over n appends: copies happen during full-array copies of sizes 1, 2, 4, ..., up to the largest power < n. So total copies C(n) ≤ 1 + 2 + 4 + ... + 2^{⌊log₂(n)⌋} < 2n. Formally:

text

C(n) < 2n

Thus amortized copies per append ≤ C(n)/n < 2. So amortized time per append is O(1) (constant number of element moves plus the O(1) actual insertion).

Plain-English: across n appends you do fewer than 2n element-copy operations, so average <2 copies per insert.

**Accounting (potential) proof** Charge each append 3 units:- 1 pays for placing the new element.- 2 are stored as credit on the newly inserted element.When a resize copies m elements into a new array of capacity 2m, each copied element uses 1 credit to pay its copy. Since each element was given 2 credits when inserted and will be copied at most once per doubling level, credits suffice. So constant charge (O(1)) per append covers future copies.

**Upper bound for doubling from capacity 1** Amortized element-copy bound ≤ 2 copies per insertion (more precisely < 2; tends to 2 from below). So amortized cost O(1).

**General multiplicative growth c>1** Total copies per element form geometric series with ratio 1/c. The amortized number of copies per insertion is bounded by:

text

amortized copies ≤ c / (c - 1)

Intuition: larger c reduces resize frequency so fewer copies; as c→1+ the bound blows up.

**Additive growth (increase capacity by +k each time)** Let k be constant. Number of resizes ≈ n / k, and the i-th resize copies Θ(i·k) elements, so total copies Θ((n/k)^2 · k) = Θ(n^2 / k). Amortized copies per insertion = Θ(n / k) — not constant. So additive growth yields amortized Θ(n) per append (bad for large n). For backend workloads with unknown peak sizes, multiplicative growth (e.g., doubling) is preferred to keep append O(1) amortized.

Unlock Full Question Bank

Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.

Join thousands of developers preparing for their dream job.