Assess the ability to analyze, compare, and optimize algorithmic solutions with respect to time and space resources. Candidates should be fluent in Big O notation and able to identify dominant operations, reason about worst case, average case, and amortized complexity, and calculate precise time and space bounds for algorithms and data structure operations. The topic includes recognizing complexity classes such as constant time, logarithmic time, linear time, linearithmic time, quadratic time, and exponential time, and understanding when constant factors and lower order terms affect practical performance. Candidates should know and apply common algorithmic patterns and techniques, including two pointers, sliding window, divide and conquer, recursion, binary search, dynamic programming, greedy strategies, and common graph algorithms, and demonstrate how to transform brute force approaches into efficient implementations. Coverage also includes trade offs between time and space and when to trade memory for speed, amortized analysis, optimization tactics such as memoization, caching, pruning, iterative versus recursive approaches, and data layout considerations. Candidates must be able to reason about correctness, invariants, and edge cases, identify performance bottlenecks, and explain practical implications such as cache behavior and memory access patterns. For senior roles, be prepared to justify precise complexity claims and discuss optimization choices in system level and constrained environment contexts.
EasyTechnical
73 practiced
Write a Python function that, given a sorted array of integers and a target value, returns any pair of indices whose values sum to the target. The function must run in O(n) time and O(1) extra space and should handle edge cases like empty arrays and duplicates. Explain correctness and complexity.
Sample Answer
Use the two-pointer technique: keep one pointer at the start and one at the end, move them inward depending on the current sum. This is O(n) time, O(1) extra space and works on sorted arrays (duplicates handled naturally).
python
def two_sum_sorted(nums, target):
"""
Given sorted list nums, return a tuple of indices (i, j) such that nums[i] + nums[j] == target.
Returns None if no such pair exists.
Time: O(n), Space: O(1)
"""
if not nums or len(nums) < 2:
return None
i, j = 0, len(nums) - 1
while i < j:
s = nums[i] + nums[j]
if s == target:
return (i, j) # any valid pair of indices
elif s < target:
i += 1
else:
j -= 1
return None
Correctness: Because the array is sorted, increasing i increases the sum and decreasing j decreases it; thus all candidate pairs are explored without revisiting. Duplicates are fine—pointers treat values independently by index. Edge cases: empty array, length 1, no pair -> return None. Complexity: single pass O(n), constant extra space O(1).
HardSystem Design
73 practiced
Design a model serving architecture to guarantee P95 latency under 50ms for a model whose GPU inference takes 30ms plus 10ms preprocessing and 5ms postprocessing per request. Consider cold starts, autoscaling, batching strategies, warm pools, caching, early-exit models, hardware choices, and how to measure and mitigate tail-latency sources.
Sample Answer
Requirements & SLA- P95 latency < 50 ms per request. Per-request work: preprocessing 10 ms (CPU), GPU inference 30 ms, postprocessing 5 ms = 45 ms baseline. That leaves ~5 ms for networking/queuing/overheads — tight, so design must minimize tail sources.High-level architecture- Edge/API layer (gRPC, TLS offload) → preprocessing service (CPU) → model serving cluster (GPU) → postprocessing & aggregator → clients/metrics.- Use colocated preprocessing on the same host as the GPU-serving pod to avoid extra network hops when possible.Key components & strategies1. Hardware & runtime- Use low-latency GPUs (e.g., NVIDIA A10/A2/T4 for inference or A100 with MIG slices). Use TensorRT/ONNX Runtime with optimized kernels and FP16/int8 quantization to reduce GPU inference below 30 ms if possible.- Prefer MIG or dedicated GPUs per critical low-latency model to avoid noisy neighbours.2. Cold starts & warm pools- Maintain a warm pool of hot replicas with model already loaded in GPU memory. Keep minimum N ready replicas per zone so cold-start is microseconds-level (no model load).- Container image kept warm; use fast snapshot restore if using VM-based warm starts.3. Autoscaling & capacity planning- Autoscale based on latency SLO (p95) and queue length, not just CPU. Use predictive autoscaling from recent arrival-rate trends with headroom for sudden spikes.- Keep a baseline capacity to cover expected P95 by load testing: required concurrent instances = ceil((RPS * service_time) / concurrency_per_replica) with margin.4. Batching strategies- For strict p95 latency, use tiny or no batching (batch size 1) to avoid waiting. If throughput needs increase, use dynamic batching with a max wait time (e.g., 2–5 ms), and enforce SLO-aware batch windows: allow batching only when queue latency + batch execution time <= remaining SLO budget.- Implement adaptive batching: if latency approaches SLO, disable batching.5. Caching & early-exit- Add result-cache for deterministic inputs or shard-level cache for frequent queries (e.g., embeddings). Cache lookup must be sub-ms.- Use cascade/early-exit models: cheap classifier that handles easy cases in <10 ms; forward hard cases to heavyweight GPU. This reduces average and tail load.6. Tail-latency mitigation- Prioritized queues and request hedging (duplicate to two replicas and use first response) for high-priority requests; use sparingly due to cost.- Avoid co-locating heavy background jobs with latency-critical pods.- Use real-time backpressure: reject or queue with graceful degradation when queueing time threatens SLO.7. Pre/postprocessing optimization- Parallelize CPU preprocessing across threads; use vectorized libraries and native code to hit ~10 ms budget. If preprocessing is variable, move deterministic parts to a front cache or edge.Measurement & observability- End-to-end tracing (distributed spans), record per-component latencies (network, preprocess, queue, GPU, postprocess).- SLO dashboards for p50/p95/p99, service-time histograms, capacity utilization, queue lengths.- Synthetic canary traffic with tail-focused tests; periodic chaos tests (kill replicas) to measure cold-start behavior.- Profilers to find outliers: GC pauses, kernel stalls, PCIe transfer times.Example numeric setup- Assume each replica can serve 20 req/s at batch=1 (45 ms + 5 ms margin). For 200 RPS steady-state, maintain baseline 12 replicas; keep 2–3 warm spare replicas for spikes. Autoscaler scales when 95th latency > 40 ms or queue length > threshold.Trade-offs- Dedicated GPUs and warm pools increase cost but are necessary to meet strict P95.- Aggressive batching improves throughput but increases latency tail — only enable when SLO margin exists.- Hedging reduces tail but increases resource usage.ConclusionCombine low-latency hardware and optimized runtime, warm pools + SLO-driven autoscaling, conservative batching, caching/early-exit, and deep observability. Continuously test tails with synthetic and production traces to tune autoscaling and batching policies so P95 stays < 50 ms.
EasyTechnical
143 practiced
Implement in Python a function that returns the maximum sum of any contiguous subarray of length k in an integer array. The implementation must be O(n) time and O(1) extra space. Include guard clauses for invalid k, negative numbers, and explain why sliding window yields the stated complexity.
Sample Answer
Approach: use a fixed-size sliding window of length k. Sum the first k elements, then slide the window right one element at a time by subtracting the element leaving and adding the entering element. Track the maximum seen. This is O(n) time and O(1) extra space.
python
def max_subarray_sum_k(arr, k):
"""
Return the maximum sum of any contiguous subarray of length k.
Guard clauses:
- k must be an int > 0
- k must be <= len(arr)
Works with negative numbers in arr (they are allowed).
Time: O(n), Extra space: O(1)
"""
if not isinstance(k, int):
raise TypeError("k must be an integer")
if k <= 0:
raise ValueError("k must be > 0")
n = len(arr)
if k > n:
raise ValueError("k cannot be greater than array length")
# initial window sum
window_sum = sum(arr[:k])
max_sum = window_sum
# slide the window
for i in range(k, n):
window_sum += arr[i] - arr[i - k] # add entering, remove leaving
if window_sum > max_sum:
max_sum = window_sum
return max_sum
Key points:- Sliding window updates sum in O(1) per step so whole algorithm is O(n).- Extra space is O(1) because we keep only running sums and indices.- Negative numbers in arr are handled naturally; the max may be negative if all values are negative.Edge cases:- k == n returns sum(arr)- Single-element k (k==1) returns max(arr)- k invalid (non-int, <=0, >n) raises errors as guarded above.
HardTechnical
134 practiced
Prove or explain the lower bound that any comparison-based sorting algorithm requires Omega(n log n) comparisons in the worst case, using the decision-tree model. Then discuss how non-comparison sorts such as radix sort avoid this bound and what assumptions are required to do so.
Sample Answer
Decision-tree proof (comparison model)- Model: any comparison-based sorting algorithm on n distinct keys can be represented as a binary decision tree. Each internal node is a comparison between two keys; each leaf corresponds to a possible total order (permutation) of the input.- Correctness requires at least one leaf per permutation, so the tree must have ≥ n! leaves.- A binary tree of height h has at most 2^h leaves; therefore 2^h ≥ n! ⇒ h ≥ log2(n!).- Use Stirling’s approximation: log2(n!) = Θ(n log2 n) (more precisely ≈ n log2 n − Θ(n)). Thus the worst-case number of comparisons (height h) is Ω(n log n).Intuition: comparisons can only gain 1 bit of information each; there are log2(n!) bits needed to identify the correct permutation.How non-comparison sorts avoid the bound- Radix/counting/bucket sorts are not limited to pairwise comparisons; they inspect key bits/digits or use direct indexing, exploiting more powerful operations.- Example: counting sort sorts integers in range [0..k] in O(n + k) time by counting occurrences; radix sort sorts w-bit keys by processing digits (e.g., base B) in O((n + B) · (w / log2 B)) or commonly O(n · w) for fixed w. For fixed-size keys (w = O(1) or w = O(log n)), radix can be O(n).- Assumptions required: - Keys are drawn from a finite domain (bounded range or fixed-length representation). - Constant-time random access and arithmetic on key digits (word RAM model). - Enough memory for counting/buckets.- Trade-offs: these algorithms break the comparison lower bound by relying on model-specific operations; if keys are arbitrary or only comparisons are allowed, the Ω(n log n) bound still applies.Practical note for ML engineers: for large datasets of fixed-size numeric IDs or hashed keys, radix/counting can dramatically speed up preprocessing; for arbitrary comparable objects (e.g., complex feature tuples without cheap digitization), use comparison-sort guarantees.
MediumTechnical
88 practiced
For a large knowledge graph with millions of nodes and weighted edges, compare BFS, Dijkstra, and A* in time and space complexity. Explain when each is appropriate, and describe how heuristic quality in A* affects explored node counts and therefore practical complexity.
Sample Answer
Definition / setup:- BFS: breadth-first search for shortest paths on unweighted (or unit-weight) graphs.- Dijkstra: single-source shortest paths for non-negative weighted graphs using a priority queue.- A*: best-first search using f(n)=g(n)+h(n) where h(n) is a heuristic estimating cost-to-goal.Time complexity (big‑O, worst case):- BFS: O(V + E) time, O(V) space (queue + visited). For millions of nodes this is linear in graph size.- Dijkstra: with a binary heap (typical) O((V + E) log V). With Fibonacci heap O(E + V log V) but higher constant factors. Space O(V) (distances + predecessor + heap).- A*: worst-case O((V + E) log V) (same as Dijkstra with priority queue) because a poor heuristic devolves to Dijkstra; space O(V) to store open/closed sets.When to use:- BFS: use when edges are unweighted or unit-weight and you need shortest hop-count. Very memory- and time-efficient for that case.- Dijkstra: use when edges have non-negative weights and you need all shortest paths from a source (or single-source to target without heuristic). Good general-purpose algorithm when no admissible heuristic exists.- A*: use when you have a specific start and goal, non-negative weights, and a domain-specific admissible (and preferably consistent) heuristic. A* focuses search toward the goal and can drastically reduce work versus Dijkstra on large graphs.Heuristic quality and practical complexity (A*):- Admissible: never overestimates true cost — guarantees optimality. Consistent (monotone) heuristics ensure nodes are expanded at most once.- Extremes: - h(n)=0 => A* == Dijkstra (expands like Dijkstra). - h(n)=h*(n) (perfect heuristic) => A* expands only nodes on an optimal path (minimal expansions).- Intermediate: the closer h(n) is to h*(n), the fewer nodes A* expands. Roughly, the number of expanded nodes grows exponentially with the error of the heuristic in many spatial graphs: small improvements in heuristic accuracy can yield large reductions in explored nodes and runtime.- Trade-offs: admissible but weak heuristics reduce benefit; inadmissible heuristics can cut expansions but risk suboptimal paths — acceptable only if optimality can be relaxed.- Practical notes: for huge graphs (millions nodes), memory for OPEN/CLOSED dominates. Use heuristics that are cheap to compute, consistent, and informative; combine with pruning, bidirectional search, hierarchical abstractions, or landmarks (ALT) to reduce expansions.Summary:- BFS for unit-weight shortests (O(V+E)), Dijkstra for non-negative weights (O((V+E) log V)), A* when you can supply a strong admissible heuristic — same worst-case as Dijkstra but often far faster in practice; heuristic quality directly controls explored-node count and thus practical runtime and memory.
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
