Algorithmic Complexity & Code-Level Optimization Questions

Reasoning about the time and space complexity of code and applying local optimizations that materially change performance. Covers Big-O analysis and performance modeling, data-structure selection, hot-loop and allocation reduction, and knowing when an algorithmic change beats micro-optimization. Emphasizes performance-aware coding grounded in complexity rather than premature tuning.

MediumTechnical

86 practiced

A query with multiple optional WHERE clauses performs poorly because the planner chooses a bad plan. Explain strategies to improve performance: partial indexes, composite indexes, covering indexes, query rewriting, use of statistics, and query hints. Provide small examples showing when each strategy is applicable.

Sample Answer

When optional WHERE clauses make the planner pick a bad plan, apply targeted strategies so indexes and stats guide the planner toward efficient plans.

Partial indexes — create indexes that only cover rows relevant to a frequent predicate. Use when queries often filter the same condition.Example:

sql

CREATE INDEX ON orders (customer_id) WHERE status = 'active';
-- Good if many queries include WHERE status='active' AND customer_id=...

Composite indexes — order columns in the index to match common multi-column filters or sorts. Use when multiple columns are commonly used together.Example:

sql

CREATE INDEX ON events (user_id, created_at);
-- Helps WHERE user_id=? AND created_at BETWEEN ... and ORDER BY created_at DESC

Covering (index-only) — include columns needed by the query so it can be satisfied from the index without touching the table (Postgres: index must be able to return visibility).Example:

sql

CREATE INDEX ON products (category_id) INCLUDE (price, name);
-- SELECT name, price FROM products WHERE category_id=... can be index-only

Query rewriting — transform optional WHEREs into predictable patterns so planner can choose stable plans (e.g., normalize NULLs, avoid ORs that hinder index use).Example:

sql

-- Bad: OR prevents index use
SELECT * FROM t WHERE a = $1 OR $1 IS NULL;
-- Rewrite into two queries or use UNION ALL:
SELECT * FROM t WHERE a = $1
UNION ALL
SELECT * FROM t WHERE $1 IS NULL AND <other_predicates>;

Use of statistics — increase pg_stats_target or create extended statistics for correlated columns so planner has better cardinality estimates.Example:

sql

ALTER TABLE orders ALTER COLUMN amount SET STATISTICS 1000;
CREATE STATISTICS ord_usr (ndistinct, dependencies) ON user_id, status FROM orders;
ANALYZE orders;

Query hints / planner control — Postgres has limited hints; use set enable_... for testing or pg_hint_plan extension to force plans. Use sparingly and only after measurement.Example:

sql

SET local enable_seqscan = off; -- force index usage for testing
-- or use pg_hint_plan: /*+ IndexScan(t idx_name) */

When to pick which:- Partial: selective predicates that frequently appear.- Composite: repeat multi-column filters/sorts.- Covering: high read rate, small projected columns.- Rewriting: ORs, optional parameters, or patterns that defeat indexes.- Stats: wrong cardinality causing bad join/order choices.- Hints: last resort when planner can't be persuaded otherwise.

Always test with representative data, run EXPLAIN (ANALYZE, BUFFERS), and measure end-to-end latency.

MediumSystem Design

108 practiced

Design a caching strategy for a product detail API that must sustain 50k RPS and where roughly 10% of products are updated every hour. Discuss cache placement (client, CDN edge, origin), invalidation strategies (TTL, pub/sub, cache-busting), preventing stampedes, and trade-offs in consistency and freshness.

Sample Answer

Requirements & constraints:- Serve product-detail at 50k RPS with ~10% of products updated/hour (~0.028 updates/sec per product if 1M products; overall ~28 updates/sec).- Low latency for reads, reasonable freshness (minutes), cost-efficient origin load.

High-level multi-layer cache:1. Client/browser: short local cache + ETag/If-None-Match to permit 304s for unchanged content.2. CDN edge (primary read cache): caches full product JSON/HTML; edge TTL + stale-while-revalidate.3. Origin (app/cache tier e.g., Redis/ memcached + DB): authoritative. Use an in-memory cache for writes/reads consistency window.

Invalidation strategy (combined):- Default TTL: moderate (e.g., 5–15 minutes) to reduce origin hits.- Event-driven invalidation: on product update, publish invalidation message (Kafka/Redis PubSub) to a service that: - Issues CDN purge/prefetch for that product key (use surrogate keys to purge groups). - Updates origin cache (invalidate or write-through).- Cache-busting for schema/major changes: bump version in URL (/v2/product/{id}) so clients and CDN fetch new shape.

Preventing stampedes:- Stale-while-revalidate at the CDN: serve stale while asynchronously refreshing from origin.- Single-flight/coalescing at origin cache layer: first request triggers backend refresh; others wait or get stale.- Probabilistic early refresh: refresh some keys before TTL expires based on access frequency.- Circuit-breaker/backoff: rate-limit refreshes under origin overload.

Data flow:Client -> CDN edge cache (hit) -> serve.If miss/stale: CDN checks origin cache -> if miss: single-flight -> DB.

Scalability numbers / tradeoffs:- With 50k RPS and, say, 90% cache hit at CDN, origin sees 5k RPS; further origin caching (Redis) plus single-flight can reduce this to hundreds.- 10% hourly updates imply ~28 purge events/sec — manageable with batched invalidations and surrogate-key purges.

Consistency vs freshness trade-offs:- TTL + stale-while-revalidate yields low-latency reads but allows short-lived staleness (seconds–minutes). Good for most product details.- Event invalidation provides near-real-time freshness for updated items but increases invalidation overhead and cost (CDN purge rates).- Strong consistency (no caching or synchronous cache update) would guarantee freshness but can't meet 50k RPS cost/latency targets.

Operational notes / best practices:- Use surrogate-keys and batched purges to avoid per-item purge throttling.- Monitor cache-hit ratio, purge rates, origin CPU; tune TTLs and SWR window based on observed update/read patterns.- Implement metrics and dashboards (hit/miss, purge latency, refresh latency) and alert on origin saturation.- Start with conservative TTL + SWR + pub/sub invalidation for updated items; adjust as product SLAs and costs dictate.

MediumTechnical

75 practiced

You have 2000 concurrent HTTP requests arriving at your app cluster. Average DB latency per query is 20ms and the database supports up to 200 concurrent connections. Design connection pool sizing per app instance and explain trade-offs between latency, throughput, and resource limits. Show the calculation you use.

Sample Answer

Situation & assumptions:- 2000 concurrent HTTP requests arrive.- Each request issues one DB query with average DB latency = 20 ms (0.02 s).- DB supports up to 200 concurrent connections.- Number of app instances = N (not given); solution expresses per-instance pool as function of N and gives examples.- Aim for healthy DB utilization (~60–80%) to avoid queueing and tail latency.

Calculation / reasoning:- A single DB connection can handle ≈ 1 / 0.02s = 50 queries/sec (qps).- DB theoretical max throughput = 200 connections * 50 qps = 10,000 qps (but we shouldn’t run at 100%).- Target DB concurrent connections = 0.7 * 200 ≈ 140 (70% utilization).- Per-instance pool size = floor(target_connections / N) = floor(140 / N).

Examples:- N = 10 instances → pool ≈ 14 connections/instance.- N = 20 instances → pool ≈ 7 connections/instance.- N = 5 instances → pool ≈ 28 connections/instance.

Trade-offs:- Latency: larger pools reduce waiting for a connection and lower request tail latency, but only until DB capacity is reached. Above target utilization, queueing at DB increases latency sharply.- Throughput: DB max throughput is the bottleneck. Increasing pools across instances won’t increase throughput beyond DB capacity; it only increases concurrency and potentially contention.- Resource limits: each DB connection consumes memory/CPU on DB and app (threads). Too many connections can exhaust DB resources and increase context switching.- Complexity: small pools + async/non-blocking app design (reactive drivers) allow higher client-side concurrency with fewer DB connections by multiplexing requests.

Recommendations:1. Decide N (auto-scale). Use per-instance pool = floor(0.7*200 / N).2. Monitor DB connection usage, queue times, p99 latencies; adjust target utilization (60–80%) accordingly.3. Prefer async DB drivers or batching to reduce needed connections.4. Implement circuit breakers / backpressure when DB saturation indicators appear.

This approach balances latency, throughput, and resource limits while giving a clear per-instance sizing method.

EasyTechnical

89 practiced

Describe average-case versus worst-case complexity. Use quicksort and heapsort as concrete examples: explain why quicksort has different average and worst-case behavior, what inputs cause the worst case, and how average-case analysis is typically computed.

EasyTechnical

105 practiced

Explain big-O time complexity and why an O(n log n) algorithm like mergesort typically outperforms an O(n^2) algorithm like insertion sort for large inputs. Give an example where constant factors or small input sizes make O(n^2) acceptable and describe how you would validate your choice empirically in production.

Unlock Full Question Bank

Get access to hundreds of Algorithmic Complexity & Code-Level Optimization interview questions and detailed answers.

Join thousands of developers preparing for their dream job.