## Facebook Interview Question for Software Engineer / Developers

• 2

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
5
of 5 vote

{15, 50, 10, 45} => 15 and 50
{10, 45, 15, 50} => 10 and 50

Comment hidden because of low score. Click to expand.
3
of 3 vote

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;``````

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

last time I checked 40 is bigger than 35, therefore the answer is (and subsequently, the algorithm) is right.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

I think your code only checks consecutive values, what if the min/max are not next to one another?

Comment hidden because of low score. Click to expand.
2
of 2 vote

``````int max_gain_stock(const std::vector<int>& v)
{
if (v.empty())
{
return 0;
}
int min = v;
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;
}``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

you might want to consider the case when v.empty () == true before calling v

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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++;
}
while (i = stocks[i-1]) {
i++;
}
int sell = i-1;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

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) {
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 );

}``````

Comment hidden because of low score. Click to expand.
0

There is a bug. You can't buy on the last day and still sell.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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]

Comment hidden because of low score. Click to expand.
0

Dude what if the array has negative values? If the stock market looses then there will be a negative value. If that's the case your code fails.

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why does buying at 10 and selling at 50 not give max profit.How is the maximum profit equal to 35

Comment hidden because of low score. Click to expand.
0
of 0 vote

Why is the answer here not equal to 40. You buy at 10 on the first day and sell at 50.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````/*******************************************
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;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int GetMaxProfit(int[] a)
{
int profit = 0;
int maxProfit = 0;
int max = a;
int min = a;

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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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
min_price = prices
max_price = prices
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))``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public static void maxProfit()
{
int[] stock =  {10, 30, 42, 15, 20, 50, 10, 25};
int minIdx = 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;
}
else if(stock[j] < stock[minIdx])
{
minIdx = j;
}
j++;
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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) {
}
}

Comment hidden because of low score. Click to expand.
0
of 0 vote

I'm not sure this problem and answers. But I think we should consider to avoid local optimal solutions. Such as { 50, 100, 20, 80 } and { 20, 80, 50, 100 }.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````>>> 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``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int maxProfit(int[] a) {
if (a.length < 2) {
return 0;
}

int max = a;
int min = a;
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);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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

Comment hidden because of low score. Click to expand.
0
of 0 vote

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;

for (int i = 0; i < array.count; i++) {
if ([array[i] intValue] < lowestBuyAmount) {
}
else {
maxProfit = MAX(maxProfit, [array[i] intValue] - lowestBuyAmount);
}
}

return maxProfit;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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++) {
continue;
}
else if (a[i] - a[new_buy] > profit) {
sell = i;
}
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

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")
print("Stock Trace 2")
print("Stock Trace 3")

Stock Trace 1
best return: 9.390049641773377
sell at (val, idx): (9.400862760505838,14)
Stock Trace 2
best return: 9.390049641773377
sell at (val, idx): (9.400862760505838,14)
Stock Trace 3
best return: 8.121879769310974
sell at (val, idx): (9.400862760505838,13)``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
static int maxProfit(int[] p)
{
// by AniMus 2017/07/08
try
{
if (p.Length==0 || p.Length==1)
{
return 0;
}
int sell=p[p.Length-1];
int sellIndex=p.Length-1;

Console.WriteLine("");
for (int i=p.Length-2;i>=0;i--)
{
{
}
{
Console.WriteLine("Selling at {0} [{1}]",p[i],i);
sell=p[i+1];
sellIndex=i+1;
}

}
Console.WriteLine("Selling at \${0} on day {1}",sell,sellIndex);
}
catch(Exception)
{
throw;
}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
static int maxProfit(int[] p)
{
// by Ani.Mus 2017/07/08
try
{
if (p.Length==0 || p.Length==1)
{
return 0;
}
int sell=p[p.Length-1];
int sellIndex=p.Length-1;

Console.WriteLine("");
for (int i=p.Length-2;i>=0;i--)
{
{
}
{
Console.WriteLine("Selling at {0} [{1}]",p[i],i);
sell=p[i+1];
sellIndex=i+1;
}

}
Console.WriteLine("Selling at \${0} on day {1}",sell,sellIndex);
}
catch(Exception)
{
throw;
}
}
}}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def maxprofit(self,stock):
min_price=sys.maxint()
max_profit = 0
for i in xrange(len(stock)):
if stock[i] < min_price:
min_price=stock[i]
if stock[i] - min_price > max_profit:
max_profit = stock[i] - min_price
return max_profit``````

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.