But it doesn't have to end here! Sign up for the 7-day coding interview crash course and you'll get a free Interview Cake problem every week.
You're in!
Writing programming interview questions hasn't made me rich yet ... so I might give up and start trading Apple stocks all day instead.
First, I wanna know how much money I could have made yesterday if I'd been trading Apple stocks all day.
So I grabbed Apple's stock prices from yesterday and put them in an array called stockPrices, where:
So if the stock cost $500 at 10:30am, that means stockPrices[60] = 500.
Write an efficient method that takes stockPrices and returns the best profit I could have made from one purchase and one sale of one share of Apple stock yesterday.
For example:
int[] stockPrices = { 10, 7, 5, 8, 11, 9 };
// Returns 6 (buying for $5 and selling for $11)
GetMaxProfit(stockPrices);
No "shorting"—you need to buy before you can sell. Also, you can't buy and sell in the same time step—at least 1 minute has to pass.
We’ll greedily walk through the array to track the max profit and lowest price so far.
For every price, we check if:
To start, we initialize:
We decided to return a negative profit if the price decreases all day and we can't make any money. We could have thrown an exception instead, but returning the negative profit is cleaner, makes our method less opinionated, and ensures we don't lose information.
using System;
public static int GetMaxProfit(int[] stockPrices)
{
if (stockPrices.Length < 2)
{
throw new ArgumentException("Getting a profit requires at least 2 prices",
nameof(stockPrices));
}
// We'll greedily update minPrice and maxProfit, so we initialize
// them to the first price and the first possible profit
int minPrice = stockPrices[0];
int maxProfit = stockPrices[1] - stockPrices[0];
// Start at the second (index 1) time.
// We can't sell at the first time, since we must buy first,
// and we can't buy and sell at the same time!
// If we started at index 0, we'd try to buy *and* sell at time 0.
// This would give a profit of 0, which is a problem if our
// maxProfit is supposed to be *negative*--we'd return 0.
for (int i = 1; i < stockPrices.Length; i++)
{
int currentPrice = stockPrices[i];
// See what our profit would be if we bought at the
// min price and sold at the current price
int potentialProfit = currentPrice - minPrice;
// Update maxProfit if we can do better
maxProfit = Math.Max(maxProfit, potentialProfit);
// Update minPrice so it's always
// the lowest price we've seen so far
minPrice = Math.Min(minPrice, currentPrice);
}
return maxProfit;
}
time and space. We only loop through the array once.
This one's a good example of the greedy approach in action. Greedy approaches are great because they're fast (usually just one pass through the input). But they don't work for every problem.
How do you know if a problem will lend itself to a greedy approach? Best bet is to try it out and see if it works. Trying out a greedy approach should be one of the first ways you try to break down a new question.
To try it on a new problem, start by asking yourself:
"Suppose we could come up with the answer in one pass through the input, by simply updating the 'best answer so far' as we went. What additional values would we need to keep updated as we looked at each item in our input, in order to be able to update the 'best answer so far' in constant time?"
In this case:
The "best answer so far" is, of course, the max profit that we can get based on the prices we've seen so far.
The "additional value" is the minimum price we've seen so far. If we keep that updated, we can use it to calculate the new max profit so far in constant time. The max profit is the larger of:
Try applying this greedy methodology to future questions.
Reset editor
Powered by qualified.io