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
70 practiced
Explain the Count-Min Sketch data structure: layout of the array of counters, update and query pseudocode, error bounds, and how to choose width and depth given memory and desired error epsilon/delta. Discuss application to counting high-frequency metrics in SRE systems and how sketches can be merged across workers.
Sample Answer
Count-Min Sketch (CMS) is a compact probabilistic structure for approximate frequency counts. It uses a 2D array of counters with d rows and w columns, and d pairwise-independent hash functions h1..hd. Each row is a separate hash mapping; updates increment one counter per row, queries take the row-wise minimum to reduce overestimation.Layout:- counters[d][w] initialized to 0- hash functions hi(x) ∈ [0, w-1]Update and query pseudocode:
python
# params: counters[d][w], hash_funcs[0..d-1]
def update(x, c=1):
for i in range(d):
j = hash_funcs[i](x) % w
counters[i][j] += c
def query(x):
estimates = []
for i in range(d):
j = hash_funcs[i](x) % w
estimates.append(counters[i][j])
return min(estimates)
Error bounds:- For width w = ceil(e/epsilon), depth d = ceil(ln(1/delta)): - With probability ≥ 1-delta, estimate ≥ true_count and estimate ≤ true_count + epsilon * total_count.- CMS only overestimates (no underestimation) and error scales with total stream mass.Choosing w and d given memory M and desired (epsilon, delta):- Memory ≈ d * w * counter_size.- Set w = ceil(e / epsilon), d = ceil(ln(1/delta)); adjust for available memory by trading epsilon vs delta.SRE applications:- Count high-frequency metrics (e.g., per-IP requests, error keys) with bounded memory for cardinality-heavy streams.- Use for heavy-hitter detection (track items whose estimated count > threshold), burst detection, or top-k approximations combined with a heap.- Good for high-throughput ingestion where exact counts are too costly.Merging across workers:- CMS is mergeable: elementwise sum of corresponding counters from same (w,d,hash functions) produces a CMS representing the union stream. Ensure identical hash functions, same w/d, and same counter width to avoid bias.Practical notes:- Use 64-bit counters if totals can be large; consider conservative update variants or conservative decrementing to reduce error for heavy hitters.- Combine with exact small cache (lossy counting or heavy-hitter structure) for more accurate top-k.
HardSystem Design
100 practiced
Design an index for time-series data that supports fast range queries by time and tag filters (e.g., host=web01, service=auth). Consider using inverted indexes for tags, time-partitioned B-trees or LSM-trees, and segment metadata. Discuss read/write complexity, memory footprint, compaction costs, and why you would choose one approach in an SRE observability backend.
Sample Answer
Requirements & constraints:- Append-heavy writes (metrics/traces), high cardinality tags, frequent range queries by time + arbitrary tag filters, multi-tenant, SLOs for query latency, retention/TTL.High-level design:- Hybrid: inverted index for tags + time-partitioned LSM trees for samples.- Data is partitioned by fixed time windows (e.g., 1h segments). Each segment contains: 1) an LSM-tree (or time-ordered SSTables) storing samples keyed by (series_id, timestamp), 2) segment metadata (min_time, max_time, cardinality, tombstone ranges, bloom filters), 3) per-segment inverted posting lists (or pointers) mapping tag-value -> posting list of series_ids / chunk IDs.Write path:- Ingest: normalize tags -> compute series_id (hash) -> append sample to memtable for current time-segment -> update in-memory per-segment posting lists for new series_ids.- Flush memtable -> create SSTable; update segment metadata; background compaction merges SSTables and merges posting lists.Read path (query host=web01,service=auth, time=[t0,t1]):1. For each time segment overlapping [t0,t1], check metadata (bloom filters/min-max) to skip irrelevant segments.2. Use inverted index to fetch posting lists for host=web01 and service=auth, intersect them (efficient by choosing smallest list first, use skip-lists/bitmaps).3. For resulting series_ids, read LSM SSTables for that segment and scan only timestamps within [t0,t1] (use time index in SSTable).4. Merge results from segments and return.Complexity:- Writes: amortized O(1) per sample write to memtable; durable write cost includes WAL append and eventual compaction. LSM write amplification depends on compaction strategy (typically 2-10x).- Reads: - Tag-filter cost dominated by posting list sizes and intersection: O(sum(|posting_i|) + cost_intersection). Using compressed bitmaps (Roaring) intersection is fast ~O(size of compressed representation). - Time-scan cost proportional to number of returned samples plus small seeks per series per segment (random reads limited by SSTable layout and bloom filters).- Memory footprint: - In-memory: memtables, in-memory posting lists for recent segments, bloom filters, chunk caches. Using compressed bitmaps and partial in-memory indexes bounds memory. - On-disk: SSTables + compressed posting lists. Storage grows with retention; older segments can be compacted or downsampled.- Compaction costs: - CPU/IO heavy, increases write amplification and temporary disk. Use tiered/leveled compaction tuning: leveled for low read amplification on hot data, tiered or time-windowed compaction for immutable historical segments to avoid re-merging old data. - Per-segment compaction reduces global cross-time merges—good for time-series.Why LSM + inverted index for SRE observability:- Write-heavy workloads: LSM excels at high-throughput sequential writes and efficient WAL + memtable flush.- Tag filtering: inverted index (compressed bitmaps or posting lists) gives efficient multi-tag intersection and supports arbitrary tag queries common in observability.- Time partitioning + segment metadata allows fast pruning of irrelevant data and easier retention/compaction policies.- Tunable trade-offs: compaction strategy, segment size, bitmap compression let you tune for latency, throughput, and storage cost.- Operational advantages: append-only SSTables simplify crash recovery; time-window segments simplify TTL/retention and rebuilds for tenants.Alternatives & trade-offs:- Time-partitioned B-tree: better worst-case read latencies and lower compaction overhead, but poorer write throughput and heavier random I/O at scale—less suitable for high-cardinality, high-ingest observability.- Fully in-memory inverted index: fast queries but prohibitive memory for high cardinality; can be used as cache for hot series.- Use bitmaps (Roaring) vs posting lists: bitmaps are faster to intersect but suffer on extremely sparse high-cardinality tags—choose hybrid: bitmaps for dense tags, posting lists for sparse tags.Operational considerations:- Cardinality limits and sampling: enforce per-tenant tag cardinality or apply rollups/downsampling to control index size.- Autoscaling compaction workers, IO throttling, backpressure on ingest.- Background reindexing for schema changes; metrics around compaction lag and write amplification to monitor SLOs.Summary:For an SRE observability backend I’d choose time-partitioned LSM-trees for storage with per-segment inverted indexes (compressed bitmaps + posting lists) and rich segment metadata. This balances high write throughput, efficient tag-based queries, predictable pruning, and operational controls over compaction and retention—matching SRE needs for scalability, reliability, and tunable latency.
HardTechnical
146 practiced
Implement a data structure in Python that supports insert(val), delete(val), and get_random() in expected O(1) time. get_random should return a uniformly random element among current elements. Provide the implementation details, explain how to handle duplicates, and analyze complexity and memory usage.
Sample Answer
Approach: maintain a dynamic array (list) for O(1) random access and a hashmap from value -> set of indices in the array to support duplicates. On delete, swap the element-to-remove with the last element and update indices sets — all operations are expected O(1) amortized.
python
import random
from collections import defaultdict
class RandomizedCollection:
def __init__(self):
# values list stores current elements
self.values = []
# idx_map maps value -> set of indices in self.values
self.idx_map = defaultdict(set)
def insert(self, val):
"""Insert val. Return True if this is the first occurrence."""
first = len(self.idx_map[val]) == 0
self.values.append(val)
self.idx_map[val].add(len(self.values) - 1)
return first
def delete(self, val):
"""Remove one occurrence of val. Return True if removed."""
if not self.idx_map[val]:
return False
# remove arbitrary index of val
remove_idx = self.idx_map[val].pop()
last_val = self.values[-1]
# move last element into remove_idx if not removing the last
if remove_idx != len(self.values) - 1:
self.values[remove_idx] = last_val
# update last_val's index set
self.idx_map[last_val].remove(len(self.values) - 1)
self.idx_map[last_val].add(remove_idx)
# pop last element
self.values.pop()
# cleanup empty set to keep idx_map small
if not self.idx_map[val]:
del self.idx_map[val]
return True
def get_random(self):
"""Return uniformly random element. Raises IndexError if empty."""
if not self.values:
raise IndexError("get_random from empty collection")
return random.choice(self.values)
Key points:- Handles duplicates by storing all indices in a set for each value.- delete uses swap-with-last to avoid O(n) element shifts.Complexity:- insert: expected O(1) amortized (list append, set add)- delete: expected O(1) amortized (set pop/remove, list pop, constant updates)- get_random: O(1) (random.choice)Memory:- O(n) for the list + O(n) total for all index sets in the map (each element’s index stored once).
HardTechnical
72 practiced
You must implement cross-region deduplication for alerts that may be generated in different regions within seconds. Constraints: eventual consistency, bounded memory, and minimal added latency. Propose data structures and algorithms (time-bucketed bloom filters, counting bloom, CRDT approaches) to deduplicate with acceptable false positives, and analyze complexity, network cost, and consistency trade-offs.
Sample Answer
Requirements & constraints:- Deduplicate alerts across regions within seconds.- Eventual consistency acceptable.- Bounded memory and minimal latency added.- Accept some false positives (i.e., drop duplicate alerts occasionally) but avoid false negatives.Design summary:1) Local per-region time-bucketed Bloom filters (TBBF)- Each region maintains a sliding window of Bloom filters, one per short time bucket (e.g., 1s or 5s) for TTL = dedupe window (e.g., 60s). Insert alert fingerprint (hash of alert key + normalized fields) into current bucket.- To test: query all buckets in window locally. If present => treat as duplicate. Rotate & discard oldest bucket to bound memory.2) Cross-region approximate sync: periodic compact Bloom-exchange- Every T_sync (e.g., 1–5s) each region exports a compressed Bloom (or XOR-merged sketch) of its recent buckets for last W_sync (a few seconds) to peers or a lightweight aggregator.- Receiving region checks incoming Bloom(s) first before local accept; if remote says "seen", drop or de-dup with lower confidence.3) Counting Bloom for local deletions (optional)- Use counting Bloom for per-bucket if you need safe deletions when merging overlapping windows or handling replays. Use small counters (4 bits) to bound memory.4) CRDT alternative for stronger convergence- Use Observed-Remove Set CRDT per alert fingerprint with TTL: regions add element with timestamp; anti-entropy (gossip) merges. Memory bounded by garbage-collecting entries older than window. Higher network cost and bookkeeping; better for true convergence.Trade-offs and analysis:- False positives: Bloom filters cause FP => occasional suppression of unique alerts. Tune filter size and k to target low FP (e.g., <0.1%).- False negatives: Possible if sync latency > dedupe window or if bloom rotations drop entries; minimized by sizing window and sync frequency.- Latency: Local Bloom checks are O(k) hashes — microseconds. Cross-region sync adds T_sync latency only for detecting remote duplicates; accept local optimistic processing and retroactive suppression if needed.- Memory: O(m) bits per bucket; total = m * (window / bucket). Counting Bloom multiplies by counter bits.- Network cost: periodic export size ~m bits per region per T_sync. Can compress (bitset compression) and reduce by exchanging only aggregated recent buckets. CRDT gossip costs are higher (per-element metadata).- Consistency: Design is eventual. Tuning knobs: bucket size, window length, T_sync, Bloom size, k, and choice between bloom-exchange (lower cost, approximate) vs CRDT (higher cost, stronger convergence).Operational considerations:- Fingerprint stable (canonicalize alert fields, use 64–128-bit hash).- Monitor FP/FN rates, tune BF parameters, expose metrics (insert rate, filter saturation).- Backoff policy: when unsure (e.g., remote not reachable), accept alerts locally and mark possible duplicates for downstream dedupe or suppression.- Safety: For critical alerts, bypass dedupe or require stricter confirmation to avoid missing incidents.Conclusion:Use time-bucketed Bloom filters with short periodic cross-region Bloom exchange for low-latency, bounded-memory dedupe with acceptable false positives. Use counting Bloom for safe deletions and CRDT only if strong convergence outweighs network/CPU cost.
EasyTechnical
90 practiced
Explain why hash table operations are O(1) on average but can degrade to O(n) in the worst case. Give examples of pathological inputs, discuss the roles of load factor, hash function quality, and collision-resolution strategy, and relate it to SRE concerns such as high-cardinality metric keys and DoS via adversarial inputs.
Sample Answer
Hash table operations are O(1) on average because a good hash function spreads keys uniformly across buckets, so lookups/inserts examine only one or a small constant number of slots. Expected cost ~O(1 + α) where α = load factor (n/buckets). With α kept bounded (e.g., resizing at α≈0.75), average constant time holds.Worst-case O(n) happens when many keys collide into the same bucket, turning lookup into a linear scan. Pathological inputs:- Many keys with identical hash (e.g., deliberately chosen strings that collide).- Poor hash functions or small bucket counts causing clustering.- Adversarial inputs crafted to exploit hash weaknesses (real-world DoS).Role of factors:- Load factor: higher α → more collisions → slower ops; dynamic resizing keeps α low.- Hash function quality: cryptographic/strong universal hashes reduce collision probability; deterministic weak hashes are vulnerable to clustering.- Collision resolution: chaining degrades to O(n) if one chain is long; open addressing suffers probe sequence long runs under high load or clustering.SRE implications and mitigations:- High-cardinality metric keys (per-user/session labels) inflate memory and α — enforce cardinality limits, aggregation, cardinality-aware sampling.- Adversarial DoS: validate/limit input key space, use randomized or stronger hash functions, per-request rate limits, and fallback limits on bucket chain lengths.- Monitoring: track hash table sizes, load factor, tail latencies; alert on unusual growth or CPU spikes. Resizing and sharding hash tables across workers can bound worst-case impact.
Unlock Full Question Bank
Get access to hundreds of Data Structures and Complexity interview questions and detailed answers.
