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
91 practiced
Define the following asymptotic time complexity classes and give one concrete algorithmic example for each: O(1), O(log n), O(n), O(n log n), O(n^2), O(2^n). Explain the difference between worst-case, average-case, and amortized analysis and provide one short example illustrating each concept.
Sample Answer
**Definitions & one concrete example each****O(1) — Constant time**- Definition: Time independent of n.- Example: Accessing an array element by index (arr[i]).**O(log n) — Logarithmic**- Definition: Grows proportional to log n (base irrelevant).- Example: Binary search on a sorted array.**O(n) — Linear**- Definition: Grows proportional to n.- Example: Single pass to compute feature means over dataset.**O(n log n) — Linearithmic**- Definition: n times logarithmic factor.- Example: Merge sort used to sort training examples.**O(n^2) — Quadratic**- Definition: Time proportional to n squared.- Example: Naive pairwise distance computation between n vectors.**O(2^n) — Exponential**- Definition: Doubles with each additional input element.- Example: Brute-force subset enumeration for feature selection.**Worst-case vs Average-case vs Amortized**- Worst-case: Upper bound on any input (e.g., quicksort worst-case O(n^2) with bad pivots).- Average-case: Expected cost over input distribution (e.g., quicksort average O(n log n) for random pivots).- Amortized: Average cost per operation over a sequence, guaranteeing overall bound (e.g., dynamic array append: occasional O(n) resizes but amortized O(1) per append).These distinctions matter in ML systems when choosing algorithms for preprocessing, hyperparameter search, and real-time inference where predictable latency or expected throughput affects design.
EasyTechnical
121 practiced
Explain how dynamic arrays (resizable arrays) implement the append operation in common languages such as Python list or Java ArrayList. Describe the memory layout differences compared to linked lists, explain a geometric resizing strategy such as doubling, derive the amortized time complexity for a sequence of n appends, state the worst case cost for a single append, and discuss memory overhead and fragmentation effects in practice.
Sample Answer
**Approach / memory layout**Dynamic arrays (Python list, Java ArrayList) store elements in a contiguous block of memory. Compared to linked lists (nodes with pointers scattered on heap), arrays give O(1) index access and much better cache locality; linked lists have O(1) insert at arbitrary position given node but poor locality and extra pointer overhead.**Geometric resizing (doubling)**When capacity is full, allocate new array of size 2 * capacity and copy elements over. This growth strategy keeps reallocations infrequent.**Amortized cost derivation**If capacity doubles, the total number of element copies after n appends is bounded by:
text
1 + 2 + 4 + ... + n/2 < 2n
So total work for n appends is O(n) gives amortized O(1) per append.Plain statement:- Amortized time per append = O(1)- Worst-case time for a single append (when resize occurs) = O(n) due to copying**Memory overhead & fragmentation**- Average allocated capacity is up to ~2x the in-use size (so ~50% wasted on average with doubling). Some implementations use 1.5× to trade memory vs frequency of copies.- Contiguous allocation can cause external fragmentation or allocation failure under memory pressure, unlike linked lists that allocate many small nodes.- In practice, arrays perform better for ML/data pipelines because contiguous layout improves CPU cache and vectorized operations (e.g., filling, memcpy, SIMD), important for high-throughput workloads.**Practical notes for Applied Scientist**Prefer contiguous buffers (arrays, numpy) for numeric workloads for locality and BLAS/SIMD efficiency; choose resizing factor based on memory vs copy-cost trade-offs.
MediumTechnical
93 practiced
Implement an LRUCache class in Python with fixed capacity. Provide get(key) and put(key, value) methods that run in O(1) average time. Do not use OrderedDict; implement a hashmap plus a doubly linked list for O(1) eviction and update. Specify behavior for missing keys and for updating existing keys.
Sample Answer
**Approach (brief)**Use a hashmap (dict) mapping key -> node and a doubly linked list with head (most recent) and tail (least recent). get moves node to head; put inserts or updates and moves to head; when capacity exceeded remove tail and delete from hashmap. Missing key -> return -1. Updating existing key -> update value and mark as most-recent.**Code**
python
class Node:
def __init__(self, k, v):
self.k = k; self.v = v
self.prev = None; self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.map = {} # key -> Node
# dummy head/tail to simplify ops
self.head = Node(0,0)
self.tail = Node(0,0)
self.head.next = self.tail
self.tail.prev = self.head
def _remove(self, node):
p, n = node.prev, node.next
p.next, n.prev = n, p
def _add_to_head(self, node):
node.next = self.head.next
node.prev = self.head
self.head.next.prev = node
self.head.next = node
def get(self, key: int) -> int:
node = self.map.get(key)
if not node:
return -1
# move to head (most recent)
self._remove(node)
self._add_to_head(node)
return node.v
def put(self, key: int, value: int) -> None:
node = self.map.get(key)
if node:
node.v = value
self._remove(node)
self._add_to_head(node)
else:
if len(self.map) >= self.cap:
# evict LRU (tail.prev)
lru = self.tail.prev
self._remove(lru)
del self.map[lru.k]
newn = Node(key, value)
self.map[key] = newn
self._add_to_head(newn)
**Key points & complexity**- get/put average O(1) using dict + O(1) linked-list ops- Space O(capacity)- Missing key: get -> -1- Updating existing key: update value and promote to most-recent**Edge cases**- capacity <= 0 (could raise ValueError or treat as zero-capacity cache)- concurrent access requires locking (if used in multithreaded production)
EasyTechnical
68 practiced
Describe the two main collision resolution strategies for hash tables: separate chaining and open addressing. For each method explain insertion, lookup, and deletion complexity in average and worst case, how load factor affects performance, and scenarios where one strategy is preferable given memory constraints and predictable workloads.
Sample Answer
**Overview**As an applied scientist I'll choose collision strategy based on memory, latency guarantees, and workload predictability. Two main strategies: Separate chaining and Open addressing.**Separate chaining**- Mechanism: each bucket holds a linked list or dynamic array of entries.- Complexity: - Average (with good hash): insertion O(1), lookup O(1), deletion O(1) — constant-time proportional to 1 + load factor α. - Worst-case: O(n) if many collisions (all keys in one bucket).- Load factor: performance degrades linearly with α; resizing (increase bucket count) keeps α small.- When preferable: memory abundant or keys are large/variable; workloads with many deletions (easy removal) or when simpler concurrency (per-bucket locks) is desired.**Open addressing**- Mechanism: store entries directly in table; on collision probe (linear, quadratic, or double hashing).- Complexity: - Average: insertion/lookup/deletion O(1) if α is low; constant grows as α→1. - Worst-case: O(n) (clusters or full table).- Load factor: highly sensitive — performance deteriorates quickly as α > ~0.7 (depends on probe). Deletions need tombstones or rehashing.- When preferable: tight memory constraints (no per-element pointer overhead), predictable static workloads (few deletions, known max size), better cache locality.**Practical guidance for applied scientist**- If models require compact in-memory maps and workload is read-heavy with predictable size → open addressing (double hashing) for cache benefits.- If frequent updates/deletes and unpredictable key counts → separate chaining to avoid tombstone complexity and support concurrent updates.
MediumTechnical
82 practiced
A production Python service is experiencing periodic slowdowns traced to dict operations under certain input patterns. Explain how worst-case behavior in hash tables can arise from collisions, how an adversary could trigger pathological behavior, and propose mitigations at the language and application level to restore predictable performance.
Sample Answer
**Situation & brief root cause**Hash tables (Python dict) expect uniformly-distributed hash codes. If many keys collide (same hash modulo bucket count), lookups/insertions degrade from average O(1) to O(n) in the number of colliding keys because the engine must probe or scan chains to resolve collisions.**How an adversary triggers it**An attacker generates many distinct keys whose hash values collide (e.g., controlled strings with chosen suffixes) and submits them as inputs (API parameters, feature names, etc.). Python historically added per-process hash salt (PYTHONHASHSEED) to make offline collision crafting harder, but targeted inputs can still cause pathological collisions in some contexts.**Mitigations — language/process level**- Ensure hash randomization is enabled (PYTHONHASHSEED != 0). This makes precomputed collision sets ineffective across processes.- Upgrade Python to a version with robust dict implementation (recent CPython has optimized probing).- Where predictable worst-case matters, use data structures that guarantee bounds (e.g., use balanced trees like sortedcontainers, or libraries with worst-case guarantees).**Mitigations — application level**- Validate and rate-limit untrusted inputs (reject huge numbers of distinct keys in a single request).- Shard maps: use multiple smaller dicts (by hashing into k buckets) so worst-case work is limited per shard.- Replace a single large dict of untrusted keys with alternative structures: a trie for strings, a probabilistic structure (Bloom filter) to pre-filter, or map keys to integers before use.- Detect anomalies via runtime metrics (latency spikes correlated with high insertion rates) and fall back to protective mode (circuit-breaker).**Example detection + quick fix**- Profile with pyinstrument/tracing to confirm dict ops are hot.- Quick app patch: if len(new_keys) > threshold per request, reject or batch; long-term: use sharding or sortedcontainers.SortedDict for guaranteed O(log n).Why this matters for an Applied Scientist: adversarial input can bias training/feature pipelines and distort experiments; applying these mitigations preserves reproducibility and production stability while balancing performance and security.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
