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
97 practiced
You're tasked to detect CPU usage spikes: given an array of per-second CPU usage percentages and integer k, implement a function in Python to compute the maximum average CPU usage over any contiguous window of size k. Aim for O(n) time and O(1) extra space. Explain edge cases and numerical precision considerations.
Sample Answer
Use a sliding-window sum to maintain the sum of the current k-second window; update it in O(1) per step to get O(n) time and O(1) extra space.
python
def max_average_cpu(cpu, k):
"""
cpu: list[float] or list[int] - per-second CPU percentages (0..100)
k: int - window size (seconds)
Returns the maximum average over any contiguous window of size k.
Raises ValueError for invalid inputs.
"""
n = len(cpu)
if k <= 0 or k > n:
raise ValueError("k must be between 1 and len(cpu)")
# initial window sum
window_sum = sum(cpu[0:k])
max_sum = window_sum
for i in range(k, n):
window_sum += cpu[i] - cpu[i - k] # slide the window forward
if window_sum > max_sum:
max_sum = window_sum
return max_sum / k # average as float
Key points:- O(n) time: one pass after computing first sum. O(1) extra space: only a few scalars.- Works with ints or floats; returns float average.Edge cases:- k == n returns average of entire array.- k <= 0 or k > n: invalid.- Empty cpu list: invalid unless k==0 (not allowed here).Numerical precision:- Use float for sums if inputs are floats. For very long arrays or large magnitudes, consider using math.fsum for better precision:
- If percentages are bounded (0–100), standard double precision is sufficient for practical monitoring.
HardTechnical
119 practiced
Compare LRU, LFU, and LRU-K cache eviction policies. For each, describe worst-case and average-case behavior, implementation complexity, and scenarios where one outperforms the others. For LRU-K, explain how K and history window size affect hit rate and metadata overhead, and provide complexity analysis of maintaining policy metadata.
Sample Answer
Situation: Comparing eviction policies LRU, LFU, and LRU-K from an SRE perspective — I’ll describe behavior, complexity, when each shines, and for LRU-K how K and history window trade off hit rate vs metadata.LRU (Least Recently Used)- Behavior: Evicts the item with oldest access time.- Worst-case: Poor with scan/one-off patterns (large sequential scans flush hot items) → low hit rate.- Average-case: Strong for temporal locality workloads (web sessions, recent reads).- Implementation: Doubly-linked list + hash map → O(1) get/put, metadata O(N) (prev/next pointers + timestamp optional).- When better: Simple caches, predictable recency-dominant workloads, low implementation cost.LFU (Least Frequently Used)- Behavior: Evicts items with lowest access frequency.- Worst-case: Frequency pollution — old but once-hot items may persist; cold-heavy workload shifts slowly.- Average-case: Good for long-term popularity; outperforms LRU when access frequency is stable.- Implementation: Counter per key, often with frequency buckets (O(1) amortized with specialized structures like min-heap alternatives or ordered maps). Metadata O(N) counters; updating costs higher than LRU if counters unbounded.- When better: Hot-spot caches where popular items remain popular (e.g., CDN object popularity).LRU-K- Behavior: Tracks the time of the K-th most recent access; evicts items with oldest K-th access. Captures both recency and frequency by requiring K accesses to promote an item.- Parameters trade-offs: - K: larger K prefers long-term popularity (reduces noise from short bursts); K=1 reduces to LRU. Increasing K usually raises hit rate for stable hot items but increases metadata and latency to consider items “hot.” - History window (time or count): limits how far back accesses matter. A shorter window reduces metadata and forgets very old accesses (useful when popularity shifts); longer window increases hit rate for items with sparse but regular accesses but increases storage and processing.- Metadata & complexity: must store up to K timestamps (or compressed counters) per item → O(KN) storage. Maintenance per access: append timestamp and possibly evict oldest timestamp (O(1) with circular buffer). Selecting eviction candidate requires ordering by K-th timestamp — maintain a priority queue keyed by K-th timestamp or an approximate structure; updates to key in priority queue are O(log N). With bucketed or segmented approaches you can get amortized O(1) but with more complexity.- Worst/average-case: Worst-case when many items have similar K-th timestamps leading to churn and high update cost; average-case improves hit rate compared to LRU and LFU for mixed workloads (transient scans + stable hot items).SRE implications and choice:- Use LRU for simple, memory-constrained caches and workloads dominated by recency.- Use LFU when popularity is stable and you need to retain long-term hot items (e.g., auth tokens, popular API responses).- Use LRU-K for mixed workloads where you want to filter out one-off accesses but still react to repeated access patterns; tune K and window: small K (2–3) and moderate window for many services. Beware metadata overhead and choose approximate variants (count-min sketches, TinyLFU) or sampled LRU-K to reduce cost in large-scale distributed caches.Complexity summary:- LRU: O(1) ops, O(N) metadata.- LFU: O(1) amortized with frequency-bucket implementation; naive heaps O(log N); metadata O(N) counters.- LRU-K: per-access O(1) for timestamp insert, O(log N) if maintaining global K-th-ordering; metadata O(KN). Approximate variants trade some accuracy for lower cost.Edge operational notes: For distributed caches, prefer approximations to keep network/replication cost down; monitor eviction/invalidation metrics and adapt K/window with A/B tests to meet SLOs for cache hit rate and latency.
EasyTechnical
85 practiced
In practice, hash map operations are often described as 'O(1)', but may degrade. As an SRE, explain average-case and worst-case time complexity of hash table operations (lookup/insert/delete). Discuss causes of worst-case behavior (collisions, adversarial inputs) and mitigation strategies (rehashing, better hash functions, switching to balanced trees after thresholds).
Sample Answer
Average-case: O(1) per lookup/insert/delete. Reason: with a good hash function and load factor α = n / m (n items, m buckets) the expected bucket length is O(α), so operations examine a constant number of entries.Worst-case: O(n). If many keys map to the same bucket (all collisions), operations degenerate to scanning a long list (or tree) of size n. Adversarial inputs can force pathological collisions if the hash is predictable.Causes of worst-case behavior:- High load factor (table too full)- Poor or non-random hash functions- Intentional collision attacks (malicious clients)- Implementation using simple chaining with linked listsMitigations an SRE should know and apply:- Maintain target load factor and rehash (grow) proactively to keep α low- Use strong, randomized or salted hash functions to resist adversarial inputs- Use alternative collision resolution: open addressing with probing patterns that degrade less, or chaining with buckets that switch to balanced trees (e.g., Java’s HashMap switches to red-black tree after threshold) so worst-case becomes O(log n)- Enforce client-side rate limits and input validation to minimize adversarial load- Monitor metrics: bucket distribution, max chain length, latency tail, and trigger autoscaling or rehashing when anomalies appear- Test with adversarial datasets during load testingAs an SRE, combine algorithmic mitigations with operational controls (monitoring, throttling, safe defaults) to keep hash-table performance predictable.
HardTechnical
80 practiced
You must schedule a rolling upgrade of thousands of microservice instances with dependency constraints (some services must remain available for others). Formulate this as an optimization or scheduling problem, discuss complexity (is it NP-hard?), propose practical heuristics (topological waves, capacity-preserving batches, weighted priorities), and analyze runtime and quality of heuristics.
Sample Answer
Problem formulation:- Model services as directed dependency graph G=(V,E) where edge u→v means v depends on u (u must remain sufficiently available while v is upgraded).- Each node i has instances n_i, upgrade time t_i, and capacity contribution c_i per instance. Global constraint: at any time, for every service v, sum of available capacity of each dependency u ≥ required threshold R_{v,u} (e.g., 50% of pre-upgrade capacity).- Objective: minimize makespan (total wall-clock upgrade time) or weighted downtime cost Σ_i w_i * downtime_i subject to availability constraints and parallelism limits (max concurrent upgrades K).Complexity:- This generalization reduces to Scheduling with Precedence Constraints and Resource Constraints (multi-resource), and to Partition/Multiprocessor Scheduling when thresholds fixed — known NP-hard. So optimal scheduling is intractable at large scale.Practical heuristics (SRE-friendly):1) Topological waves: - Compute a topological order of condensed SCCs; upgrade layer-by-layer (wave = nodes with no unmet prerequisites). - Within a wave, upgrade services in parallel respecting capacity thresholds. - Runtime: O(|V|+|E|) to compute waves; scheduling per wave linear. - Quality: preserves dependency order, simple, conservative (may be suboptimal parallelism).2) Capacity-preserving batches: - For each service, upgrade in small batches b (percentage or fixed instances) so dependency capacities never drop below thresholds. - Greedy pack: pick batches across services maximizing parallelism while satisfying R_{v,u} and K. - Runtime: O(iterations * V log V); iterations ≈ total_instances / b. - Quality: good availability, near-optimal makespan if batches large enough and packing effective.3) Weighted-priority scheduling: - Assign priority p_i = w_i/t_i or based on SLO impact; use greedy list scheduling that picks highest priority batches that fit capacity constraints. - Combine with back-off: if a chosen batch would violate thresholds, try next candidate. - Runtime: O(total_batches log V). - Quality: balances SLOs vs time; not optimal but effective in practice.Hybrid approach:- Use topological waves to respect hard dependencies, inside waves run capacity-preserving, weighted-priority batch packing. Add safety: health checks, canary first, auto-rollback, and real-time feedback to adapt batch size.Empirical considerations:- Test in canary staging to tune batch size and priority weights.- Monitor latency/error budgets; loop: if errors rise, reduce concurrency or pause.- Heuristic quality improves with accurate capacity models; worst-case can be arbitrarily suboptimal but typically within small factor in practice.
MediumTechnical
94 practiced
Compare token bucket and leaky bucket algorithms for API rate limiting. Describe implementation details, per-request time and space complexity, burst handling, fairness, and performance. For distributed enforcement across multiple stateless frontends, propose algorithmic approaches and analyze consistency, latency, and correctness trade-offs.
Sample Answer
High-level summary:- Token Bucket: capacity C tokens, refill at rate r. A request consumes tokens; allowed if tokens ≥ cost. Allows bursts up to C and enforces average rate r.- Leaky Bucket (queue-based / rate-limiter form): treats incoming requests as water into a fixed-rate drain. Excess is queued (or rejected) and drained at constant rate; enforces a hard output rate with bounded queue.Implementation details:- Token Bucket (in-memory single node) - State: current_tokens (float), last_refill_time (timestamp) - On request: refill = (now - last_refill_time)*r; tokens = min(C, tokens+refill); if tokens >= cost → tokens -= cost → allow else reject. - Per-request time: O(1). Space: O(1) per key (e.g., per-client).- Leaky Bucket (simple counter/drain) - State: queue_size or last_drain_time + backlog - On request: compute drained = (now - last_drain_time)*drain_rate; backlog = max(0, backlog - drained); if backlog + 1 ≤ queue_limit → enqueue/allow else reject. - Per-request time: O(1). Space: O(1) for counters or O(n) if storing queued items.Burst handling:- Token bucket: permits bursts up to capacity C instantly. Good for clients that need short spikes.- Leaky bucket: smooths traffic strictly; bursts are either buffered up to queue_limit or rejected — more even output but less permissive to bursts.Fairness and performance:- Fairness: Both can be per-client keyed; fairness across clients depends on partitioning keys and enforcement placement. Token bucket can starve small continuous consumers if a bursty client consumes tokens; implement per-client buckets or weighted tokens to ensure fairness.- Performance: Both are O(1) and low-latency when local in-memory. Leaky bucket may require tracking backlog; token bucket needs floating arithmetic.Distributed enforcement across stateless frontends:Challenges: consistency of token count across frontends, low latency, correctness under concurrent requests.Approaches:1) Centralized state (single Redis/DB per key) - Use atomic operations (Lua script INCR/GET with TTL or Redis token-bucket script). - Consistency: strong (if master reachable). - Latency: extra network hop per request → higher tail latency. - Correctness: good, supports precise limits; single-point throughput limits and availability risk.2) Sharded keys to specific frontends (sticky hashing) - Route a client’s requests to a designated frontend that holds local bucket. - Consistency: strong per-client, low latency. - Trade-offs: reduced load balancing flexibility; failure of a frontend requires reassign/reset handling.3) Distributed approximate counters (local tokens + periodic refill sync) - Each frontend holds local token bucket with capacity C_local = C_global/N + burst allowance. Refill centrally or via gossip. - Consistency: eventual/approximate (may allow slight overage). - Latency: low (local), high correctness risk under skewed traffic.4) Leases with central coordination (token grants) - Frontends request token grants from central service in batches (e.g., lease 100 tokens), consume locally until exhausted. - Consistency: good amortized, reduces central load. - Latency: lower than per-request central, but grants create coarse-grained correctness windows (possible short-lived over-alloc).5) Hybrid (fast-path local, slow-path central) - Allow local consumption up to local reserve; overflow consults central authoritative store. - Balances latency and correctness.Analysis of trade-offs:- Strong correctness requires central coordination or routing guarantees; costs: increased latency, central throughput/availability concerns.- Low-latency local enforcement trades correctness: to avoid false rejections/overages, tune local capacity and refill granularity; monitor and reconcile overages asynchronously.- Availability: central store must be highly available (clustered Redis). Use retries and degrade policy (fail-open vs fail-closed) depending on SLOs.- Monitoring & mitigation: emit metrics for rejections, overages, token grant usage; use adaptive throttling and fallback to global enforcement if local anomalies detected.Recommendation for SRE:- For strict global limits (billing/security): use atomic central enforcement (Redis Lua scripts) or lease-based grants with strong monitoring and graceful degradation.- For low-latency per-client smoothing: use sticky routing or local token buckets with conservative local allocation and periodic reconciliation.- Always instrument limits, expose telemetry, and design fail-open/closed policies consistent with business risk.
Unlock Full Question Bank
Get access to hundreds of Algorithm Analysis and Optimization interview questions and detailed answers.
