Problem Solving and Analytical Thinking Questions

Evaluates a candidate's systematic and logical approach to unfamiliar, ambiguous, or complex problems across technical, product, business, security, and operational contexts. Candidates should be able to clarify objectives and constraints, ask effective clarifying questions, decompose problems into smaller components, identify root causes, form and test hypotheses, and enumerate and compare multiple solution options. Interviewers look for clear reasoning about trade offs and edge cases, avoidance of premature conclusions, use of repeatable frameworks or methodologies, prioritization of investigations, design of safe experiments and measurement of outcomes, iteration based on feedback, validation of fixes, documentation of results, and conversion of lessons learned into process improvements. Responses should clearly communicate the thought process, justify choices, surface assumptions and failure modes, and demonstrate learning from prior problem solving experiences.

MediumTechnical

31 practiced

Implement the Misra-Gries algorithm (frequent elements) in Python to find all items that occur more than N/k times in a stream. Provide code, explain why it maintains O(k) memory, and state what verification is needed if you only have a single pass over the stream.

Sample Answer

To find all items appearing > N/k times in a stream, use the Misra–Gries algorithm: maintain at most k-1 candidate items with counts; on each element, increment if it's a candidate, add it with count=1 if there's space, otherwise decrement all counts by 1 and remove zeros. After one pass you have candidates; a second pass (or stored partial counters) is required to verify true frequencies.

python

def misra_gries(stream, k):
    """
    Return candidate items that may occur > N/k times.
    stream: iterable of items (single pass allowed)
    k: integer > 1
    """
    if k <= 1:
        raise ValueError("k must be > 1")
    counters = {}  # item -> count, size <= k-1

    # First pass: build candidates
    for x in stream:
        if x in counters:
            counters[x] += 1
        elif len(counters) < k - 1:
            counters[x] = 1
        else:
            # decrement all counts
            to_delete = []
            for key in list(counters):
                counters[key] -= 1
                if counters[key] == 0:
                    del counters[key]
    return counters.keys()  # candidates; need verification

# Example usage:
# candidates = misra_gries(my_stream, k=10)
# Then verify by counting occurrences of each candidate in a second pass.

Why O(k) memory:- counters holds at most k-1 keys, so space is O(k). Each update touches only current candidates or decrements them; no per-item storage.

Verification needed with single pass:- The algorithm only yields candidates — to confirm which actually exceed N/k you must know true frequencies. With only one sequential pass and no ability to rewind, you must either (a) maintain exact counters for candidates in parallel during the pass (i.e., keep an additional hash of true counts for current candidates), or (b) materialize the stream (or sample) to re-scan. Without verification you can only guarantee the output is a superset of true heavy hitters.

MediumTechnical

41 practiced

A daily ETL that usually completes in 30 minutes now takes 3 hours. Outline a structured approach to root-cause analysis: what metrics and logs you compare between runs, what targeted experiments you'd run (sampleed runs, warm/cold cache), and how you'd isolate whether the cause is data volume, skew, external dependency, or config changes.

Sample Answer

Step 1 — Clarify scope & baseline- Confirm the exact job, schedule, and recent changes (deployments, config, libraries, cluster size).- Capture a baseline: a “healthy” run (30m) metrics and a failing run (3h).

Step 2 — Collect and compare metrics/logs- Pipeline-level: total runtime, stage timings, per-task durations, shuffle read/write bytes, GC time.- Spark metrics: executor count, cores, memory usage, spill to disk, task failure/retries, scheduler delay.- I/O & external: source/target read throughput (MB/s), latency to external services (DB, S3), network errors.- Data metrics: input row counts, file counts, avg/95/99 row sizes, partition counts.- System: CPU, disk IOPS, network, io wait on worker nodes.- Logs: driver/executor logs, application master, and any error/warning trends.

Step 3 — Targeted experiments (controlled)- Replay healthy input on current cluster (isolates infra/config): does performance degrade? If yes, infra/config issue.- Run current (large) input on a known-good cluster or snapshot of previous config: does it still take 3h? If yes, data-driven.- Run sampled runs: 1%, 10%, 50% of input and measure scaling (linear vs superlinear indicates skew or shuffle explosion).- Warm vs cold cache: pre-warm caches (e.g., broadcast variables, HDFS/S3 caching) vs cold run to detect cache effects.- Toggle parallelism/executor sizing: increase executors/cores/memory to see if bottleneck alleviates (indicates resource insufficiency).- Isolate stages: run individual Spark stages or SQL fragments to find the slow stage.

Step 4 — Diagnosis matrix (how to isolate causes)- Data volume increase: input row/file counts much higher; sampled runs scale linearly; per-task time proportional to data.- Skew: small subset tasks are orders-of-magnitude slower; task duration distribution has heavy tail; increases in shuffle spill/GC for some partitions.- External dependency: source read throughput drop, increased latency in DB/S3 metrics, errors/retries correlate with job stalls.- Config/regression: recent code/config changes correlated with start time; replay old code on new data — if fast, config/code change is culprit.

Step 5 — Remediation & verification- If skew: add salting, repartition by better key, increase parallelism, reduce skewed partitions.- If volume: add incremental processing, partition pruning, sampling, or scale cluster.- If external: work with service owners, add retries/backoffs, cache external reads, parallelize I/O.- If config/regression: revert or patch, add tests, CI performance benchmark.

Step 6 — Preventive measures- Add regression alerts (runtime, stage durations, task skew percent).- Store per-run metrics and histograms; automated canary runs after deploys.- Maintain playbook with quick experiments above.

Expected outcome: pinpoint slow stage or resource, run targeted fix, validate by comparing metrics (stage time, task distribution, throughput) to baseline.

MediumTechnical

35 practiced

Compare HyperLogLog and Bloom filters from a data platform perspective. For each, describe primary use-cases (distinct counting vs membership test), memory/accuracy trade-offs, mergeability, and practical validation steps you'd run in production to ensure they perform as expected.

Sample Answer

HyperLogLog vs Bloom filter — concise, practical comparison for a data platform engineer.

Primary use-cases- HyperLogLog (HLL): approximate distinct counting (cardinality). Good for unique user counts, daily active users, unique IPs across streams.- Bloom filter: membership test (set membership with false positives). Good for cache-aside deduplication, filtering known-bad items, quick existence checks before expensive lookups.

Memory / accuracy trade-offs- HLL: accuracy controlled by precision p (registers m = 2^p). Standard error ≈ 1.04 / sqrt(m). Example: p=14 (m=16384) → ~0.8% error using ~12–16 KB. Memory grows exponentially with p but stays tiny for large cardinalities.- Bloom: accuracy via number of bits (m) and hash functions (k). False positive rate ≈ (1 - e^{-kn/m})^k. For n items, choose m ≈ -n * ln(fp) / (ln2)^2. Memory scales linearly with expected n. No false negatives; FPR trade-off vs memory.

Mergeability- HLL: mergeable by taking register-wise max; ideal for distributed aggregation (map-reduce, streaming windows).- Bloom: can merge (bitwise OR) only if same m and hash functions; OR preserves membership semantics but increases false positive rate relative to separate sets — suitable if parameters chosen with headroom.

Practical validation in production- Unit/Integration tests: - HLL: compare HLL estimate vs exact count on sampled datasets across ranges (small to very large). Verify error within theoretical bounds and stable after merges/serialized-deserialized. - Bloom: insert known set, test zero false negatives, measure empirical false positive rate against a large probe set not inserted; compare against expected FPR.- Load & stress tests: - Simulate concurrent merges, serialization, and high-throughput updates; ensure throughput and latency meet SLAs.- Monitoring & alerting: - Track metrics: HLL_estimate / exact_sample_ratio, Bloom_empirical_FPR, memory usage, serialization errors. Alert if deviation exceeds threshold (e.g., error > 2× theoretical).- Backfills / A/B checks: - Periodically compute exact counts or run exact membership checks on a randomized subset and compare; use as ground truth to recalibrate parameters.- Versioning & schema: - Enforce parameter/version metadata with stored sketches/filters; validate compatibility before OR/merge.- Capacity planning: - For Bloom, provision extra bits for growth; for HLL, pick p to cover expected cardinality while keeping acceptable error.

Summary: use HLL for scalable distributed cardinality with cheap merges and predictable relative error; use Bloom for space-efficient membership checks where false positives are tolerable. Validate with deterministic unit tests, randomized ground-truth sampling, stress tests, and continuous monitoring/alerts.

EasyTechnical

40 practiced

Compare a data warehouse and a data lake. For an organization storing terabytes of raw semi-structured logs that also needs BI reporting, when would you choose a warehouse, a lakehouse, or a hybrid approach? Explain trade-offs in cost, performance, governance, and time-to-insight.

Sample Answer

Definition and core difference:- Data warehouse: structured, schema-on-write, optimized for BI/OLAP (e.g., Redshift, BigQuery, Snowflake).- Data lake: raw/unstructured or semi-structured storage (object store/HDFS), schema-on-read, cheap at scale.- Lakehouse: combines lake cost and flexibility with warehouse-style performance & governance (Delta, Iceberg, Hudi + query engines).

When to choose which (given terabytes of semi-structured logs + BI needs):- Warehouse: choose when BI is primary, queries are predictable, and you can afford ETL to curate data into tables. Pros: excellent performance, mature SQL tooling, strong governance. Cons: higher storage & compute cost, slower to onboard raw logs (ETL time).- Lakehouse: choose when you need both raw log retention for data science and performant BI without duplicating storage. Pros: lower storage cost for raw logs, ACID/partitioning for analytics, faster time-to-insight for ad-hoc queries. Cons: depends on maturity of engine; may require more engineering to tune.- Hybrid: choose when existing BI ecosystem demands a warehouse but you also need full-fidelity raw logs. Keep raw logs in lake, curated marts in warehouse (or use query federation). Pros: best-of-both, simpler governance boundaries. Cons: duplicated storage/processing costs and pipeline maintenance.

Trade-offs:- Cost: lake cheapest for storage; warehouse more expensive for storage+compute; lakehouse middle (cheap storage, compute costs for optimizations).- Performance: warehouse highest for concurrent BI; lakehouse close if using optimized formats/indexes; raw lake slow without optimizations.- Governance: warehouse has mature role-based access, auditing; lakehouse adds transactionality and easier lineage; raw lake needs additional tooling (catalogs, IAM).- Time-to-insight: lake fastest to ingest raw logs (schema-on-read) for exploration; warehouse needs ETL but gives consistent dashboards. Lakehouse/hybrid can minimize latency by enabling queryable raw + curated views.

Recommendation (practical): Start with lake + lakehouse capabilities (Delta/Iceberg) to retain raw logs and support exploration; implement nightly/streaming ETL to populate curated warehouse marts or materialized views for high-concurrency BI. This balances cost, governance, and performance while keeping time-to-insight low.

MediumSystem Design

35 practiced

Design a CDC ingestion pipeline from Postgres to a data lake that guarantees at-least-once delivery, supports replay/backfill, and handles schema changes. Outline components (capture, transport, transform, storage), how you record progress/offsets, ordering guarantees, and monitoring you'd implement.

Sample Answer

Requirements & constraints:- At-least-once delivery, replay/backfill, handle Postgres schema evolution, preserve per-row ordering where needed, land into cloud data lake (e.g., S3) for downstream ETL.

High-level architecture (components):1. Capture: Debezium (Postgres logical decoding) runs connectors per DB/replica to emit change events (INSERT/UPDATE/DELETE + tx metadata + LSN).2. Transport: Apache Kafka — one topic per database.table (or per schema) with partitioning by primary key hash to keep per-row ordering. Use compacted topics for keyed state and long retention for replay.3. Transform: Kafka Streams / ksqlDB or Spark Structured Streaming consumers to apply lightweight enrichment, normalize schemas, and produce parquet/avro batches. Use schema registry (Confluent or AWS Glue) with Avro/Protobuf for evolution.4. Storage: Write to data lake using a transactional table format (Delta Lake / Apache Hudi / Iceberg) to support idempotent upserts and efficient time-travel for backfill/replay.

Progress / offsets & replay:- Kafka stores offsets; consumers commit after successful sink writes. For stronger tracking, maintain an external checkpoint store (e.g., Kafka consumer group + immutable checkpoint records in a metastore like DynamoDB / PostgreSQL / Hive metastore) containing last processed LSN per table/partition and sink file manifest. For replay/backfill, you can: - Rewind Kafka consumer offsets to earlier offsets or - Use retained Debezium snapshots + produce to Kafka, or - Re-run a historical snapshot job that reads Postgres snapshot at a point-in-time and replays into Kafka.- Include source LSN/tx-id and event sequence in each message for deterministic dedup/ordering.

Ordering guarantees:- Guarantee ordering per primary key by partitioning Kafka by primary key. Cross-key ordering is not guaranteed. Within a transaction, Debezium preserves tx ordering; include tx id and event index to enforce deterministic application in sinks if needed.

At-least-once & Idempotence:- Kafka + consumer commit after sink success yields at-least-once. To avoid duplicates in lake, write to table format supporting idempotent upserts (merge by primary key + LSN) or use file-commit atomicity (e.g., Delta/Hudi). Store LSN in target rows and apply "apply only if LSN > existing_LSN" logic.

Schema evolution:- Use schema registry (Avro/Protobuf) to version schemas. Emit schema id with each message. Transformation layer handles field additions/removals, and sink supports nullable fields. For incompatible breaking changes, use migration process: evolve consumer logic, run backfill to fill new columns, support parallel writes (new table) and cutover.

Monitoring & observability:- Metrics: connector health, Kafka lag per topic/partition, consumer commit latency, sink write success/failure rates, throughput, and end-to-end latency (source LSN -> lake commit).- Alerts: connector downtime, consumer lag > threshold, schema registry changes, sink error spikes.- Data quality checks: row count reconciliation (source vs landed for time windows), checksum/hash lineage per batch, DLQ for malformed events (retain original message + error metadata).- Tracing & logs: include message keys, LSN, tx-id in logs; distributed tracing for pipeline stages.- Playbooks: automated offset rewind, DLQ inspection tools, and schema-change runbooks.

Trade-offs:- Using Kafka + Debezium simplifies capture/replay but costs more infra. Delta/Hudi add complexity but give strong idempotence and time-travel for backfills. Partitioning by PK gives per-row ordering but limits fan-out for hot keys — mitigate with salt or adaptive partitioning.

This design provides at-least-once guarantees, supports replay/backfill via Kafka rewind or snapshot replays, handles schema evolution with schema registry and transactional lake formats, and offers operational observability for safe production use.

Unlock Full Question Bank

Get access to hundreds of Problem Solving and Analytical Thinking interview questions and detailed answers.

Join thousands of developers preparing for their dream job.