Coinbase·Data Scientist·Technical Phone Screen·Senior

Senior

Jun 2026

Summary

Coinbase data scientist interview with a SQL question that looks straightforward but has a real scalability gotcha buried in it. The kind of problem where you can get a working answer pretty easily but the follow-up about performance is where they actually care.

Questions Asked (1)

Given a table with id and val columns, return for each row the sum of all val entries where the value is less than or equal to that row's val. Ties count fully. How do you do this without a correlated subquery that blows up on large tables?

Algorithms & Data StructuresData ModelingTechnical Trade-offs

Author's notes

My first instinct was a self-join with a WHERE clause and I actually started writing it out before realizing that's exactly the O(n²) thing they were steering away from.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a window function to compute a running sum over the sorted values, which gives the cumulative sum for each row including ties. This avoids the O(n^2) correlated subquery and leverages efficient sorting and window aggregation in modern databases.

Pro tip: Mention that window functions are optimized in most databases and can handle large datasets efficiently, but be prepared to discuss fallback strategies like self-join with aggregation if window functions are not supported.

1. Clarify the requirement

Restate the problem: for each row, compute the sum of all val entries less than or equal to that row's val, with ties fully included. Confirm that the output should include the original id and val along with the cumulative sum.

2. Identify the efficient approach

Recognize that a correlated subquery would be O(n^2) and inefficient. Instead, use a window function: SUM(val) OVER (ORDER BY val ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) to get the running sum.

3. Handle ties correctly

Ensure that ties are fully included by using the default RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW, which includes all rows with the same val. Alternatively, use ROWS if you want to include only rows up to the current row in the sort order, but that would not fully include ties.

4. Write the SQL query

Construct the query: SELECT id, val, SUM(val) OVER (ORDER BY val) AS cumulative_sum FROM table; This uses the default window frame that includes all rows with val <= current val.

5. Discuss performance and alternatives

Explain that window functions are efficient (O(n log n) due to sorting) and scale well. If window functions are unavailable, suggest a self-join with GROUP BY as a fallback, but note its higher complexity.

Key Points to Mention

Window functions (e.g., SUM() OVER) are ideal for cumulative sums and avoid correlated subqueries.
The default window frame RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW includes all ties.
Performance: sorting is O(n log n), much better than O(n^2) for large tables.
Alternative: self-join with GROUP BY, but it's less efficient and more complex.
Database support: window functions are available in PostgreSQL, MySQL 8+, SQL Server, etc.
Edge cases: NULL values, duplicate vals, and ordering stability.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.