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 fees | Coinbase Coding Question

Maximize profit with transaction fees

Company: Coinbase

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

You are given an array prices where prices[i] is the price of a stock on day i and an integer fee representing the commission charged when you sell. You may complete as many transactions as you like (buy one and later sell one share), but you must sell before you buy again and can hold at most one share at a time. Return the maximum net profit achievable. Describe your algorithm and analyze time and space complexity. Follow-ups: How would the solution change if the fee were charged on both buy and sell, or if multiple shares could be held concurrently?

Quick Answer: This question evaluates algorithm design skills, specifically understanding of dynamic programming and greedy strategies for optimizing profit under transaction fees, along with stateful decision-making and handling cost constraints.

You are given an integer array `prices` where `prices[i]` is the price of a given stock on day `i`, and an integer `fee` representing a commission charged each time you sell. You may complete as many transactions as you like (buy one share and later sell one share of the stock), but you must sell the share before you buy again, and you can hold at most one share at any time. The fee is charged on each completed sale. Return the **maximum net profit** you can achieve. Example: - `prices = [1, 3, 2, 8, 4, 9]`, `fee = 2` -> `8`. Buy at 1, sell at 8 (profit 8-1-2 = 5), buy at 4, sell at 9 (profit 9-4-2 = 3). Total = 8. Follow-ups to discuss (not graded): How would the solution change if the fee were charged on both buy and sell? What if you could hold multiple shares concurrently?

Constraints

1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4
An empty prices array returns 0.

Examples

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

Expected Output: 8

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

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

Expected Output: 6

Explanation: Buy at 1, sell at 10 (10-1-3 = 6). A single transaction beats splitting because each sale costs the fee.

Input: ([], 2)

Expected Output: 0

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

Input: ([5], 2)

Expected Output: 0

Explanation: Single day: you can never buy and sell, so profit is 0.

Input: ([9, 8, 7, 1], 1)

Expected Output: 0

Explanation: Strictly decreasing prices: no profitable transaction exists, so the best is to do nothing.

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

Expected Output: 13

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

Hints

Track two running states as you scan the days: the best net profit while holding no share (cash) and the best net profit while holding one share (hold).
On each day, you can sell (cash = max(cash, hold + price - fee)) or buy (hold = max(hold, cash - price)). Subtract the fee once per completed sale.
Initialize cash = 0 and hold = -prices[0], then iterate from day 1. The answer is cash at the end, since ending while holding a share is never better than having sold.

Quick Overview

This question evaluates algorithm design skills, specifically understanding of dynamic programming and greedy strategies for optimizing profit under transaction fees, along with stateful decision-making and handling cost constraints.