MediumTechnical

114 practiced

Explain how HyperLogLog estimates distinct items in a stream: include register structure, the role of hashing, and how multiple registers combine to yield an estimate. Given a 100KB memory budget and expected cardinality up to 1e9, propose HLL parameters (p) and estimate the expected relative error. Also explain how to merge sketches from shards.

Sample Answer

HyperLogLog (HLL) is a cardinality sketch that uses probabilistic counting with small fixed memory.

How it works (structure + hashing):- Hash each stream item with a good 64-bit hash to produce uniformly random bits.- Split the hash: the first p bits select one of m = 2^p registers; the remaining bits are used to compute rho(w) = the position of the first 1 (count of leading zeros + 1).- Each register M[i] stores the maximum rho seen for items mapped to that register (small integer; typically 6–7 bits suffice in practice).

Combining registers → estimate:- Compute Z = 1 / (sum_{i=1..m} 2^{-M[i]}).- Raw estimate E = alpha_m * m^2 * Z, where alpha_m is a bias-correction constant (depends on m).- Apply small-range correction (linear counting) when many registers are zero, and large-range corrections if E approaches hash-space limits.

Parameter choice given 100 KB budget and cardinality up to 1e9:- 100 KB = 100*1024 = 102400 bytes = 819200 bits.- If we allocate 6 bits/register, max registers ≈ 819200 / 6 ≈ 136533 → nearest power of two: choose p = 17 (m = 131072), which uses 131072 * 6 = 786432 bits ≈ 96 KB (fits).- Standard HLL relative error ≈ 1.04 / sqrt(m). For m = 131072: error ≈ 1.04 / 362.04 ≈ 0.00287 → about 0.29% (very small).

Practical notes:- Use 64-bit hashing to avoid collisions and ensure the rho computation has enough bits for large cardinalities.- Keep register bit-width ≥ ceil(log2(max rho)). With 64-bit hashes, rho ≤ 64 so 6 bits (0–63) suffice; some implementations use 8 bits for simplicity.- For expected cardinalities ~1e9, p=17 is plenty; HLL handles much larger values but check large-range correction if estimates approach 2^32 or higher depending on hash bits.

Merging sketches from shards:- HLL is trivially mergeable: to combine sketches from shards, take element-wise maximum of corresponding registers: M_merged[i] = max_j M_shard_j[i]. Then compute estimate from M_merged as usual. This is associative and commutative, so it supports distributed aggregation and fault-tolerant reduce operations.

Summary: pick p=17 (m=131072) under 100KB with 6-bit registers, expected relative error ≈ 0.29%; use 64-bit hash; merge by element-wise max.

HardSystem Design

86 practiced

You operate a geographically replicated key-value store with limited inter-region bandwidth but require linearizable writes. Propose protocol optimizations to reduce message count and bandwidth: e.g., leader leases for local reads, batching Raft/Appends, digest-only snapshots, or client-side leases. Analyze impacts on latency, freshness, and failure scenarios (leader loss, partition).

Sample Answer

Requirements & constraints:- Linearizable writes globally.- Limited inter-region bandwidth; want fewer cross-region messages and less payload.- Reads can favor local latency if safe.

High-level approach:Combine several orthogonal optimizations: leader leases for local reads, batching & append pipelining for Raft, digest-only snapshots, and careful client-side leases/caching with validation. Preserve linearizability by making any local shortcut conservative and fall back to global coordination on uncertainty.

Protocol optimizations and rationale:1. Leader leases for local reads- Region leader holds a lease (timestamped) from the global Raft leader or quorum. Local reads served without global round-trip while lease valid.- Impact: very low read latency and zero cross-region bandwidth for majority of reads. Freshness: linearizable if lease guarantees no concurrent leader elsewhere could commit earlier writes. If lease expires or on suspected clock skew, reads must require global validation.- Failure: on leader loss or partition, leases expire -> must redirect to global leader or read via quorum.

2. Batching Raft/appends + pipelining- Accumulate multiple client writes into single AppendEntries across regions; allow pipelined in-flight appends to amortize RTT.- Impact: reduces per-op bandwidth and CPU. Latency: slightly increases per-write queuing delay but improves throughput and effective latency under load.- Failure: larger batches mean more to replay on leader crash; use durable write-ahead log and small max-batch to bound recovery time.

3. Digest-only snapshots / meta-sync- Send compact digests (hashes, bloom filters, or vector of applied indices) across regions instead of full state for membership/consistency checks; full snapshot transfer only when needed.- Impact: huge bandwidth savings for anti-entropy and state verification; low latency for checks. Freshness unaffected if digests validated by quorum responses.- Failure: hash collisions improbable; fallback to full snapshot on mismatch.

4. Client-side leases/caching with validation- Clients cache recent read values with short TTL and include cached-version token on write/conditional operations. Validation uses leader/quorum to ensure version monotonicity.- Impact: reduces reads hitting servers and cross-region verification for hot keys. Freshness: slightly stale if TTL misconfigured; to keep linearizability, reads that must be linearizable either use leader-validated lease or perform a read-modify-write via leader.- Failure/partition: cached tokens rejected -> client retries to leader.

Trade-offs and failure handling:- Leader loss: revoke leases; leaders detect via heartbeat timeout and election; clients redirected. Use conservative lease durations (≤ election timeout/2) and synchronized clocks (NTP/Paxos clocks) to bound risk.- Network partition: local-region followers can serve stale reads only if they hold safe lease; otherwise deny or forward. Writes always require global quorum — in severe partitions, writes block to preserve linearizability.- Bandwidth vs freshness: longer leases and larger caches save bandwidth but increase window for stale reads if a concurrent leader arose; mitigate with short leases, lease renewals piggybacked on AppendEntries, and lease invalidation messages on leadership change.- Latency vs throughput: batching improves throughput and amortizes cross-region cost at expense of per-write queuing delay; choose adaptive batching based on load and SLOs.

Operational recommendations:- Instrument lease hit/miss, batch sizes, and digest mismatches; dynamically tune lease durations and batch windows.- Make optimizations configurable per key/tenant (hot keys get aggressive caching; critical keys require strict leader reads).- Ensure strong testing for leader-change races and use formal reasoning or model checking for lease invariants.

Summary:Combine conservative leader leases, batching/pipelining, digest-based snapshots, and client-side caching with validation. Each reduces inter-region messages/bandwidth but requires careful lease sizing, fallback to quorum operations, and robust handling of leader loss and partitions to retain linearizability.

EasyTechnical

93 practiced

On some embedded platforms, division is slow or unavailable. Describe practical methods to compute integer division and modulo without using / or %: e.g., shift-and-subtract (long division), multiplication by reciprocal using fixed-point precomputed multipliers, and table-lookup for small divisors. For each method, state performance, precision trade-offs, and appropriate use cases.

Sample Answer

Here are three practical approaches to compute integer division/modulo without using / or % on constrained embedded platforms, with performance, precision trade-offs, and recommended use cases.

1) Shift-and-subtract (binary long division)- Idea: Align divisor by left shifts and subtract while building quotient bits (like long division).- Performance: O(n) bit-steps (n = word bits). For small divisors or when using hardware shifts it’s predictable but slower than single-cycle divide.- Precision: Exact integer result (quotient and remainder) — no approximation.- Use case: When correctness is paramount, divisor varies at runtime, or hardware lacks multiply/reciprocal support. Good for small code size and deterministic timing.

2) Multiplication by reciprocal (fixed-point precomputed multiplier)- Idea: Precompute M ≈ floor(2^k / d). Compute q = (a * M) >> k with possible small correction; r = a - q*d.- Performance: Very fast: single multiply + shift (+ occasional correction). Excellent for repeated divides by the same constant.- Precision: Requires careful choice of k and correction to guarantee exactness for integers; without correction yields approximate/biased results.- Use case: Optimize division by constants (compile-time known). Ideal where multiply is fast (hardware multiplier) and you need high throughput.

3) Table lookup (quotient/remainder or reciprocal)- Idea: For small range of divisors or small dividend space, store precomputed quotient/remainder or multipliers.- Performance: O(1) access; fastest and predictable.- Precision: Exact if table built correctly; limited by table size.- Use case: Very small divisors (e.g., divide by 3..16), byte-sized inputs, or tight loops where memory trade-off is acceptable.

Trade-offs summary:- Shift-subtract: minimal memory, exact, slower.- Reciprocal multiply: high speed, low memory, needs careful fixed-point math and corrections.- Table: fastest, exact, high memory for large domains.

Pick based on frequency of operation, whether divisor is constant, available instructions (mul/shift), and memory budget.

MediumSystem Design

94 practiced

Design a backend system to handle 100,000 requests/sec with p95 latency <= 50ms. Servers are CPU-limited (small VMs). Describe architecture choices (stateless services, sharding), caching layers (CDN, edge cache, in-memory), request batching, offloading, and techniques to reduce CPU per request (precomputation, protocol optimization). Explain how to detect and gracefully degrade under overload.

Sample Answer

Requirements:- 100k req/s sustained, p95 ≤ 50ms, CPU-limited small VMs, high availability.- Assume mostly read-heavy API with some writes (adjust if different).

High-level architecture:- Edge: CDN + global load balancer (route 100k/s geographically).- API tier: stateless application servers behind autoscaling groups.- Data tier: sharded databases (read replicas) + write leader(s).- Cache tier: multi-layer caching (CDN → edge cache → regional in-memory cache → local L1).

Components & choices:1. Stateless services- Keep app servers stateless to autoscale quickly; store session state in Redis or JWT.- Use lightweight frameworks and native threads to reduce context-switch overhead.

2. Sharding and partitioning- Shard traffic by customer/tenant or key-hash across service pools and DB partitions to distribute CPU and I/O.- Consistent hashing to minimize re-sharding cost.

3. Caching layers- CDN for static content and cacheable API responses (cache-control, stale-while-revalidate).- Edge cache (regional POPs) for high-hit-rate content.- Regional in-memory cache (Redis cluster) for dynamic but hot objects.- Local process L1 cache (in-memory LRU) to avoid network hops for very hot keys.

4. Request batching and multiplexing- Batch upstream DB or downstream RPC calls when possible (e.g., bulk-get) to amortize per-request CPU.- Use HTTP/2 or gRPC with multiplexing to reduce connection overhead.

5. Offloading- Push heavy transformations to background workers or precompute.- Use CDN Workers / edge functions for simple logic (A/B routing, auth token validation) to save origin CPU.- Use async patterns: accept request, return 202, process in background for non-critical paths.

6. Reduce CPU per request- Precompute and materialize views for expensive joins; serve from cache.- Serialize compactly (protobuf instead of JSON) and use binary protocols to reduce parsing cost.- Avoid unnecessary allocations; use pooling and zero-copy where applicable.- Profile and optimize hot paths; use JIT tuning or native libs for heavy math.

7. Backpressure and overload detection- Instrument p95/p99 latency, request queues, CPU utilization, error rates, cache hit ratio.- Apply circuit breakers and rate-limiters at edge/load balancer per client/tenant.- Detect overload patterns: rising queue length, sustained CPU > 80%, increasing p95.

8. Graceful degradation strategies- Probabilistic sampling or shed low-value traffic (e.g., anonymous analytic events).- Serve stale cached responses (stale-while-revalidate) when origin slow.- Reduce feature set: return lightweight payload (omit non-essential fields) under overload.- Throttle per-tenant with fair queuing; return 429 with Retry-After when necessary.- Deprioritize background jobs and queue less critical work.

Scalability & trade-offs:- Trade CPU for latency: more aggressive caching reduces CPU but increases staleness.- Batching reduces per-op overhead but increases tail latency if waiting for batch window—tune batch size and time window.- Edge logic reduces origin load but complicates consistency.

Operational notes:- Load test to validate autoscaling behavior; add headroom (peak+30%).- Continuous profiling, hotkey detection, and automated runbooks for overload scenarios.- Roll out changes gradually with feature flags and monitor real user metrics (p95).

EasyTechnical

95 practiced

Explain the time-space trade-off between memoization and recomputation. Use two concrete examples: (a) naive Fibonacci recursive computation; (b) 0/1 knapsack dynamic programming. For each example explain when memoization is beneficial and when bottom-up or recomputation is preferable given a tight memory budget. Provide complexity (time and space) for both approaches.

Algorithm Design Under Constraints Questions

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Sample Answer

Unlock Full Question Bank