Data-Centric Algorithmic Problem Solving Questions

Foundational algorithm design and data-structure concepts with an emphasis on data-centric problem solving. Covers algorithmic paradigms (e.g., greedy, dynamic programming, divide-and-conquer, graph algorithms), data structures, complexity analysis, and practical approaches to solving computational problems using data.

MediumTechnical

38 practiced

An operational dashboard queries a fact table with 500M rows and is taking multiple seconds to render. Describe a step-by-step approach to profile, diagnose, and optimize the query and dashboard. Discuss use of EXPLAIN, index design, schema changes, materialized views, pre-aggregation, caching, and monitoring.

Sample Answer

Start by clarifying requirements: acceptable latency, required freshness, typical filters (time ranges, customer, product), concurrency and dashboard tool (Tableau/Looker).

1) Profile the query- Capture the slow SQL produced by the BI tool (use query logging).- Run EXPLAIN/EXPLAIN ANALYZE on the SQL to see scan types, join order, estimated vs actual rows, and hotspots (sequential scans, large sorts, nested loop on big joins).

2) Diagnose root causes- Identify full table scans, expensive joins, big sorts, or network transfer (SELECT * in dashboards).- Check cardinalities and stale statistics causing bad plans.- Monitor system metrics (CPU, I/O, tempdb/sort spill, connection pool) during query.

3) Quick fixes (low-risk)- Add or update statistics and run ANALYZE.- Remove unnecessary columns and reduce resultset from DB (let BI tool do less post-processing).- Ensure predicates use indexed columns (avoid functions on columns).

4) Index design- Create composite indexes matching WHERE + JOIN + ORDER BY patterns; consider covering indexes to avoid lookups.- Test with CREATE INDEX CONCURRENTLY / online if production.- Beware of write amplification on high-insert fact tables; prioritize read-friendly indexes sparingly.

5) Schema changes & partitioning- Partition the fact table by time (day/month) to prune scans for recent ranges.- Consider clustering by date or frequent filter to keep hot data contiguous.

6) Materialized views & pre-aggregation- Build materialized views for expensive aggregations (e.g., daily rollups by product/customer) refreshed on a schedule or incrementally.- Implement a pre-aggregation layer: store hourly/daily summaries and let dashboard query those for common time ranges.- Use incremental refresh where possible to reduce rebuild cost.

7) Caching- Enable BI-tool caching, result-set cache, or a query cache (Redis) for identical queries/dashboards.- Use CDN or dashboard snapshots for executive pages that tolerate stale data.- Cache at different layers: DB query cache, BI tool extract (Tableau extract/Power BI dataset), or application layer.

8) Long-term & monitoring- Add query-level monitoring and alerting (slow query log, pg_stat_statements).- Track dashboard-level metrics (render time, cache hit rate, user patterns).- Automate refresh schedules, and maintain a lifecycle for materialized views and indexes.

Trade-offs: indexes and materialized views speed reads but increase storage and maintenance cost; partitioning improves pruneability but adds complexity. Prioritize based on SLA: if sub-second needed, rely on pre-aggregations + cache; if near-real-time required, optimize indexes, partitioning, and incremental materialized views.

Example outcome: After adding time partitioning, creating a covering index for the common WHERE+GROUP BY, and switching dashboards to query a daily pre-aggregated table refreshed hourly, render time dropped from 6s to <500ms and DB CPU utilization fell 30%.

MediumTechnical

34 practiced

List and explain five common SQL anti-patterns that cause slow BI queries (e.g., SELECT *, applying functions to indexed columns, unbounded CROSS JOINs). For each anti-pattern propose a practical fix and how you would measure the improvement in performance.

Sample Answer

1) SELECT * - Why slow: pulls unnecessary columns, increases I/O and network transfer for BI extracts and visualizations. Prevents the optimizer from using covering indexes. - Fix: Select only needed columns; create materialized views or thin extracts for frequent dashboards. Use column pruning in ETL. - Measure: Compare bytes read, execution time, and dashboard load time before/after; monitor query_plan I/O and looker/tableau extract size.

2) Applying functions to indexed columns (e.g., WHERE UPPER(email)=...) - Why slow: prevents index seeks; forces full table/partition scans. - Fix: Use computed/indexed columns or store normalized values (lowercased) and query those, or rewrite predicate (WHERE email = LOWER(?)). - Measure: Check index usage in EXPLAIN, reduction in scanned rows, and latency percentiles.

3) Unbounded CROSS JOINs or non-selective joins - Why slow: Cartesian products blow up row counts; joins without proper keys cause massive shuffles in distributed engines. - Fix: Ensure correct join keys, add join predicates, pre-aggregate or filter inputs, use broadcast joins when one side is small. - Measure: Row count deltas in plan, memory/spill metrics, and query runtime.

4) NOT IN / OR predicates that block index use - Why slow: Often trigger full scans and prevent sargability. - Fix: Replace with NOT EXISTS, use UNION ALL of indexed predicates, or transform logic (anti-join). Add proper indexes/statistics. - Measure: EXPLAIN changes, scanned rows, and latency improvements.

5) Selective use of DISTINCT/ORDER BY LIMIT without indexes - Why slow: DISTINCT and ORDER BY force sorting/aggregation across large datasets if no covering index exists. LIMIT without index still scans. - Fix: Create appropriate indexes to support ORDER BY; push down LIMIT via subqueries with indexed predicates; pre-aggregate in ETL. - Measure: Sort/spill metrics in query plan, CPU usage, and response time.

General measurement approach: capture baseline EXPLAIN plans, scanned rows, I/O bytes, CPU time, and dashboard load times; run A/B tests on cached vs uncached results and report median/95th percentile improvements.

EasyTechnical

45 practiced

Given table transactions(transaction_id PK, user_id INT, amount DECIMAL, occurred_at TIMESTAMP), write an ANSI SQL query to compute a running total of amount per user ordered by occurred_at. Include output columns: user_id, occurred_at, amount, running_total. Explain any assumptions about duplicate timestamps.

Sample Answer

Approach: use a window SUM partitioned by user_id and ordered by occurred_at. To make ordering deterministic when multiple transactions share the same timestamp, add a tiebreaker (transaction_id). Use RANGE vs ROWS: ROWS UNBOUNDED PRECEDING with ORDER BY (occurred_at, transaction_id) ensures each row’s running_total includes all prior rows including ties resolved by transaction_id.

SQL (ANSI):

sql

SELECT
  user_id,
  occurred_at,
  amount,
  SUM(amount) OVER (
    PARTITION BY user_id
    ORDER BY occurred_at, transaction_id
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
  ) AS running_total
FROM transactions
ORDER BY user_id, occurred_at, transaction_id;

Assumptions:- transaction_id is unique and monotonically increasing (or at least unique) so it can serve as a deterministic tiebreaker.- If you prefer to treat all rows with the same occurred_at as simultaneous (i.e., include all same-timestamp rows in the same running_total value), use RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW with only ORDER BY occurred_at; behavior depends on SQL dialect support for RANGE with non-numeric ORDER BY.

This returns per-user cumulative amounts over time suitable for BI dashboards and time-series visuals.

MediumTechnical

36 practiced

Write Python code to merge two sorted iterators (generators yielding numbers in ascending order) into a single sorted iterator without loading all elements into memory. The solution should handle infinite/very large streams and perform lazy consumption.

Sample Answer

To merge two sorted iterators lazily, keep a single-item buffer (the "current" value) for each iterator. Repeatedly compare the buffered values, yield the smaller, and advance that iterator to refill its buffer. This uses O(1) extra memory and works with infinite streams because we only consume as needed.

python

def merge_sorted_iters(a_iter, b_iter):
    """Merge two ascending sorted iterators lazily into a single ascending iterator."""
    sentinel = object()

    def advance(it):
        try:
            return next(it)
        except StopIteration:
            return sentinel

    a = iter(a_iter)
    b = iter(b_iter)
    a_val = advance(a)
    b_val = advance(b)

    while a_val is not sentinel or b_val is not sentinel:
        if a_val is sentinel:
            yield b_val
            b_val = advance(b)
        elif b_val is sentinel:
            yield a_val
            a_val = advance(a)
        else:
            if a_val <= b_val:
                yield a_val
                a_val = advance(a)
            else:
                yield b_val
                b_val = advance(b)

Key points:- Lazy: only one element per source buffered.- Memory: O(1) extra.- Time: each yielded element does O(1) work.Edge cases:- Equal values: both are emitted preserving multiplicity.- One or both iterators empty or infinite: handled correctly.

Alternative: use heapq.merge(a_iter, b_iter) which also merges lazily and supports multiple inputs.

HardTechnical

36 practiced

You must compute pairwise correlations for 100k features (100k x 100k matrix). This is infeasible naively. Propose algorithmic strategies to approximate or reduce dimensionality: random projections, feature hashing, PCA, block-wise streaming covariance; discuss memory/time trade-offs and how to prioritize which feature pairs to compute exactly.

Sample Answer

Goal: compute useful pairwise correlations among 100k features without materializing a 100k×100k matrix (10^10 entries). Tradeoffs are between accuracy, compute, and memory; prioritize business-relevant pairs.

Strategies (what, why, trade-offs):- Random projections (Johnson-Lindenstrauss): embed features into k ≈ O(log N / ε^2) dims, compute correlations in reduced space. Good for global structure and nearest-neighbor style queries. Memory: O(100k·k). Time: O(n_samples·100k·k). Trade-off: approximate inner products; controllable error vs k.- Feature hashing: map sparse categorical features into m buckets, then compute correlations on buckets. Very cheap and streaming-friendly. Collisions bias correlations toward zero and introduce false positives; choose m based on collision tolerance.- PCA / SVD on feature covariance (or on samples × features): compute top r components (r≪100k) via incremental or randomized SVD. Captures directions of largest variance so you can approximate correlations for features that load on same components. Memory: store 100k×r matrix. Time: O(n_samples·100k·r). Trade-off: misses low-variance but business-important relationships.- Block-wise streaming covariance: stream data in chunks, compute block covariances for subsets of features and flush to disk; combine via online formulas. Allows exact pairwise for blocks but still O(100k^2) if full—so use blocking to focus compute budget.- Hybrid: use cheap approximate method (RP or hashing) to find candidate highly-correlated pairs, then compute exact correlation only for candidates using block-wise reads.

How to prioritize exact computations:- Business rules: only pairs that affect KPIs, dashboards, or known feature groups (product segments, metrics).- Variance & loadings: focus on features with high variance or high loading on top PCA components.- Approximate screening: run LSH/approximate nearest neighbors on projected space to produce top-k candidate pairs per feature.- Sparsity: for sparse features, compute correlations only among features with overlapping non-zero support.

Practical notes for BI:- Use randomized SVD libraries (scikit-learn, Facebook’s fbpca) or Spark ML for distributed PCA.- Persist reduced representations and candidate lists; compute exact correlations lazily when a dashboard or alert needs them.- Monitor approximation error by validating a sample of exact pairs.

Example config: choose k=500 for JL → memory ~100k×500 ≈ 50M floats (~200MB), find top-100 candidates per feature, then compute exact correlations for those ≈10M pairs (feasible with block-wise reads).

Unlock Full Question Bank

Get access to hundreds of Data-Centric Algorithmic Problem Solving interview questions and detailed answers.

Join thousands of developers preparing for their dream job.