Facebook Interview Question for Software Developers


Country: United States
Interview Type: Phone Interview




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

It can be done in constant time. There should be one more condition in the question that there should be only one local maximum and one local minimum.
Given array A, local maxima or local minima is

A[0] +/- (A[ A.length -1 ] + A.length - A[0])/2

.

- Imran Khan March 31, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how does this handle the case

[1,0,1,2,3,2,1,2,1,2]

from my calculations it comes out as

1 +/- (2 + 10 - 1)/2 => 1 +/- 5.5

it seems your solution can locate the theoretical maximum and minimums possible (you are calculating the max distance it can continue in a direction while still being able to hold to the rules of the array) but it isn't effective for locating the real local max or min.

Another contradiction case is

[1,2,1,2,3,2,3,4,3,2]

Use of long arrays which include staggering between two numbers for extended portions can screw this one up.

- Javeed March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

The array can either contain local max or local min, not both. This was also a condition

- xyz March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works for the condition if only one local maxima/minima exists.
We also can check whether there has more than one local maxima/minima in a range [u,v].

- ninhnnsoc March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@xyz: the condition you just added is important.
O(1) solution by Imran Khan works now.

- ninhnnsoc March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

It's interesting to solve this for the case where there can be any number of local minima / maxima (find any one). In this case, O(log n) is the best achievable complexity, through a modified binary search.

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

how did you come up with this solution?

- Marcello Ghali March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Almost... but it fails on this array

{6,7,6,7,6,7,6,7,6,5}

- Alex March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@javed, @Alex , then examples which you gave have multiple local maximum/minimum. There should be continuous increment/decrement.

- Imran Khan March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Imran Khan, can you explain your solution or point us to a good resource?

- Marcello Ghali April 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

difference=A[length-1]-A[0]+1
A[0+difference] or A[length-1-difference] will be local minima or maxima. I am not sure. But it worked for all my tests. I have written code in separate answer below

- kandarp2516 April 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

My solution builds on the hypothesis from JosephB (only 1 local min OR local max)

f : first
l : last
n : number of items in the array
a : the array itself

The local min / max can be computed in O(1) with the following formulas:

MAX= ( ( (f + (n - 1)) - l ) / 2 ) + l
MIN= ( ( (f - (n - 1)) - l ) / 2 ) + l;

In order to determine whether we look for local min or max :
( (l + f) / 2 ) < a[((n-1) / 2)] <--- if true, local max otherwise local min

With the above, the java solution would be (i took the liberty of using sample input from JosephB as well):

import java.io.*;
import java.util.*;

/*
* To execute Java, please define "static void main" on a class
* named Solution.
*
* If you need more classes, simply define them inline.
*/

class Solution {

private static int[] A = new int[]
{
1,2,3,4,5,4,3,2,1 //-> Local max is 5
// 3,4,5,6,7,8,7,6,5 //-> Local max is 8
// 5,6,7,8,7,6,5,4,3 //-> Local max is 8
// 1,2,3,4,5 //-> No local max or min exists
// 5,4,3,2,1 //-> No local max or min exists
// 9,8,7,6,7,8 //-> Local min is 6
// 3,2,1,2,3,4,5,6,7 //-> Local min is 1
// 7,6,5,4,3,4,5,6,7 //-> Local min is 3
//// 1,2,1,2,1,2,1 //-> Multiple maxima/minima exist
//// 1,2,1,2,3,2,1,2,1,2 //-> Multiple maxima/minima exist
// 1,2,3,4,3,2,1,0,-1,-2 //-> Local max is 4
// 3,2,1,0,-1,-2,-1,0,1 //-> Local min is -2

};

public static void main(String[] args) {

Solution solution = new Solution();
solution.findLocalMinMax(A);

}

// find local Min/Max
public int findLocalMinMax(int[] a) {
if (a.length < 3) {
System.out.println("Invalid input");
return Integer.MIN_VALUE;
}

int n = a.length;
int first = a[0];
int last = a[n-1];

int median = (last + first) / 2;
int mediumIndex = (n-1) / 2;
//System.out.println("median: " + median);
//System.out.println("med value: " + a[mediumIndex]);

// Check no min/max due to asc only
if ((first + (n - 1)) == last) {
System.out.println("No local max / min - Ascending");
return Integer.MIN_VALUE;
}

// Check no min/max due to desc only
if ((first - (n - 1)) == last) {
System.out.println("No local max / min - Descending");
return Integer.MIN_VALUE;
}

// Check which edge is bigger and its previous / next to determine max / min
int result;
String type;
if (median < a[mediumIndex] ) {
result = findLocalMax(first, last, n);
type = "Local max";
} else {
result = findLocalMin(first, last, n);
type = "Local min";
}

System.out.println(type + ": " + result);

return result;
}

// find local max
private int findLocalMax(int f, int l, int n) {
int result = ( ( (f + (n - 1)) - l ) / 2 ) + l;
return result;
}

// find local min
private int findLocalMin(int f, int l, int n) {
int result = ( ( (f - (n - 1)) - l ) / 2 ) + l;
return result;
}

}

- teo2403 October 13, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I feel like this is not possible

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

It's impossible in less than O(log n) unless you're guaranteed there's only one local maximum / minimum. This condition was originally omitted from the problem posting by the OP.

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

I guess you mean O(1) space? How can we do this in O(1) time?

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

Yes, I agree O(1) seems tough, but maybe we are missing something. You say "the" local min/max, but I assume there can actually be more than one. IF there at most one, then we can quickly determine whether there are 0, then check to two possible locations for our single stationary point if one exists (easy to work out based on length of the array and |final-start|).

The O(log n) solution is a variant of binary search. First we note that there is a min/max (or "stationary point") in the range a[x] to a[y] iff. |a[x]-a[y]| < |x-y|. So, we can look at the middle element, a[m]. First we check if it's a stationary point. If not, we check whether there is a stationary point in either range 0 to m and m to L. We recurse on whichever range has a stationary point (if both do, pick either).

But I am not sure if the precise value of |a[x]-a[y]| can tell us, not only if there is a stationary point, but how many, where to look etc. If you can find more information, maybe something quicker is possible - constant time, though? :S

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

I can see O(1) time iff there is a strictly increasing sequence followed by a strictly decreasing sequence as in your examples. Otherwise I'd say it's impossible

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

I think that xyz understood wrong the question, If the interview said something is for a reason, I think the sequeance is first increasing and then decreasing (or viceverse), with this terms there is a solution in O(1).

- Kent March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mind sharing that solution then? Using a 2-pointer approach I can get the min OR max for any sequence in O(n) time with O(1) additional space usage. Not sure how you would do that in constant time.

- dph April 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

class GetMaximaMinima
{
    static int getIt(int[] arr)
    {
        int diff=Math.abs(arr[arr.length-1]-arr[0]);
        if(diff+1<arr.length)
        {
            int minus=arr.length-2-diff,plus=diff+1;
            if(arr[minus]>arr[minus-1] && arr[minus]>arr[minus+1])
                return arr[minus];
            if(arr[minus]<arr[minus-1] && arr[minus]<arr[minus+1])
                return arr[minus];
            if(arr[plus]>arr[plus-1] && arr[plus]>arr[plus+1])
                return arr[plus];
            if(arr[plus]<arr[plus-1] && arr[plus]<arr[plus+1])
                return arr[plus];
        }
        return Integer.MAX_VALUE;
    }
    public static void main(String[] st)
    {
        int[] arr={1,2,3,4,5,4};
        System.out.println("local minima/maxima:"+getIt(arr));
    }
}

- kandarp2516 April 01, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about [1, 2, 3, 4, 3, 2, 1]? Your solution doesn't seem to return a maximum.

- dph April 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

thx dud..i can figure the solution

- ano April 08, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I am pretty certain that the interviewer would have meant O(1) space, and not time. Otherwise, as others have already pointed out, it seems to be impossible in constant time, without any preprocessing.

- Code Hero April 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In Java:

public static void getMaximum() {
		
		Integer[] array = new Integer[]{0,1,2,3,4,3,2,1,0};
		
		Arrays.sort(array);
		
		System.out.println("Maximun: " + array[array.length -1]);
		
		
	}

- manuel April 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That provides the maximum, however the challenge is to locate a solution in O(1) time, which means that sorting or traversing all elements is not permitted.

- JosephB May 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That provides the maximum, however the challenge is to locate a solution in O(1) time, which means that sorting or traversing all elements is not permitted.

- JosephB May 23, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

val x :Array[Int] = {1,2,3,4,5,4,3,2,1}

val absMax = x[0] + x.length -1 = 1+ 9 -1 = 9
val absMin = x[0] - (x.length -1) = 1 -9 +1 = -7

val numberOfPluses = (absMax - x[x.length -1])/2 = (9 - 1)/2 = 4
val numberOfMinuses = x.length -1 - numberOfMinuses = 9 -1 - 4 = 4

val localMax = absMax - numberOfMinuses = 9 - 4 = 5

val localMin = absMin + 2*numberOfPluses = -7 + 8 = 1

- chavdar.chernashki May 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

val localMin = absMin + numberOfPluses = -7 + 4 = -3

- chavdar.chernashki May 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

bool isLocal(int A[], int i)
{
	int x = A[i - 1] - A[i], y = A[i + 1] - A[i];

	return x >> 31 == y >> 31;
}

int findLocalMinOrMax(int A[], int n)
{
	assert(A != NULL && n > 0);

	int differ = abs(A[n - 1] - A[0]);

	if (differ >= n) throw logic_error("invalid input");

	if (differ == n - 1) throw logic_error("there is no local min or max");

	int offset = (n - 1 - differ) >> 1;

	return isLocal(A, offset) ?  A[offset] : A[n - 1 - offset];
}

- malinbupt May 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I came up with two approaches/formulas to solve this problem, but first a couple clarifications; from the wording "Find the local max OR min" we can infer that there is only a single min or max, otherwise the problem would have said minima or maxima (plural form), also the "OR" states that there can be either one max or one min, but not both. It is not possible to locate multiple max/min in O(1) time. We also know from the "local" wording and the clarification that the max/min cannot be edge elements. Now with these conditions it is possible to solve this problem in O(1) time by using mathematical formulas.

Taking all conditions into consideration, the sequence of numbers must always consecutively increase, and then at some point (but only once) change direction to then consecutively decrease or vise versa. With that said, here are some valid, and invalid input examples:

Valid input:
    12345432 (max = 5)
    56789876543 (max = 9)
    7656789 (min = 5)
    98765456 (min = 4)

Invalid input:
    123456 (the max/min is at an edge)
    121212121 (contains 4 maxima and 3 minima)
    121232121 (contains 2 local maxima, 1 global maxima and 2 minima)
    54345454 (contains 1 global minima, 1 local minima and 2 maxima)

Legend:
    f = the first number in the list (compared with last number and total numbers to find min/max)
    l = the last number in the list (compared with first number and total numbers to find min/max)
    n = the total/count of numbers in the list (needed to know the highest/lowest possible number)
    s = the second number in the list (needed to determine increasing/decreasing trend, meaning that we are looking for the max/min)
    a = the answer, which is either the local max or min (supporting input with only a single min or single max)

FORMULA #1:

This works by determining the highest/lowest possible max/min, and then subtracting from that based on the first and last numbers, which limit the max/min. The end result is a calculated max or min. Note that we use the first and second numbers to determine whether the numbers are increasing (looking for a max) or decreasing (looking for a min).

a = (2f - s + n(s - f)) + (|((2f - s + n(s - f)) - l)| / 2(f - s))

Note: Number enclosed within || means absolute value, example: |5| = |-5| = 5

(For a coded example see function "findCalculated")

This only looks complicated because it returns valid results for either a max or min, but if you separate them you would simply get:

Solve for max:
    e = f + n - 1
    a = e - (e - l) / 2

Solve for min:
    e = f - n + 1
    a = e + (e - l) / 2

Note: "e" means "extreme", it represents the highest/lowest possible max/min

FORMULA #2

This formula works differently and is a bit simpler, rather than calculating the logical max/min, it returns the expected index within the list, from which the max/min is to be read from. This formula also supports finding either a max or min.

a = |(n + (l - f)(s - f)) / 2|

(For a coded example see function "findPositional")

FINAL NOTES

There is a deficiency in both formulas, neither alerts of a problem when the max/min is an edge case, additionally they will both return incorrect results if the input sequence contains multiple maxima and/or minima. The first problem is easily solved in code by verifying that the result is not equal to either of the edges. The second problem is a bit trickier, however note that due to the behavior of these two formulas, they will both return different results given input with multiple minima/maxima; in my example below I actually use both of my formulas, and if they don't produce the same result then I know that we have invalid input with multiple maxima/minima.

Here is the code/verification using PHP:

<?php

class FindMaxMin
{
    // Collects the results, and filters for common problems due to invalid input
    // Input: $s = the numerical sequence for which we seek the local max or min
    public static function find($s)
    {
        $n = count($s);
        $a1 = self::findPositional($s, $n);
        $a2 = self::findCalculated($s, $n);
        if ($a1 != $a2)
            return 'Multiple maxima/minima exist';
        if ($a1 == $s[0] || $a1 == $s[$n - 1])
            return 'No local max or min exists';
        return ($a1 > $s[0] ? 'Local max is ' : 'Local min is ') . $a1;
    }

    // Finds the local max/min by calculated and querying its expected index within the list
    // Input: $s = the numerical sequence, $n = the length of the sequence
    private static function findPositional($s, $n)
    {
        // Formula: a = |(n + (l - f)(s - f)) / 2|
        return $s[abs(($n + ($s[$n - 1] - $s[0]) * ($s[1] - $s[0])) / 2)];
    }

    // Finds the local max/min by calculating the highest/lowest possible max/min
    // Input: $s = the numerical sequence, $n = the length of the sequence
    private static function findCalculated($s, $n)
    {
        // Formula: a = (2f - s + n(s - f)) + (|((2f - s + n(s - f)) - l)| / 2(f - s))
        return (2 * $s[0] - $s[1] + $n * ($s[1] - $s[0])) + (abs((2 * $s[0] - $s[1] + $n * ($s[1] - $s[0])) - $s[$n - 1]) / 2 * ($s[0] - $s[1]));
    }
}

function main () {
    // Generate test input
    $input = [
        [1, 2, 3, 4, 5, 4, 3, 2, 1],
        [3, 4, 5, 6, 7, 8, 7, 6, 5],
        [5, 6, 7, 8, 7, 6, 5, 4, 3],
        [1, 2, 3, 4, 5],
        [5, 4, 3, 2, 1],
        [9, 8, 7, 6, 7, 8],
        [3, 2, 1, 2, 3, 4, 5, 6, 7],
        [7, 6, 5, 4, 3, 4, 5, 6, 7],
        [1, 2, 1, 2, 1, 2, 1],
        [1, 2, 1, 2, 3, 2, 1, 2, 1, 2],
        [1, 2, 3, 4, 3, 2, 1, 0, -1, -2],
        [3, 2, 1, 0, -1, -2, -1, 0, 1]
    ];

    // Process input
    foreach ($input as $sequence)
        echo implode($sequence, ','), ' -> ', FindMaxMin::find($sequence), "\n";
}

main();

Here is the output:

1,2,3,4,5,4,3,2,1 -> Local max is 5
3,4,5,6,7,8,7,6,5 -> Local max is 8
5,6,7,8,7,6,5,4,3 -> Local max is 8
1,2,3,4,5 -> No local max or min exists
5,4,3,2,1 -> No local max or min exists
9,8,7,6,7,8 -> Local min is 6
3,2,1,2,3,4,5,6,7 -> Local min is 1
7,6,5,4,3,4,5,6,7 -> Local min is 3
1,2,1,2,1,2,1 -> Multiple maxima/minima exist
1,2,1,2,3,2,1,2,1,2 -> Multiple maxima/minima exist
1,2,3,4,3,2,1,0,-1,-2 -> Local max is 4
3,2,1,0,-1,-2,-1,0,1 -> Local min is -2

- JosephB May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I don't understand why hasn't anyone considered using Hash tables.

- Hopper June 11, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Because you would have to hash every number into the table first, taking O(n) time.

- Aaron September 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Because you would have to hash every element into the table, which would take O(n) time.

- Aaron September 13, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the C++ version of solution

#include<iostream>
using namespace std;

void find_minmax(int *A, int len)
{
  if (A[0] > A[1])
  {
    if ((A[0] - (len-1)) == A[len-1])
    {
      cout<< "No local min or max exist"<<endl;
      return;
    }
    int min = (A[0]-(len-1)+ A[len-1])/2;
    cout << "Local min : "<< min <<endl;

  } else {
    if ((A[0] + (len-1)) == A[len-1])
    {
      cout<<"No local min or max exists"<<endl;
      return;
    } else {
      int max = (A[0] + (len-1) + A[len-1])/2;
      cout <<"Local max : " << max << endl;
    }
  }
}

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

This is to explain the equation. It took me a while to understand the equation, and thanks @ Imran Khan for hinting this can be calculated and leading to O(1) running time.

If the array wouldn't have any min or max, then the following equation should meet (as @hankm2004 shows above):
A[length-1] - A[0] == length - 1

Let's say for A = [3, 4, 5] and B = [3, 4, 3], min/max happened at A[1] (A[length-1-1). A[2] - B[2] is 2 because A and B has only ONE element different. This can finalized due to "increment by 1 or decrement by 1" only. Hence, if the diff needs to be divided by 2. If there's no diff, of course, no such min/max exists.

- Happy Minions January 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is to explain the equation. It took me a while to understand the equation, and thanks @ Imran Khan for hinting this can be calculated and leading to O(1) running time.

If the array wouldn't have any min or max, then the following equation should meet (as @hankm2004 shows above):
A[length-1] - A[0] == length - 1

Let's say for A = [3, 4, 5] and B = [3, 4, 3], min/max happened at A[1] (A[length-1-1). A[2] - B[2] is 2 because A and B has only ONE element different. This can finalized due to "increment by 1 or decrement by 1" only. Hence, if the diff needs to be divided by 2. If there's no diff, of course, no such min/max exists.

- Happy Minions January 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

save the edges of the array and insert the entire array into a min-max heap.
findmin and findmax takes constant time. Check to make sure that the edges are not equal to what is returned by the search functions.

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

But insertion is logn for each element, so nlogn in total....

- SK March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

There is nothing in the question that indicates the insertion complexity... only search complexity.

- Alex March 31, 2015 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

As far as I know, without being able to use at least O(n) preprocessing, it isn't possible to meet these requirements. If the O(1) refers to final data assessment (post processed, i.e. put into a heap) then yes it is easily done (with a heap). If there is a way to do it in O(1) without pre-processing, I'd love to know how

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

Agreed. This can definitely be done in O(logn), but I see no way of doing this in O(1) time.

- Skor March 31, 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