DSA interview question

Best Time to Buy and Sell Stock with Transaction Fee

Medium · Algorithms · Topics: dynamic programming, array, state machine

The problem

You're building a trading bot backend for a fintech app. The brokerage charges a flat fee on every completed transaction (buy + sell pair). You're given an array prices where prices[i] is the stock price on day i, and an integer fee representing the transaction fee. You can buy and sell as many times as you want, but you must sell before you buy again (i.e., you can only hold at most one share at a time). Your job: return the maximum profit achievable, accounting for the fee on every transaction.

Function signature

int maxProfit(vector<int>& prices, int fee);

Test cases

Input `prices`	`fee`	Output	Explanation
`[1,3,2,8,4,9]`	2	8	Buy@1, sell@8 (profit 7-2=5), buy@4, sell@9 (profit 5-2=3) → total 8
`[1,3,7,5,10,3]`	3	6	Buy@1, sell@10 (profit 9-3=6), skip other trades since fee eats profit
`[1,2,3,4,5]`	1	3	Buy@1, sell@5 (profit 4-1=3); splitting into multiple trades costs more fee
`[1]`	2	0	Can't complete any transaction
`[]`	1	0	Empty array
`[5,4,3,2,1]`	1	0	Prices only decrease — no profitable trade possible

(Always verify: does one big trade beat multiple small trades once fee is introduced? That's the crux of this problem.)

How interviewers phrase it

"You can buy and sell stock unlimited times, but each transaction costs a fixed fee. Maximize profit."
"This is a variant of 'Best Time to Buy and Sell Stock II' — now there's a cost per trade."
They may probe: "Why can't you just greedily take every positive price difference like in the no-fee version?"

Clarifying questions to ask

Is the fee charged once per completed transaction (buy+sell pair), or separately on buy and on sell?
Can I hold at most one share at a time (no multiple concurrent holdings)?
Must I sell before buying again, or can I buy multiple times before selling?
What's the range/size of prices and fee? (Signals whether O(n) is required vs O(n²) DP is acceptable.)
Are prices guaranteed non-negative integers?

Follow-ups to expect

"Can you do this in O(1) space?"
"What if there's a limit on the number of transactions (like at most k trades)?"
"What if there's a cooldown period after selling?"
"Why does a greedy 'buy low, sell high on every uptick' approach fail here?"
"Can you also return the actual days to buy/sell, not just profit?"
"What if fee applies to both buy and sell separately?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview