Facebook Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
If I understand correctly, the answer for that particular example would be buying on 15 and selling on 50. If that's the case and I didn't get something wrong, this is a straight-forward max sum on a 1D array (prefix sum).
Code should look something like this:
int best = 0, curr = 0;
for (int i = 1; i < A.size(); i++) {
curr += (A[i]-A[i-1]);
curr = curr < 0 ? 0 : curr;
best = curr > best ? curr : best;
}
return best;
This code returns 40 instead of 35 for input [10, 30, 42, 15, 20, 50, 10, 25].
It counts max profit between 10 (1st element) and 50, instead of 15 (4th element) and 50.
last time I checked 40 is bigger than 35, therefore the answer is (and subsequently, the algorithm) is right.
I believe that the question asks for buy/sell values that are not containing local minimums and maximums in between. Just a straight gain from buy to sell instances.
The author of this question may need to clarify though.
int max_gain_stock(const std::vector<int>& v)
{
if (v.empty())
{
return 0;
}
int min = v[0];
int max_gain = 0;
for (int i = 1; i < v.size(); ++i)
{
int local = v[i] - min;
if (local > max_gain)
{
max_gain = local;
}
if (v[i] < min)
{
min = v[i];
}
}
return max_gain;
}
To solve this problem efficiently in O(N), you would need to track the minimum value’s index. As you traverse, update the minimum value’s index when a new minimum is met. Then, compare the difference of the current element with the minimum value. Save the buy and sell time when the difference exceeds our maximum difference (also update the maximum difference).
void getMaxProfit(int stocks[], int sz, int &profit) {
if (sz == 1) {
profit = 0;
return;
}
profit = 0;
for (int i = 1; i < sz; i++) {
while (i < sz && stocks[i] <= stocks[i-1]) {
i++;
}
int buy = i-1;
while (i = stocks[i-1]) {
i++;
}
int sell = i-1;
profit += stocks[sell]-stocks[buy];
}
}
O(n) time, O(1) space.
static void becomeABillionaire(int arr[]) {
int i = 0, buy = 0, sell = 0, min = 0, profit = 0;
for (i = 0; i < arr.length; i++) {
if (arr[i] < arr[min])
min = i;
else if (arr[i] - arr[min] > profit) {
buy = min;
sell = i;
profit = arr[i] - arr[min];
}
}
System.out.println("We will buy at : " + arr[buy] + " sell at " + arr[sell] +
" and become billionaires worth " + profit );
}
def bestBuySell(array):
minIndex = 0
maxIndex = 0
bestProfit = 0
for i, x in enumerate(array):
if x < minIndex:
minIndex = i
elif x - array[minIndex] > bestProfit:
maxIndex = i
bestProfit = x - array[minIndex]
return {'buy': array[minIndex], 'sell': array[maxIndex]}
Modified version of Kadane's algorithm which tracks from and to indexes, O(n) time.
public static int maxProfit(int[] input) {
int maxSoFar = 0;
int maxEndingHere = 0;
int maxEndingHerePrev = 0;
int maxBest = 0;
int fromTemp = -1;
int from = -1;
int to = -1;
for (int i = 1; i < input.length ; i++) {
maxEndingHere = maxEndingHere + input[i] - input[i-1 ];
if (maxEndingHere < maxEndingHerePrev) { maxEndingHere = 0; fromTemp = i; }
if (maxSoFar < maxEndingHere) maxSoFar = maxEndingHere;
maxEndingHerePrev = maxEndingHere;
if (maxEndingHere > maxBest) {
from = fromTemp;
to = i;
maxBest = maxEndingHere;
}
}
System.out.println("Max profit is "+maxBest + ". Buy at "+input[from]+", sell at "+input[to]);
return maxBest;
}
/*******************************************
O(n^2)
/*******************************************
int max = 0; int sz = A.size();
for(int i = 0; i < sz; i++)
for(int j =i+1; j<sz;j++)
max = ((a[j]-a[i])>max?(a[j]-a[i]):max);
cout<<"The biggest difference is "<< max<<endl;
/******************************************************
O(n)
/******************************************************
int max = 0, min = 0, indexMin=0, indexMax=0;int sz = A.size();
for(int i = 0; i < sz; i++)
{
if(a[i]>max){ max = a[i]; indexMax = i;}
}
min = max;
for(int i = 0; i < sz; i++)
{
if(a[i]<min && (indexMin < indexMax)){ min = a[i]; indexMin = i;}
}
if(indexMax > indexMin)
cout<<"The biggest difference is "<< max-min<<endl;
else
cout<<"The biggest difference is "<< 0<<endl;
public int GetMaxProfit(int[] a)
{
int profit = 0;
int maxProfit = 0;
int max = a[0];
int min = a[0];
for (int i = 1; i < a.Length; i++)
{
if (a[i] < max)
{
min = a[i];
max = a[i];
}
else if (a[i] > max)
{
max = a[i];
profit = max - min;
if (profit > maxProfit)
maxProfit = profit;
}
}
return maxProfit;
}
The question is a bit unclear, but nothing the interviewer wouldn't be able to clarify in 20 seconds. My understanding is that a buy/sell price is only valid during a buy-sell cycle. Using the example above you would need to sell your stock for 42 if you bought it for 10, 50 if you bought it for 15, etc,.
def max_profit(prices):
if not prices:
return 0
prev = prices[0]
min_price = prices[0]
max_price = prices[0]
profit = 0
for i in range(len(prices)):
if prices[i] < min_price:
min_price = prices[i]
elif prices[i] > max_price:
max_price = prices[i]
tmp_profit = max_price - min_price
if tmp_profit > profit:
profit = tmp_profit
if prices[i] < prev:
min_price = prices[i]
max_price = prices[i]
prev = prices[i]
return profit
stock_prices = [10, 30, 42, 15, 20, 50, 10, 25]
print(max_profit(stock_prices))
public static void maxProfit()
{
int[] stock = {10, 30, 42, 15, 20, 50, 10, 25};
int minIdx = 0;
int buyIdx = 0;
int sellIdx = 0;
int maxDiff = 0;
int j = 0;
while(j < stock.length)
{
if(stock[j] - stock[minIdx] > maxDiff)
{
maxDiff = stock[j] - stock[minIdx];
sellIdx = j;
buyIdx = minIdx;
}
else if(stock[j] < stock[minIdx])
{
minIdx = j;
}
j++;
}
System.out.println("buy"+stock[buyIdx]+"sell"+stock[sellIdx]);
}
public static void findStockPair(int[] s) {
int n = s.length;
int maxDiff = 0;
int min = -1;
int max = -1;
for(int i=0; i<n-1; i++) {
for(int j=i+1;j<n;j++) {
int diff = s[j] - s[i];
if( diff > maxDiff ) {
maxDiff = diff;
min=i;
max=j;
}
}
}
if( min!=-1 && max!=-1) {
System.out.println("Pair buy="+s[min +" sell="+s[max]);
}
}
>>> def make_cash(i):
... lowest,highest=0,0
... for pos,x in enumerate(i):
... if pos==0:
... lowest=x # theoretical highest cant be on the first day
... elif pos!=len(i)-1: # theoretical buy or sell any day
... if x<lowest: lowest=x
... if x>highest: highest=x
... elif pos==len(i)-1: # cant buy on the last day!
... if x>highest: highest=x
... return highest-lowest
public int maxProfit(int[] a) {
if (a.length < 2) {
return 0;
}
int max = a[0];
int min = a[0];
int currentProfit = 0;
int possibleMin = min;
int maxInd = 0;
for (int i = 1; i < a.length; i++) {
if (max < a[i]) {
max = a[i];
currentProfit = max - min;
}
if (possibleMin > a[i]) {
possibleMin = a[i];
}
if (a[i] - possibleMin > currentProfit) {
min = possibleMin;
max = a[i];
currentProfit = max - min;
}
}
return Math.max((max - min),0);
}
def bestPrice(stock):
best = minp = 0
for currp in xrange(1, len(stock)):
# if found price lower than previous lowest
if stock[currp] < stock[minp]:
minp = currp
# evaluate profit comparing to lowest
else:
best = max(stock[currp] - stock[minp], best)
return best
print(bestPrice([10, 30, 42, 15, 20, 50, 10, 25])) # 40
print(bestPrice([10, 5, 30, 42, 15, 20, 50, 10])) # 45
Straight forward. You know basically want to iterate through the array, and compare the smallest value you find, with all values ahead of that value. As you iterate if you find a smaller value, you use that one instead for the calculations. Here it is in objective-c.
Here is a solution in Obj-C:
+ (int)maxStockMarketProfit:(NSArray *)array
{
if (array.count < 2)
return 0;
int maxProfit = 0;
int lowestBuyAmount = INT_MAX;
for (int i = 0; i < array.count; i++) {
if ([array[i] intValue] < lowestBuyAmount) {
lowestBuyAmount = [array[i] intValue];
}
else {
maxProfit = MAX(maxProfit, [array[i] intValue] - lowestBuyAmount);
}
}
return maxProfit;
}
void get_buy_sell(int *a, int sz)
{
int buy = 0, sell = 0, profit = 0, new_buy = 0;
int i;
for (i = 0; i < sz; i++) {
if (a[new_buy] >= a[i]) {
new_buy = i;
continue;
}
else if (a[i] - a[new_buy] > profit) {
buy = new_buy;
sell = i;
profit = a[i] - a[new_buy];
}
}
printf("buy : %d, sell : %d\n", buy, sell);
}
This problem is similar to some other dynamic programming problems, all of which are looking for the largest cumulative sum sub-array. In this case, we're not looking for the largest cumulative sum, but the most positive a[right_idx] - a[left_idx].
General solution:
The crux of the solution is to keep a left pointer, and run right pointers forward, cumulatively summing the elements as we go. If our cumulative sum is larger than any we've found so far, we replace that best result with the new one. We stop each of these cumulative runs when the cumulative sum drops to zero. When the cumulative sum drops to zero, we move the left pointer to the location of the right pointer and begin another forward run with the right pointer.
We stop the whole process when the right pointer reaches the end.
Specific solution:
In this case, we don't compute a cumulative sum, but the a[right_idx] - a[left_idx].
The complexity will be O(n) in compute, since for each new run, we move the left pointer to meet the right pointer. Memory use will be O(1) in memory since the only auxiliary data structures we need are pointers and the best difference.
def buy_low_sell_high(stock_trace):
best_diff = 0
best_left = -1
best_right = -1
left_idx = 0
right_idx = 0
while right_idx < len(stock_trace) - 1:
right_idx = left_idx + 1
# run, right pointer
while right_idx < len(stock_trace) - 1:
diff = stock_trace[right_idx] - stock_trace[left_idx]
if diff > best_diff:
best_diff = diff
best_left = left_idx
best_right = right_idx
elif diff <= 0:
# move left pointer to right pointers location
left_idx = right_idx
# start a new run
break
right_idx += 1
print("best return: {}".format(best_diff))
print("buy at (val, idx): ({},{})".format(stock_trace[best_left], best_left))
print("sell at (val, idx): ({},{})".format(stock_trace[best_right], best_right))
Some inputs
stock_trace1 = [
0.010813118732461158,
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
stock_trace2 = [
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
0.010813118732461158,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
stock_trace3 = [
7.848782642974635,
6.412165671008653,
2.41400198901051,
7.380876605993766,
7.050665938613819,
1.545930172530945,
4.890855121484591,
4.007390799132676,
4.959796684292704,
8.252891965307231,
1.2789829911948636,
3.0432514514857867,
6.694507808651309,
9.400862760505838,
0.5439483796581279,
5.538854666259302,
0.010813118732461158,
0.15483879273656131,
5.923645176042162,
1.6929368892019125
]
The outputs
print("Stock Trace 1")
buy_low_sell_high(stock_trace1)
print("Stock Trace 2")
buy_low_sell_high(stock_trace2)
print("Stock Trace 3")
buy_low_sell_high(stock_trace3)
Stock Trace 1
best return: 9.390049641773377
buy at (val, idx): (0.010813118732461158,0)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 2
best return: 9.390049641773377
buy at (val, idx): (0.010813118732461158,10)
sell at (val, idx): (9.400862760505838,14)
Stock Trace 3
best return: 8.121879769310974
buy at (val, idx): (1.2789829911948636,10)
sell at (val, idx): (9.400862760505838,13)
{{
static int maxProfit(int[] p)
{
// by AniMus 2017/07/08
try
{
if (p.Length==0 || p.Length==1)
{
return 0;
}
int buy=p[p.Length-1];
int buyIndex=p.Length-1;
int sell=p[p.Length-1];
int sellIndex=p.Length-1;
Console.WriteLine("");
for (int i=p.Length-2;i>=0;i--)
{
if (sell-p[i]> sell-buy )
{
buy=p[i];
buyIndex=i;
}
if (p[i+1]-buy> sell-buy & i>=buyIndex )
{
Console.WriteLine("Selling at {0} [{1}]",p[i],i);
sell=p[i+1];
sellIndex=i+1;
}
}
Console.WriteLine("Buying at ${0} on day {1}",buy,buyIndex);
Console.WriteLine("Selling at ${0} on day {1}",sell,sellIndex);
return sell-buy;
}
catch(Exception)
{
throw;
}
}
}}
{{
static int maxProfit(int[] p)
{
// by Ani.Mus 2017/07/08
try
{
if (p.Length==0 || p.Length==1)
{
return 0;
}
int buy=p[p.Length-1];
int buyIndex=p.Length-1;
int sell=p[p.Length-1];
int sellIndex=p.Length-1;
Console.WriteLine("");
for (int i=p.Length-2;i>=0;i--)
{
if (sell-p[i]> sell-buy )
{
buy=p[i];
buyIndex=i;
}
if (p[i+1]-buy> sell-buy & i>=buyIndex )
{
Console.WriteLine("Selling at {0} [{1}]",p[i],i);
sell=p[i+1];
sellIndex=i+1;
}
}
Console.WriteLine("Buying at ${0} on day {1}",buy,buyIndex);
Console.WriteLine("Selling at ${0} on day {1}",sell,sellIndex);
return sell-buy;
}
catch(Exception)
{
throw;
}
}
}}
Best answer is 10 and 50. Author made a mistake.
- Anonymous October 27, 2015{15, 50, 10, 45} => 15 and 50
{10, 45, 15, 50} => 10 and 50