Hedge Funds puzzles, solved step by step
- Puzzles
- 100
- Traced to a firm
- 38
- Topics
- 14
- Hard
- 30
008A stock closes at 100, 96, 104, 99, 110, 105 and 112 on seven days, and short selling is not allowed. What is the maximum profit from one buy and one sell, and from any number of round trips?Man GroupLondon · 2019
Try it first
What is the most you can make with any number of round trips?
Show the worked solution
One round trip makes at most 16; unlimited round trips make 26. For one trade, walk the prices once, carrying the lowest price so far and the best sale against it: buy at 96, sell at 112. For many trades, add every day-on-day rise and skip every fall: 8 + 11 + 7 = 26. Without short selling the falls are simply sat out, never profited from.
How do you find the best single trade without checking every pair?
Imagine walking down a street of shops that all sell the same phone, planning to buy once and sell once further along. You do not need to compare every pair of shops: carry the cheapest price seen so far in your head, and at each shop ask what selling here would make against it. One pass, keeping the running minimum and the best gap found so far, gives the best single trade. Here the running minimum drops to 96 on day 2 and the best gap appears on day 7: 112 - 96 = 16.
The best single trade buys at 96 on day 2 and sells at 112 on day 7 for 16, while trading every rising leg, 96 to 104, 99 to 110 and 105 to 112, collects 8 + 11 + 7 = 26. Day Price Move Lowest so far Best single trade so far Sum of rises so far 1 100 100 0 0 2 96 -4 96 0 0 3 104 +8 96 8 8 4 99 -5 96 8 8 5 110 +11 96 14 19 6 105 -5 96 14 19 7 112 +7 96 16 26 One pass through the prices tracks both answers at once: the running minimum gives the best single trade, 16, and the running sum of positive moves gives the many-trade maximum, 26. Why is the many-trade answer just the sum of the rises?
Any rise from a low to a later high is the sum of the daily steps inside it, and some of those steps may be falls. With no short selling and no costs, the most you can make is the total of every positive day-on-day move, 26 here, because trading only the up steps collects everything a longer trade would and skips its falls. In practice that is three round trips: buy 96, sell 104; buy 99, sell 110; buy 105, sell 112.
What does the interviewer add next?
Costs. Once each round trip costs something, the sum of rises overstates the profit, because small moves stop being worth trading. With a cost of 6 per round trip, the three separate trades net 2 + 5 + 1 = 8, the best two-trade split nets 9, and the single trade from 96 to 112 nets 10, so the single trade now wins. The general version is a short dynamic programme that tracks the best profit on each day while holding and while flat.
Where candidates lose it
For the first part, candidates take the lowest and highest prices without checking the order. Here they happen to line up, 96 before 112, but an interviewer who swaps two prices will catch anyone who never checked that the low comes first.
For the second, the loss is counting falls as profit, which needs a short sale the question forbids, or stopping at 16 because it is the best single trade. Say the rule plainly: bank every rise, sit out every fall.
What the interviewer asks next
- What if each round trip costs 6?
- What if you may make at most two round trips?
- How does the answer change if short selling is allowed?
Asked at Man Group, Alternative Investments, London, 2019 (Wall Street Oasis):
Given a series of prices, find the one buy/sell trade pair which gives the maximum profit
