Facebook Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
7
of 9 vote

Same concept as stock buying and selling given that the buy date is before the sell date and you want maximum profit.

#include<stdio.h>
 
/* The function assumes that there are at least two
   elements in array.
   The function returns a negative value if the array is
   sorted in decreasing order.
   Returns 0 if elements are equal  */
int maxDiff(int arr[], int arr_size)
{
  int max_diff = arr[1] - arr[0];
  int min_element = arr[0];
  int i;
  for(i = 1; i < arr_size; i++)
  {      
    if(arr[i] - min_element > max_diff)                              
      max_diff = arr[i] - min_element;
    if(arr[i] < min_element)
         min_element = arr[i];                    
  }
  return max_diff;
}   
 
/* Driver program to test above function */
int main()
{
  int arr[] = {1, 2, 6, 80, 100};
  int size = sizeof(arr)/sizeof(arr[0]);
  printf("Maximum difference is %d",  maxDiff(arr, size));
  getchar();
  return 0;
}

Time Complexity: O(n)
Auxiliary Space: O(1)

- Anonymous January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

PS: Array does not have to be sorted, works also for unsorted arrays, for example: [2, 3, 10, 6, 4, 8, 1] where max diff = 10 - 2 = 8

- Anonymous January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question should be "large element should appear after lower"

- Psycho January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

You should cite geeksforgeeks if you borrow code.

- jgreen February 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

public class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;

        int min_val = Integer.MAX_VALUE;
        int max_diff = 0;

        for(int i = 0; i < n; i++) {
            if (prices[i] < min_val)
                min_val = prices[i];
            
            int diff = prices[i] - min_val;
            if (diff > max_diff)
                max_diff = diff;
        }

        return max_diff;
    }
}

- David January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

A simple solution in C with linear time complexity
The given array is A = {10, 3, 6, 8, 9, 4, 3}

int max = 0;
int res = 0;
for(int i = n - 1; i >= 0; i--)
{
	if(A[i] > max)
		max = A[i];
	int tempdiff = max - A[i];
	if(tempdiff > res)
		res = tempdiff;	// this gives the maximum difference in the array	
}

- vivekveeriah January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In the example, if I'm understanding the question properly, the best possible solution is 6, the difference between the first element and the last element of the array.

More generally, if we iterate forward from an element with value x, any number we encounter that is greater than x cannot be the min part of the solution, since we can always use x instead.

Iterate through all the elements, at each step checking the difference between the min and the element, updating the best solution found so far if necessary. If a new min is found update the min

- Anonymous January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Identify the max-diff from the back and iterate till front. It roughly looks like below

int maxdiff;
int smallest = arr[n-1];
int largest = arr[n-1];
for(int i=n-2; i>=0; i--)
{
int currentMaxDiff = Max(abs(arr[i]-smallest), abs(arr[i]-largest));
if(currentMaxDiff>maxdiff)
{
maxdiff=currentMaxdiff;
}
if(arr[i]<smallest)
{
arr[i] = smallest;
}
if(arr[i]>largest)
{
arr[i] = largest;
}
}

MaxDiff should have the maximum difference at the end.

- Din January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is not correct since you don't account for 'given the second element comes after the first'
Your solution delivers 2 for {3, 2, 1} but it should really be -1

- The great white January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Actually I got confusion with your answer as per your example 1-3 can produce -2 but you mentioned as it should be -1 (1-2) pls explain.

- Anbu January 29, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Given an array, find the maximum difference between two array elements -->given the second element comes after the first.<--

- The great white January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Oh, now I get what you mean. Yeah, my mistake, -2 is correct then.

- The great white January 30, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this is a typical dynamic programming question. Using following formula to get:
D[i] = D[i-1] + (A[i] - A[i-1])
D[0] = 0

Where A[] is the input array and D[] is the difference array that we calculate from input A[].


For example, A[] = 1, 5, 8, 7, 9, -5, 15, 21
Calculate D[] = 0, 4, 7, 6, 8, -6, 14, 20
go through D[] to find the maximum difference is 20, which is really O(n) complexity

- w.y January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Shouldn't the answer be 26 in your example? Max is 21 and Min is -5 and the difference = 26?

- J January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

one pass

public class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;

int min_val = Integer.MAX_VALUE;
int max_diff = 0;

for(int i = 0; i < n; i++) {
if (prices[i] < min_val)
min_val = prices[i];

int diff = prices[i] - min_val;
if (diff > max_diff)
max_diff = diff;
}

return max_diff;
}
}

- David January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is like the problem "best time to buy and sell stock".

def maxdiff(A):
	min_val = float('inf')
	diff = 0
	for a in A:
		min_val = min(min_val, a)
		c = abs(a - min_val)
		diff = max(diff, c)
	return diff

- yanshidong10123815 January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void MaximumDiff()
{
int[] arr = { 7, 6, 15, 4, 3, 21, 1 };

int min = arr[0];
int max = arr[1];
int diff = max - min;
bool minchanged = false;
bool maxchanged = false;
for (int i = 1; i < arr.Length - 1; i++)
{
minchanged = false;
maxchanged = false;
if (arr[i] < min)
{
min = arr[i];
minchanged = true;
}
if (arr[i + 1] > max)
{
max = arr[i + 1];
maxchanged = true;
}

if (minchanged && maxchanged && (max - min) > diff)
diff = max - min;
if (maxchanged && (max - min) > diff)
diff = max - min;
}
Console.WriteLine(diff);
}

- kiran007 January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

public class FindDifference {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}

}

- Punto February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

public class FindDifference {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}

}

- Punto February 17, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

This works - O(n) solution.

int maxDifference(int [] array) {
		if (array.length <= 1) {
			System.out.println("Size of the array should be greater than 1");
			System.exit(1);
		}
		int currentMaxDiff = array[1] - array[0];
		int currentMin = array[0] < array[1] ? array[0] : array[1];
		for (int i = 2; i < array.length; i++) {
			if (array[i] - currentMin > currentMaxDiff) {
				currentMaxDiff = array[i] - currentMin;
			}
			if (currentMin > array[i]) {
				currentMin = array[i];
			}
		}
		return currentMaxDiff;
	}

- Sumeet Singhal January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

dp ?

public int findMaxDiff (int [] A){
		int [] left = new int [A.length] ;
		int leftMax = Integer.MIN_VALUE ;
		for (int i = 1 ; i < A.length ; ++i) {
			if (A[i] > A[i - 1]) left[i] = A[i] - A[i - 1] + left[i - 1];			
			leftMax =  Math.max(leftMax, left[i]);
		}
		int rightMax = Integer.MIN_VALUE ;
		int [] right = new int [A.length] ;
		for (int i = A.length - 1 ; i > 0 ; --i) {
			if (A[i -1] > A[i]) right[i - 1] = A[i -1] - A[i] + right[i];			
			rightMax = Math.max(rightMax, right[i - 1]);
		}		
		return Math.max(leftMax, rightMax) ;

}

- Scott January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaxDifference {

    public static void main(String args[]) {

        int array[] = { 1, 2, 1, 4, 5, 6, 7 };
        // int array[] = { 3, 2, 1, 4, 5, 6, 7 };

        int maxDiff = Integer.MIN_VALUE;
        int mineleMent = array[0];

        for (int i = 1; i < array.length; i++) {

            int diff = array[i] - mineleMent;
            if (diff > maxDiff) {
                maxDiff = diff;
            }

            if (array[i] < mineleMent) {
                mineleMent = array[i];
            }
        }

        System.out.println(maxDiff);
    }

    /*
     * Time Complexity: O(n) Auxiliary Space: O(1)
     */
}

- Magemello January 29, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int maxDiff(int[] arr){
        if (arr.length <= 1){
            return Integer.MIN_VALUE;
        }
        int[] maxRight = new int[arr.length];
        maxRight[arr.length - 1] = arr[arr.length-1];
        for (int i = arr.length - 2; i >= 0; i--){
            maxRight[i] = Math.max(arr[i], maxRight[i+1]);
        }
        int maxDiff = Integer.MIN_VALUE;
        for (int i = 0 ; i < arr.length; i++){
            maxDiff = Math.max(maxDiff , maxRight[i] - arr[i]);
        }
        return maxDiff;
    }

- GK January 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int solve(int[] arr) {
    if(arr.length < 2) return -1;

    int maxDiff = 0;
    int min = arr[0];

    for(int i = 1; i < arr.length; i++) {
      maxDiff = Math.max(maxDiff, arr[i] - min);
      min = Math.min(min, arr[i]);
    }

    return maxDiff;
  }

- jgreen February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DiffMax{
	public static void main(String args[]){
		int arr[] = {3,5,8,2,0,3,6,9};
		int max_diff =0;
		int num=arr[arr.length-1];
		for(int i =arr.length-2;i>=0;i--){
			if(arr[i] > num){
				num = arr[i];
			}else if(arr[i] <num){
				max_diff = max_diff < num - arr[i]?num-arr[i]:max_diff;
			}
			
		}

		System.out.println("max diff is "+max_diff);

	}

}

- Bond February 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

iteration through the array actually starts at i=1,but since one may like to see the other differences between elements,I am starting from 0.

#include <iostream>

using namespace std;

void find_max(int arr [], int arr_len){
	int max = arr[1] - arr[0];
	for(int i = 0; i < arr_len - 1; i++ ){
		//cout<< arr[i+1] - arr[i]<<" ";
		if(max < arr[i+1] - arr[i]){
			max = arr[i+1] - arr[i];
			
		}
	}
	
	cout<<endl<<max<<endl;
		return;
}

int main(){
	int arr[] = { 0,6,14,19,20,60,61,70,85,95,100};
	find_max(arr,11);
	return 0;

}

- Tinashe February 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here I find the maximun and then find min before the maximun.
Then find the minnimun and then find the max after minimun.

Compare which one is greater.

void Main()
{
	int[] A = new int[]{
		3,4,5,7,8,9,11,12,15,4,6,7,8,100,0,99
	};
	
	Console.WriteLine(MaxDifference(A));
}

public static int MaxDifference(int[] A)
{
	int max = int.MinValue;
	int max_min = int.MaxValue;
	int max_index = -1;
	
	int min = int.MaxValue;
	int min_max = int.MinValue;
	int min_index = -1;
	
	for(int i = 0; i < A.Length; i++)
	{
		int a = A[i];
		if(max < a)
		{
			max_index = i;
			max = a;
		}
		
		if(min > a)
		{
			min_index = i;
			min = a;
		}
	}
	
	// Max Diference of max
	for(int i = 0; i < max_index; i++)
	{
		int a = A[i];
		if(max_min > a)
		{
			max_min = a;
		}
	}
	
	for(int i = min_index + 1; i < A.Length; i++)
	{ 
		int a = A[i];
		if(min_max < a)
		{
			min_max = a;
		}
	}
	
	int min_diff = (min_max - min);
	int max_diff = (max - max_min);
	
	return (max_diff > min_diff)?max_diff:min_diff;
}

- Nelson Perez February 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

function getMaximumDiff(arr) {
  var lo = arr[0], result = 0;

  for (var i = 0; i < arr.length; i++) {
    lo = Math.min(lo, arr[i]);
    result = Math.max(result, arr[i] - lo);
  }

  return result;
}

- shysta February 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Solution in Ruby

array = [2, 3, 10, 6, 4, 8, 1] 

min_num = array[0]
max_diff = 0

1.upto(array.length - 1) do |i|
  min_num = [min_num, array[i]].min
  max_diff = [max_diff, array[i]- min_num].max
end

p diff

- Tyrone Hsu February 16, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindDifference {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] a = {1,4,7,-7,5};
		int len = a.length;
		int j=0;int k=len-1;
		for(int i=len-1;i>=0;i--){
			int max = Math.max(a[i],a[j]);
			int min = Math.min(a[i],a[j]);
			System.out.println(min);
			a[k] = max-min;
			k--;
		}
		System.out.println("After Calculation");
		for(int diff : a){
			System.out.print(diff+",");
		}
	}

}

- Punto February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindDifference {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}

}

- Punto February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

and

public class FindDifference {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}

}

and

- Punto February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindDifference {

/**
* @param args
*/
public static void main(String[] args) {

int[] a = {1,4,7,-7,5};
int len = a.length;
int j=0;int k=len-1;
for(int i=len-1;i>=0;i--){
int max = Math.max(a[i],a[j]);
int min = Math.min(a[i],a[j]);
System.out.println(min);
a[k] = max-min;
k--;
}
System.out.println("After Calculation");
for(int diff : a){
System.out.print(diff+",");
}
}

}

- Punto February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindDifference {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		
		int[] a = {1,4,7,-7,5};
		int len = a.length;
		int j=0;int k=len-1;
		for(int i=len-1;i>=0;i--){
			int max = Math.max(a[i],a[j]);
			int min = Math.min(a[i],a[j]);
			System.out.println(min);
			a[k] = max-min;
			k--;
		}
		System.out.println("After Calculation");
		for(int diff : a){
			System.out.print(diff+",");
		}
	}

}

- Punto February 17, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int maxDiff(std::vector<int>& vec)
{
if (vec.size() < 2)
{
return -1;
}

int maxDiff = vec[1] - vec[0];
int minElem = vec[0];

for (int i = 1; i < vec.size(); ++i)
{
maxDiff = max(vec[i] - minElem, maxDiff);
minElem = min(minElem, vec[i]);
}

return maxDiff;
}

- Anonymous February 26, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Test Comment 1.

- frankie February 27, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int maxDifference (int[] a) {
		int min = a[0];
		int max = a[1];
		int maxDiff = max-min;
		
		for (int i = 0; i < a.length; i++) {
			if (a[i] - min > maxDiff) {
				maxDiff = a[i] - min;
			} else if (a[i] < min) {
				min = a[i];
			}
		}
		
		return maxDiff;
	}

- ag March 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
class MaxDifference2Elem
{
    
    static int maxDiff(int[] arr)
    {
        int min=0,max=0;
        int[] diff=new int[arr.length-1];
        for(int i=0;i<arr.length;++i)
        {
            //System.out.println("arr[i]: "+arr[i]+" arr[min]: "+arr[min]);
            if(arr[i]<arr[min])
               min=i;
            if(arr[i]>arr[max])
               max=i;
            if(i+1<arr.length)
                diff[i]=arr[i+1]-arr[i];
        }
        int res=0;
        
        if(min>max)
        {
            int temp=min;
            min=max;
            max=temp;
        }
        //System.out.print(min+","+max);
        for(int i=min;i<max;++i)
            res+=diff[i];
        return res;
    }
    public static void main(String[] st)
    {
        int[] elem={1,-2,6};
        System.out.println("largest difference: "+maxDiff(elem));
    }
}

- kandarp2516 March 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The top rated answer is incorrect. The question does not state that the array is sorted etc. Here's the correct solution:

public static int maxDiff(int[] arr)
        {
            int maxElement = arr[0];
            int minElementAfterMaxElement = int.MaxValue;
            int maxDrop = -1;

            for (int i = 1; i < arr.Length; i++)
            {
                if (arr[i] > maxElement)
                {
                    maxElement = arr[i];
                    minElementAfterMaxElement = int.MaxValue;
                }
                else
                {

                    minElementAfterMaxElement = Math.Min(arr[i], minElementAfterMaxElement);
                    maxDrop = maxElement - minElementAfterMaxElement;
                }
            }

            return maxDrop;
        }

- EefiasFira November 14, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MaximumDifference {

    public static void main(String args[]){
        int[] a = { 4, 1, 20, 5, 59, 10};
        int l = a.length;

        int j = l - 1;
        int diff = 0;
        int i = j -1;
        while (i>=0)
        {
            if (a[j] > a[i]){
               if ((a[j]-a[i]) > diff){
                   diff = a[j] - a[i];
               }
               i--;
            }
            else{
                j=i;
                i--;
            }
        }
        System.out.println(diff);

    }
}

- Vignesh March 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I'm not sure of an O(n) solution, but I'm pretty sure you can do this in O(nlogn) using modified merge sort.

On each merge you do in merge sort, you have a left subarray (L) and a right subarray (R).

Assume that L has a candidate difference (CDL) and R has a candidate difference (CDR). On the merge, find the min from L and the max from R to get a candidate difference between L and R (CDLR). Now, for the array that L and R merge into, we will take Max(CDL, CDR, and CDLR) to be the candidate difference for the merged array.

Recursively, the answer bubbles all the way to the top.

- Skor January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1. Iterate through all elements and find MIN and MAX elements of array.
Thus, result = max - min.
2. Every time, when we change MIN , we save previous value as second element.

- Ann January 28, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This is also not correct for the same reason as the previous post if the maximum has a lower array index than the minimum.

- The great white January 28, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It is given in problem statement itself that the second number comes after the first which means that max would always have higher array index then the min

- bakwas January 30, 2015 | Flag


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