How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Coinbase.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coinbase during technical interviews.

Maximize profit with transaction fee | Coinbase Coding Question

Quick Overview

This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Maximize profit with transaction fee states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

Maximize profit with transaction fee

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an array of daily stock prices and a fixed transaction fee charged on each sell, compute the maximum profit achievable with any number of buy–sell transactions. Provide an O(n) time, O( 1) or O(n) space algorithm, prove correctness, and describe how you would handle edge cases such as empty input or strictly decreasing prices.

Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Maximize profit with transaction fee states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.

You are given an array `prices` where `prices[i]` is the price of a given stock on day `i`, and an integer `fee` representing a fixed transaction fee charged on every sell. Find the maximum profit you can achieve with any number of buy-sell transactions. You may complete as many transactions as you like, but you must sell the stock before you buy again (you can hold at most one share at a time), and you pay `fee` once per completed transaction (charged on the sell). Return the maximum achievable profit. If no profit is possible (e.g. empty input or strictly decreasing prices), return 0. Use an O(n) time, O(1) space dynamic-programming approach. Track two running states as you sweep left to right: `cash` = the best profit while holding no share, and `hold` = the best profit while holding one share. Each day, you may sell (`cash = max(cash, hold + price - fee)`) or buy (`hold = max(hold, cash - price)`). The answer is the final `cash`, since ending without a held share is always at least as good as ending while holding one.

Constraints

0 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4 (when present)
0 <= fee < 5 * 10^4
You may hold at most one share at a time and must sell before buying again.

Examples

Input: ([1, 3, 2, 8, 4, 9], 2)

Expected Output: 8

Explanation: Buy at 1, sell at 8 (profit 8-1-2=5), buy at 4, sell at 9 (profit 9-4-2=3). Total = 8.

Input: ([1, 3, 7, 5, 10, 3], 3)

Expected Output: 6

Explanation: Buy at 1, sell at 7 (7-1-3=3), buy at 5, sell at 10 (10-5-3=2)... the optimal single transaction buy at 1, sell at 10 gives 10-1-3=6, which beats splitting. Total = 6.

Input: ([], 5)

Expected Output: 0

Explanation: Empty input: no transactions possible, profit is 0.

Input: ([5], 2)

Expected Output: 0

Explanation: Single day: you can buy but cannot sell, so no profit; return 0.

Input: ([9, 8, 7, 6, 5, 4], 1)

Expected Output: 0

Explanation: Strictly decreasing prices: any sell loses money after the fee, so the best is to do nothing. Profit = 0.

Input: ([1, 4, 6, 2, 8, 3, 10, 14], 3)

Expected Output: 13

Explanation: Buy 1 sell 6 (6-1-3=2), buy 2 sell 8 (8-2-3=3), buy 3 sell 14 (14-3-3=8). Total = 2+3+8 = 13.

Input: ([3, 3, 3, 3], 0)

Expected Output: 0

Explanation: Flat prices with zero fee: no price difference to exploit, profit = 0.

Hints

Track two states each day: the best profit if you currently hold no share (cash), and the best profit if you currently hold one share (hold).
Transition: cash = max(cash, hold + price - fee) models selling today (pay the fee on sell); hold = max(hold, cash - price) models buying today.
Initialize cash = 0 and hold = -prices[0]. The answer is the final cash, because finishing without a held share never loses you anything.
For empty input or strictly decreasing prices, no transaction is profitable, so the answer stays 0.

Quick Overview