Coinbase·Software Engineer·Technical Phone Screen·Senior

Senior

Jul 2026

Summary

Coinbase SWE interview with a dynamic programming problem that looked straightforward but had enough moving parts to keep you honest. The transaction fee twist changes the whole approach and they wanted proof of correctness too, not just working code.

Questions Asked (1)

Given an array of daily stock prices and a fixed fee applied on each sale, find the maximum profit you can make with unlimited buy-sell transactions. They want an O(n) solution, a correctness argument, and handling for edge cases like empty input or prices that only go down.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The fee-per-sell detail is what makes this not just a standard stock problem.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a dynamic programming approach with two states: cash (max profit with no stock) and hold (max profit with stock). Iterate through prices once, updating cash and hold based on buy/sell decisions with the fee applied on sale, achieving O(n) time and O(1) space.

Pro tip: Explicitly state the DP recurrence and walk through a small example to demonstrate correctness, and mention that the fee is only applied when selling to avoid double-counting.

1. Clarify problem and constraints

Confirm that transactions are unlimited, fee is per sale, and you can hold at most one share at a time. Ask about input size and edge cases.

2. Define DP states and recurrence

Let cash be max profit with no stock, hold be max profit with stock. Initialize cash=0, hold=-prices[0]. For each price, update cash = max(cash, hold + price - fee) and hold = max(hold, cash - price).

3. Walk through an example

Trace the algorithm on a small array (e.g., [1,3,2,8,4,9] with fee=2) to show how states evolve and final profit is computed.

4. Argue correctness and complexity

Explain that the recurrence considers all valid transactions and that the final cash is the maximum profit. State O(n) time and O(1) space.

5. Handle edge cases

Discuss empty input (return 0), single price (return 0), and monotonically decreasing prices (return 0). Also mention if fee is very large, no transactions occur.

Key Points to Mention

Dynamic programming with two states: cash and hold
Fee applied only on sale, not on buy
O(n) time and O(1) space complexity
Correctness via induction or exchange argument
Edge cases: empty array, single element, decreasing prices
Unlimited transactions but at most one share held at a time

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