Handling Problem Variations and Constraints Questions

This topic covers the ability to adapt an initial proposed solution when an interviewer introduces follow-up questions, new constraints, a changed goal, or a much larger scale of the problem. Candidates should quickly clarify what exactly changed, analyze how it affects correctness, quality, and complexity, and propose concrete modifications, such as choosing a different method, tool, or structure, adding buffering or caching, introducing parallel or incremental processing, or adopting approximation and heuristics when an exact solution becomes impractical. They should articulate trade-offs between speed, resource usage, simplicity, and robustness, explain how they would validate the modified solution and handle edge cases, and describe incremental steps and fallback plans if the primary approach becomes infeasible. Interviewers use this to assess adaptability, structured problem solving under evolving requirements, and clear communication of design decisions, regardless of technical domain.

EasyTechnical

25 practiced

Implement a Python function that maintains the top-k largest integers from a stream of numbers, using O(k) memory. Provide the function signature and briefly explain complexity. (You do not need to include unit tests, but explain how you'd test corner cases.)

Sample Answer

Use a min-heap of size k to keep the current top-k largest integers. For each incoming number from the stream:- If heap has fewer than k elements, push the number.- Else compare number to heap[0] (smallest in heap); if larger, replace the root with the new number (heapreplace) so heap always stores the k largest seen so far.This uses O(k) memory and O(log k) per update.

python

import heapq
from typing import Iterable, List

class TopK:
    def __init__(self, k: int):
        if k <= 0:
            raise ValueError("k must be positive")
        self.k = k
        self._heap: List[int] = []  # min-heap of current top-k

    def add(self, x: int) -> None:
        """Process one number from the stream."""
        if len(self._heap) < self.k:
            heapq.heappush(self._heap, x)
        elif x > self._heap[0]:
            heapq.heapreplace(self._heap, x)

    def add_many(self, items: Iterable[int]) -> None:
        for x in items:
            self.add(x)

    def topk(self) -> List[int]:
        """Return top-k in descending order."""
        return sorted(self._heap, reverse=True)

Complexity:- Time per element: O(log k) (push or heapreplace)- Space: O(k)

Edge / test cases to verify:- k larger than stream length (should return all elements)- k = 1 (max)- stream with duplicates- stream with negative numbers and zeros- strictly increasing / decreasing streams- invalid k (<=0) raises error

To test: feed deterministic streams and compare against sorted(stream)[-k:] results; test with randomized inputs and property-based checks.

HardTechnical

21 practiced

Design a heuristic or approximate method to detect near-duplicate documents at petabyte scale (e.g., for deduplication before ingest). Discuss algorithms such as MinHash/LSH, how to shard/index the sketches, mergeability, expected false-positive/negative trade-offs, and how you'd evaluate accuracy in production.

Sample Answer

Requirements & approach:- Goal: fast, memory-light near-duplicate detection across petabytes at ingest with tunable precision/recall.- Use MinHash to sketch each document’s shingle set (e.g., 5- or 9-gram shingles) and Locality-Sensitive Hashing (LSH) to bucket similar sketches. MinHash gives an unbiased Jaccard estimator; LSH makes lookup sublinear.

Sketch design:- Choose k MinHash signatures (e.g., 128–512) for accuracy; split into b bands of r rows (k = b·r) for LSH. Tuning: threshold T ≈ (1/b)^(1/r). For de-duplication threshold ~0.8, choose banding so p(similarity≥0.8) is high and p(similarity<0.8) low.- Compress sketches: store 32-bit or 64-bit hashes, optionally use XOR-folding or HyperLogLog-like compression for space.

Sharding & indexing at scale:- Implement LSH buckets as keys in a distributed key-value store (Cassandra/Dynamo/Bigtable) or inverted index in cloud object store with lookup via consistent hashing.- Shard by bucket id → partitioned by hash prefix to distribute load. Use streaming ingest (Kafka) → Spark/Flink to compute sketches and emit (bucketId, docId, sketch).- Maintain per-bucket candidate lists limited by time-window or capped size; evict old entries (TTL) for space.

Mergeability & incremental updates:- MinHash sketches are mergeable only in the sense of comparing — you can union sets by recomputing sketches or maintain per-doc sketches and use union estimation via inclusion-exclusion only approximately. For true merge of indexed buckets, store sketches per doc and update indexes; don't attempt to aggregate sketches across docs as a single representative unless you accept extra error (centroiding).

False positives/negatives trade-offs:- FP: LSH may place dissimilar docs in same bucket; reduce by increasing bands (b) (more selective) or raising similarity threshold and verifying candidate pairs with exact Jaccard on shingles for final decision.- FN: Too aggressive banding or tiny k causes misses; increase k and reduce rows per band (increase b) to lower FN at cost of more buckets/compute.- Use a two-stage pipeline: cheap LSH candidate generation (high recall), then exact/near-exact verification (Jaccard on shingles or normalized edit distance) to control FP.

Practical parameter guidance:- Start with k=256, b=32, r=8 (example) and simulate on representative dataset to pick operating point.- Store sketches and metadata in columnar store for re-checks; avoid recomputing heavy features repeatedly.

Evaluation in production:- Offline: build labeled sample corpus with ground truth duplicates (synthetic transformations: insertions, truncations, reordering, OCR noise) and measure recall@k, precision, ROC vs thresholds. Compute expected candidate size per doc.- Online: A/B test new parameters; sample candidate pairs and compute exact Jaccard to estimate live precision/recall. Track metrics: ingestion latency, per-doc candidate count, storage per doc, verification rate, FP rate (manual review + small-scale automated matching), FN approximated by monitoring unique-content growth and downstream duplicate complaints.- Monitoring & alerts: sudden spikes in candidate counts or drop in recall indicate drift (content type change), trigger re-tuning or re-shingling.

Operational concerns:- Batch vs streaming: use streaming for low-latency dedupe; fall back to batch reconciliation for heavy joins.- Cost: balance sketch size vs verification cost; push verification to async job if expensive.- Privacy & security: do not store raw content in index—store sketches/hashes only and salt hashes if needed.

This design provides a scalable, tunable near-duplicate pipeline: LSH for candidate generation, exact verification for precision, distributed sharding for scale, and production evaluation via offline labeled tests plus online sampling and monitoring.

MediumTechnical

25 practiced

When distinct counts are required for millions of users and memory per worker is limited, which approximate algorithm would you choose and why? Discuss HyperLogLog: memory vs accuracy trade-offs, mergeability across partitions, and how to test error bounds in production.

Sample Answer

I would choose HyperLogLog (HLL), specifically an HLL++ variant, because it gives excellent cardinality estimates with tiny, mergeable sketches — ideal when you have millions of users and tight memory per worker.

Why HLL (brief):- HLL estimates distinct counts using probabilistic register maxima from hashed values. It requires only O(m) memory per sketch, where m = 2^p (p is precision).- Standard error ≈ 1.04 / √m. So increasing p by 1 (doubling m) reduces error by ~√2.- Typical implementations use small registers (e.g., 6 bits) so per-sketch memory is m * bits_per_register (e.g., p=14 → m=16384 → ~12KB with 6-bit registers).

Memory vs accuracy trade-offs:- You pick p to hit your accuracy target given memory constraints. Example: p=14 gives ≈0.8% error; p=12 gives ≈1.8% error. If memory is very tight, use sparse representations (HLL++), which store small sketches compactly for low cardinalities and expand only when needed.- HLL favors constant, predictable memory and decreasing marginal gains for more memory (you must weigh the cost of doubling memory to reduce error by ~30%).

Mergeability across partitions:- HLL is naturally mergeable: to union two partitions, take per-register maxima of their register arrays; result is a valid sketch for the union. This property makes HLL ideal for distributed systems (Spark, Flink, MapReduce): compute local sketches per worker, then reduce/merge.- Ensure all workers use identical parameters (p, hash function, register width). Use a high-quality 64-bit hash (e.g., xxHash64, Murmur3_64) to minimize collisions.

Practical improvements:- Use HLL++ (sparse encoding + bias correction) for better accuracy in lower cardinalities.- Store sketches in compact binary form (e.g., serialized bytes) for network/shuffle efficiency.

How to test error bounds in production:1. Unit & synthetic tests: - Generate datasets with known cardinalities (random distinct IDs, controlled duplicates) across the relevant scale (small to very large). Compare HLL estimate vs ground truth and verify empirical error matches theoretical 1.04/√m ± tolerance. - Test skewed distributions and adversarial cases (correlated IDs, hash collisions).2. Shadow/full-count checks: - Periodically run exact counts on sampled partitions or time windows (e.g., hourly on a 1% reservoir sample or on a small subset of keys) and compare to HLL estimates. Track relative error distribution and alert if it exceeds thresholds.3. Canary and A/B: - Deploy HLL in shadow mode alongside existing exact pipeline for new datasets; monitor drift over time.4. Monitoring & alerting: - Track metrics: estimate, estimated standard error, number of merges, sketch size growth (for sparse→dense transitions), and rate of divergence vs sample ground truths. - Set alerts for sustained deviations beyond expected confidence intervals (e.g., >3σ).5. Determinism & reproducibility: - Fix hash seed and test deterministically to reproduce rare edge cases. Use different hashers in tests to ensure robustness.

Alternatives to consider (brief):- K-minimum values (KMV) gives unbiased estimates and supports set arithmetic but needs storing k values (higher memory for same error).- Bloom filters are for membership, not exact distinct counts.- Linear counting works well at low cardinalities but doesn't scale as efficiently as HLL for very large cardinalities.

Final note:Pick p based on acceptable error and memory per worker, use HLL++ with a strong 64-bit hash, leverage mergeability for distributed aggregation, and validate error empirically with synthetic datasets, reservoir/full-count comparisons, and continuous monitoring.

EasyTechnical

25 practiced

Describe a pragmatic testing strategy for verifying pipeline behaviour after a constraint change (e.g., memory-limited workers). Include unit tests, integration tests, load tests, and canary strategies for rolling the change to production.

Sample Answer

Situation: We need to change worker constraints (e.g., enforce 512MB memory per worker) and verify pipeline correctness & performance before and after rollout.

Pragmatic testing strategy:

1. Unit tests- Add tests for functions that would fail under low-memory (e.g., streaming buffer growth, serialization).- Mock memory limits using dependency injection or test harnesses; assert memory-aware code paths (spill-to-disk, chunking) are exercised.- Example: assert transform_batch() processes 10k rows in 10 chunks when chunk_size set.

2. Integration tests- Run pipeline stages end-to-end in CI with containerized workers limited to the new memory (using Docker --memory). Validate: - Functional correctness (row counts, schema, key metrics) - Fault handling (OOM kills lead to retries, checkpoint restoration)- Use sample production-like data (subsample) and assert SLAs (latency, throughput).

3. Load / Stress tests- Run scaled tests on an environment close to prod (staging) with memory-limited workers; ramp input volume to expected and 2–3x peak.- Measure: task failures, retry rate, end-to-end latency, GC pauses, spill I/O. Set thresholds (e.g., <1% task failure, <10% latency increase).- Use tools: k6 for HTTP ingestion, Spark/perf jobs, or custom drivers.

4. Canary deployment- Roll change to a small slice of production traffic (e.g., 5% of jobs or specific pipeline runs).- Dual-run strategy: run new-config jobs in parallel to baseline; compare outputs and metrics (row-level diffs, checksums, key aggregates).- Observability: dashboards for error rate, task memory, retries, throughput; alerts on regressions.- Progressive rollout: 5% → 25% → 100% with automated rollback on thresholds (e.g., data drift, error spikes).

Additional practices- Chaos tests: inject OOM in staging to validate recovery.- Feature flags/config toggles to switch memory limits without redeploy.- Post-rollout: run daily drift checks and monitor costs.

This approach catches logic bugs (unit), integration problems (integration tests), performance regressions (load), and limits blast radius during rollout (canary).

EasyTechnical

20 practiced

Explain the practical differences between batch and stream processing for a data pipeline. Given a batch job that processes hourly files, describe three scenarios where you would convert it to streaming and what concrete changes you'd make to the architecture and correctness handling.

Sample Answer

Batch vs stream — practical differences:- Batch processes data in discrete windows (e.g., hourly files). Simpler idempotency, easier recompute, higher end-to-end latency. Good for bulk ETL, analytics.- Stream processes events continuously with low latency. Requires event ordering, state management, windowing, and stronger fault-tolerance concerns. Good for real-time alerts, incremental updates.

Three scenarios to convert an hourly batch to streaming, and concrete changes:

1) Need sub-minute freshness (real-time dashboards / SLA)- Why: dashboards/users require near-real-time metrics.- Architecture changes: replace file-triggered Spark job with a streaming ingestion (Kafka/Cloud PubSub) → stream processor (Spark Structured Streaming / Flink / Beam) → OLAP store (ClickHouse/BigQuery streaming inserts).- Correctness handling: implement event-time windowing, watermarking to handle late events; use exactly-once sinks or idempotent writes; maintain state with checkpoints.

2) High volume spikes causing long batch runtimes / memory pressure- Why: hourly job can't finish within window during spikes.- Architecture changes: move to distributed stream processing with partitioned topics, autoscaling consumers, and incremental aggregation (per-key state).- Correctness handling: use checkpointing and durable offsets (Kafka consumer groups), ensure partitioning key matches aggregation key to avoid cross-partition joins, and use deduplication via unique IDs for at-least-once sources.

3) Need per-event alerting / transactional joins (fraud, anomaly detection)- Why: decisions must act on each event or join with slowly changing reference data.- Architecture changes: stream ingestion → enrich via lookup service or materialized view (stateful store like RocksDB/Flink state or Redis) → stream rule engine/ML scorer → alerting sink.- Correctness handling: manage consistency between stream and reference data with change data capture (CDC) to update materialized view; handle out-of-order events with event-time semantics and TTL for state; ensure exactly-once semantics for downstream actions (use transactional writes or compensating actions).

In all conversions, add monitoring (latency, watermark lag), backpressure handling, and replay capability (retain raw events in durable log for reprocessing).

Unlock Full Question Bank

Get access to hundreds of Handling Problem Variations and Constraints interview questions and detailed answers.

Join thousands of developers preparing for their dream job.