Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

Best answer is 10 and 50. Author made a mistake.

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

- Anonymous October 27, 2015 | Flag Reply
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;

- Alejandro October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- ikoryf October 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

well that's the answer right?

- aaa October 27, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 28, 2015 | Flag
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.

- ikoryf October 28, 2015 | Flag
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?

- simplysou November 04, 2015 | Flag
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[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;
}

- artur.ghandilyan October 28, 2015 | Flag Reply
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[0]

- zzqcraft October 29, 2015 | Flag
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;

- Alejandro October 27, 2015 | Flag Reply
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;

- Alejandro October 27, 2015 | Flag Reply
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;

- Alejandro October 27, 2015 | Flag Reply
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++;
		}
		int buy = i-1;
		while (i = stocks[i-1]) {
			i++;
		}
		int sell = i-1;
		profit += stocks[sell]-stocks[buy];
	}
}

- R@M3$H.N October 27, 2015 | Flag Reply
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) {
            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 );

}

- effy October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- jmr December 16, 2015 | Flag
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]
    return {'buy': array[minIndex], 'sell': array[maxIndex]}

- mgiroux0 October 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- revanthpobala October 27, 2015 | Flag
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;
	}

- ikoryf October 27, 2015 | Flag Reply
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

- test October 28, 2015 | Flag Reply
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.

- shree October 28, 2015 | Flag Reply
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;

- CodingPractice October 28, 2015 | Flag Reply
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[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;
        }

- x October 29, 2015 | Flag Reply
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[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))

- Dom November 01, 2015 | Flag Reply
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 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]);
}

- CodeKnight November 08, 2015 | Flag Reply
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) {
System.out.println("Pair buy="+s[min +" sell="+s[max]);
}
}

- howy November 12, 2015 | Flag Reply
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 }.

- Anonymous December 23, 2015 | Flag Reply
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

- solotronics February 02, 2016 | Flag Reply
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[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);
	}

- nikolay.ivanchev March 21, 2016 | Flag Reply
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

- demon_xxi March 29, 2016 | Flag Reply
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;
    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;
}

- Sean Carter May 01, 2016 | Flag Reply
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++) {
		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);
}

- smartbeast June 23, 2016 | Flag Reply
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")
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)

- rbrt.coleman September 27, 2016 | Flag Reply
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 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;
}
}
}}

- This is my solution July 07, 2017 | Flag Reply
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 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;
}
}
}}

- This is my solution July 07, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer should be Buy=10 and Sell=50

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

- deepjoarder July 21, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More