Coinbase·Software Engineer·Technical Phone Screen·Senior

SeniorPrefer not to say

Apr 2026Remote

Summary

Coinbase software engineer interview with two parts to a transaction selection problem. The dependency extension in part two is where things got interesting and I wasn't fully prepared for it.

Questions Asked (2)

You have N transactions each with an id, size, and fee. Build a block capped at total size 100 that maximizes total fee. No heap allowed. Walk through your approach.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The no-heap constraint threw me for a second because my first instinct was literally a max-heap.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Clarify that this is the 0/1 knapsack problem where size is weight and fee is value, then implement a dynamic programming solution using a 2D table (or 1D array) to avoid heaps. Walk through the DP recurrence, initialization, and how to reconstruct the selected transactions.

Pro tip: Mention that while DP is optimal for small capacity (100), for large capacities a greedy approach by fee-to-size ratio is a common heuristic but not always optimal—showing you understand trade-offs.

1. Clarify the problem

Confirm that each transaction can be included at most once (0/1 knapsack) and that total size must not exceed 100. Ask if fees and sizes are integers and if negative values are possible.

2. Define DP state and recurrence

Let dp[i][s] be the maximum fee using first i transactions with total size exactly s (or at most s). Recurrence: dp[i][s] = max(dp[i-1][s], dp[i-1][s - size_i] + fee_i) if size_i <= s.

3. Initialize and fill table

Initialize dp[0][s] = 0 for all s (or -inf if exact size required). Iterate i from 1 to N, s from 0 to 100, filling the table. Use a 1D array for space optimization if needed.

4. Reconstruct solution

Backtrack from dp[N][100] to determine which transactions were selected by checking if the value came from including the current item.

5. Analyze complexity and trade-offs

Time O(N * 100), space O(N * 100) or O(100) with 1D array. Discuss that this is pseudo-polynomial and works well for small capacity, but for large capacity other approaches (e.g., branch and bound) might be needed.

Key Points to Mention

0/1 knapsack problem mapping: size as weight, fee as value, capacity 100.
Dynamic programming recurrence and state definition.
Space optimization using 1D array (iterating s downwards).
Reconstruction of selected transactions via backtracking.
Time and space complexity: O(N * capacity).
Alternative greedy approach by fee/size ratio and its limitations.

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

Now transactions can have parent dependencies where including a child requires including all its ancestors. How do you modify your selection strategy to respect this while still maximizing total fee?

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

This is where I struggled.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Recognize that the parent-child dependency forms a forest (or DAG) where selecting a child requires selecting all ancestors, so the problem becomes selecting a set of nodes closed under ancestors to maximize total fee. Propose a dynamic programming approach on the tree structure, computing for each node the optimal selection of its subtree given whether the node is selected or not, then combine children choices. Discuss trade-offs between exact DP and greedy heuristics for large graphs, and mention how to handle cycles or multiple parents if the dependency is a DAG.

Pro tip: Emphasize that this is essentially a tree knapsack or maximum weight closure problem, and mention that for large-scale systems you might use a greedy approximation with priority queues while maintaining ancestor closure, but always validate with a DP on smaller instances.

1. Model the dependency as a forest/DAG

Explain that each transaction is a node, and parent dependencies form directed edges from child to parent. If each transaction has at most one parent, it's a forest; if multiple, it's a DAG. The goal is to select a subset of nodes closed under ancestors (if a node is selected, all its ancestors must be selected) to maximize sum of fees.

2. Define DP state and recurrence

For a tree, define DP[v][0] = max fee in subtree of v when v is not selected (then no descendant can be selected because selecting a descendant requires v), so DP[v][0] = 0. DP[v][1] = fee(v) + sum over children c of max(DP[c][0], DP[c][1]). For a DAG, use topological order and propagate constraints, or transform to a tree by duplicating nodes if needed.

3. Handle multiple parents and cycles

If a node has multiple parents, it can only be selected if all parents are selected. This is a maximum weight closure problem, solvable by min-cut. Mention that cycles (if any) must be contracted or handled by strongly connected components, as they force all-or-nothing selection.

4. Discuss complexity and scalability

Tree DP runs in O(n) time and space. For DAGs, min-cut on a graph with n nodes and m edges runs in polynomial time but may be too slow for very large n. Propose greedy heuristics: sort by fee, try to add transactions if all ancestors are already selected, using a priority queue and union-find to track availability.

5. Compare trade-offs and choose strategy

For exact optimality on moderate sizes, use DP or min-cut. For real-time systems with millions of transactions, use a greedy approximation that respects dependencies, possibly with a threshold or budget. Mention that the greedy may not be optimal but is fast and often close.

Key Points to Mention

The problem is equivalent to maximum weight closure in a directed graph, solvable by min-cut.
For tree-structured dependencies, dynamic programming with two states per node gives an O(n) optimal solution.
Greedy algorithms (e.g., sort by fee, add if ancestors selected) are fast but not always optimal; they can be improved with local search.
Handling multiple parents requires ensuring all parents are selected, which complicates greedy but is naturally handled by closure formulation.
Cycles in dependencies force all nodes in the cycle to be selected together; contract strongly connected components first.
Scalability considerations: exact methods may be too slow for large n, so approximations or sampling may be needed in production.

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