Recognizing Patterns and Selecting Algorithms Questions

Ability to recognize problem patterns and know which algorithm/data structure is appropriate. Includes pattern matching like 'this looks like a sliding window problem' or 'this is a backtracking problem'.

EasyTechnical

94 practiced

You must report approximate daily unique active users for millions of users with tight memory limits. Explain the HyperLogLog (HLL) algorithm pattern, how to choose the number of registers (m) for a target standard error, how merging across shards works, and trade-offs vs exact counting.

HardSystem Design

87 practiced

Design a time-series rollup algorithm and data layout to support multi-resolution queries efficiently (e.g., raw 1s for 7 days, 1m rollups up to 90 days, 1h rollups up to 3 years). Describe data structures (segment-tree-like, chunked pre-aggregates), compression methods, and query execution plan for arbitrary range aggregates. Explain trade-offs between write cost, storage, and query latency for SRE monitoring dashboards.

Sample Answer

Requirements & constraints:- Raw 1s for 7 days, 1m rollups up to 90 days, 1h rollups up to 3 years.- Support arbitrary-range aggregates (sum/count/avg/min/max/percentiles) with low dashboard latency.- High write throughput from many hosts, bounded storage/cost, durable.

High-level architecture:- Tiered time-series store with retention + rollup workers. - Tier A: raw samples (1s) kept 7d. - Tier B: 1m pre-aggregates kept 90d. - Tier C: 1h pre-aggregates kept 3y.- Ingest writes go to a write-ahead buffer and append to Tier A in chunked files (immutable segments). A background rollup pipeline consumes chunks to produce Tier B/C.

Data layout & structures:- Chunked blocks per metric per fixed time-span (e.g., 1h chunks for raw). Each chunk contains: - Header: time range, sample count, min/max, tombstones. - Index: lightweight segment-tree-like summary: hierarchical aggregates at multiple granularities inside the chunk (e.g., 1s→5s→30s→1m). This is essentially a small segment tree stored as array of precomputed aggregates to answer intra-chunk partial ranges quickly. - Payload: compressed samples.- Pre-aggregates stored as their own chunks keyed by (metric, resolution, start_time). Each pre-aggregate contains sum, count, min, max, histograms/TDigest for percentiles.- Indexes: time-ordered LSM-style index mapping (metric, resolution, time-range) → chunk file(s). A bloom filter per chunk for series existence.

Compression:- For raw numeric samples: Gorilla-like XOR compression for float/delta-of-delta for timestamps (excellent for high-cardinality hosts).- Within chunk, delta encoding + bit-packing for monotonic counters; dictionary/RLE for repeated values (e.g., same status).- For pre-aggregates, store fixed-width binary (no heavy compression) because they’re small and accessed often.- Optionally columnar layout for multi-field metrics to improve compression.

Rollup algorithm:- Rollup workers read completed raw chunks (e.g., hour-complete), compute fixed-window aggregates for 1m and 1h resolutions: - For each window, update sum, count, min, max, and merge TDigest/CKMS sketches for percentiles. - Idempotent write to pre-agg chunks (use versioned keys / compare-and-swap or append-only with reconciliation).- For monotonic counters, compute rate before downsampling (handle resets).

Query execution plan (arbitrary range):1. Normalize query: [t0, t1], requested aggregation + target resolution (or automatic).2. Choose tiles: greedy selection from highest-resolution pre-aggregates that fully cover subranges; fall back to finer resolution chunks for partial windows at edges. - Example: query 45 days: use 1h pre-aggregates for full hours in older days, 1m for more recent partial days, raw 1s for last 7 days if sub-hour precision needed.3. For each selected chunk: - If chunk has segment-tree summaries, answer intra-chunk fully from summaries; if not aligned, decompress only required sample ranges.4. Merge partial aggregates: sums and counts combine trivially; percentiles merge via TDigest; min/max keep extremes.5. If query needs rollup on-the-fly (e.g., custom interval), aggregate the chosen tiles into the final result.

Trade-offs:- Write cost vs query latency: - Eager rollups (compute every incoming sample into multiple resolutions synchronously) increase write latency and CPU but simplify queries and lower query latency. - Lazy/async rollups (background workers on completed chunks) lower write latency but queries for very recent data may need to read raw chunks and compute on-the-fly, increasing query latency.- Storage vs accuracy: - Keeping more raw data improves accuracy and supports ad-hoc aggregations but costs storage; heavier compression reduces storage at CPU cost. - Storing rich sketches (TDigest per tile) increases storage but speeds percentile queries.- Complexity vs reliability: - Segment-tree-like summaries per chunk accelerate partial reads but add write complexity and slightly higher chunk size. - Simpler layout (only whole-window pre-aggregates) easier to operate but forces more decompression during queries.

SRE considerations:- Ensure rollup idempotency and backfill path. Use deterministic chunk windows and checkpointed workers.- Monitor rollup lag; alert if rollups fall behind (dashboard SLA).- Autoscale rollup workers and storage tiering; use tiered cold storage for long-term 1h aggregates.- Provide metrics: rollup_latency, chunk_write_latency, query_p95, storage_per_metric to tune retention/compression.

Summary:- Use chunked immutable files with embedded small segment-tree summaries + Gorilla-like compression for raw; produce deterministic time-window pre-aggregates (sum/count/min/max + sketches) per resolution; query planner picks coarsest covering tiles and merges. Tune eager vs async rollups based on dashboard latency SLO vs write cost and storage budget.

EasyTechnical

73 practiced

You receive a stream of API request timestamps and an alert: 'More than N requests within any T-second window for user X'. Without writing code, explain how to recognize this as a sliding-window problem and pick which sliding-window variant you'd use (fixed window, sliding counter/deque, token bucket) for an SRE use case. Mention how you would handle late-arriving timestamps and clock skew between nodes.

Sample Answer

Recognizing the problem as a sliding-window one: the alert (“> N requests within any T-second window for user X”) asks about counts over any contiguous T-second interval, not just discrete buckets or long-term averages — that’s the definition of a sliding window. The practical choices are:

- Fixed window (simple time buckets): easy to implement and low overhead, but suffers boundary effects (two adjacent buckets can allow a 2× burst around the edge) — ok for low-cost monitoring where bursts aren’t critical.- Sliding counter / deque (exact window): maintain per-user timestamps in a deque or time-indexed counter and evict entries older than T. This gives exact detection of any T-second window and minimal false negatives — best for precise alerting and SRE incident detection.- Token bucket (leaky bucket): enforces/smooths sustained rate and allows controlled bursts; good for mitigation (rate-limiting) rather than exact retrospective alerts.

For SRE alerting I’d pick the sliding counter/deque variant for accuracy (detects any qualifying window). To scale, shard by user, cap per-user state, and use approximate data structures (count-min + sliding sketch) only if memory is constrained.

Handling late-arriving timestamps and clock skew:- Treat timestamps as event-time and use a watermark/allowed-lateness window (e.g., accept events late by up to L seconds). Buffer incoming events for L seconds before finalizing alerts; emit provisional alerts with “tentative” tags if immediate action is required.- Use monotonic clocks for processing-time ordering locally; synchronize system clocks with NTP/Chrony and include per-message source timestamps to reconcile skew.- In distributed systems, accept eventual correctness: emit immediate operational alerts for high-confidence cases, then reconcile historical windows during backfill and annotate incidents if late data changes severity.- For extreme skew or high lateness, fall back to processing-time heuristics or increase L to trade detection latency vs accuracy.

This balances accuracy for SRE diagnostics with operational cost and latency.

EasyTechnical

89 practiced

You must deduplicate event IDs in a high-velocity stream with constrained memory and long retention. Compare using an exact hash-set vs probabilistic structures like Bloom filters and Cuckoo filters. For each option, explain false positive / false negative characteristics, memory costs, and the scenarios in SRE where each is acceptable (e.g., idempotent ingestion pipelines or strict deduplication).

Sample Answer

Situation/task: Deduplicating event IDs in a high-velocity stream with constrained memory and long retention.

Exact hash-set- False positives/negatives: None (deterministic). No FPs, no FNs.- Memory cost: High — store every unique ID (hash table or persistent key-value). Cost grows linearly with retention and cardinality.- When acceptable: When strict correctness is required (billing, financial events, legal/audit traces) or when you can shard and scale storage (e.g., external KV like RocksDB, Bigtable, or Redis with sufficient memory/disk). Use when idempotency must be guaranteed.

Bloom filter- False positives/negatives: No false negatives (if implemented correctly), but has tunable false positive rate (FPR) — may declare new events as duplicates erroneously.- Memory cost: Very low for a given FPR; size = -n * ln(p) / (ln2)^2 bits (~1.44 * n * log2(1/p)).- When acceptable: Idempotent or best-effort pipelines where occasional dropped unique events are tolerable (metrics, logs sampling, non-critical analytics). Good for fast in-memory pre-filtering before backing store. Not acceptable where any dropped unique event is critical.

Cuckoo filter- False positives/negatives: No false negatives (for membership), supports deletions; FPR similar to Bloom but typically lower for small fingerprints. Deletions possible without full rebuild.- Memory cost: Comparable or slightly higher than Bloom for same FPR, often more space-efficient at moderate load factors due to compact fingerprints.- When acceptable: Streaming dedupe with need for deletions/TTL (sliding window retention) and tighter memory/FP trade-off. Good for SRE use-cases like rate-limiting, short-to-medium retention dedupe, or as cache before persistent store.

Practical pattern for SREs- Hybrid: use a compact probabilistic filter (Bloom/Cuckoo) as an in-memory first line to reduce load on an exact backing store (write-through to persistent hash-set/DB). This minimizes memory while keeping correctness for critical decisions.- TTL and sharding: use windowed filters + periodic rotation or sharded exact stores to bound memory for long retention.- Choose exact when correctness is non-negotiable; choose Bloom when you need ultra-low memory and can tolerate FPs; choose Cuckoo when you need deletions/TTL and lower FPR at similar memory.

MediumTechnical

65 practiced

Your alerting system generates 10k alerts per hour with many near-duplicates. Propose an algorithmic pipeline to cluster alerts in near real-time to reduce noise. Discuss feature extraction (text normalization, fingerprints, service id, stack trace), similarity measures, candidate algorithms (hashing, MinHash+LSH, streaming clustering), and how to evaluate cluster quality.

Sample Answer

Requirements & constraints:- Ingest ~10k alerts/hour, low-latency (near real-time: seconds–minutes), reduce duplicate noise while preserving distinct incidents, memory bounded, support retrospective re-clustering.

Pipeline (high level):1. Preprocessing & feature extraction2. Fingerprinting / embedding3. Candidate generation (approx nearest neighbors)4. Online clustering & aggregation5. Alert dedupe/notification & feedback loop (manual labeling)

Feature extraction (prioritized):- Text normalization: lowercase, remove timestamps/IDs using regex, normalize whitespace, map synonyms (HTTP 500 == server error).- Structured fields: service_id, host, region, environment, severity, metric name.- Stack traces: strip line numbers, keep function names and exception types; hash sequence order-preserving.- Context metadata: recent deploy_id, commit hash, correlated event IDs.Create a feature vector mixing categorical one-hot/ID features and token features from normalized message/stack.

Fingerprinting & similarity:- Locality-sensitive hashing on token sets: MinHash signature for bag-of-tokens (message + stack frames) to estimate Jaccard similarity quickly.- For structured fields, use exact-match or weighted equality (service match increases similarity).- Compose similarity = w_text * Jaccard_est + w_struct * structured_score + w_time * temporal_decay (exponential).

Candidate algorithms:- MinHash + LSH buckets for O(1) candidate retrieval per alert — good for large-scale near-duplicate detection.- Hash-based canonicalization: deterministic fingerprint from normalized message + top stack function -> immediate exact grouping for high-confidence duplicates.- Streaming clustering: maintain active clusters with centroid fingerprints and time-window TTL (sliding window). For each incoming alert: query LSH for candidates, compute composite similarity, if sim>threshold assign to cluster and update cluster signature; else create new cluster.- Use count-min sketch to track cluster frequencies and evict low-traffic clusters.- For smaller volumes or as a refinement, use online DBSCAN-like density clustering on embeddings (requires tuning).

Operational considerations & trade-offs:- Latency vs. recall: smaller LSH bands → fewer false negatives but more candidates and CPU.- Memory: store only cluster signatures + recent sample alerts; archive older clusters to cold storage.- Thresholds: choose conservative threshold for notifications, relaxed for internal grouping.

Evaluation:- Offline labeled dataset: precision/recall, F1 for duplicate detection.- Cluster purity, inverse purity, and adjusted rand index against ground truth.- Business metrics: % alert reduction, mean time to acknowledge (MTTA) change, false-suppression incidents.- A/B test: route a portion of alerts through clustering and monitor missed incidents and engineer satisfaction.- Continuous feedback: allow manual ungrouping/merging to retrain normalization rules and weights.

Monitoring & safety:- Emit metrics on cluster size distribution, new-cluster rate, assignment latency.- Circuit-breaker: if clustering error rate rises, fallback to raw alerts.This design provides low-latency, scalable near-duplicate clustering while allowing iterative tuning and human-in-the-loop corrections.

Unlock Full Question Bank

Get access to hundreds of Recognizing Patterns and Selecting Algorithms interview questions and detailed answers.

Join thousands of developers preparing for their dream job.