Facebook Interview Question for Software Developers

• 6

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 +/- (A[ A.length -1 ] + A.length - A)/2

.

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

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.

[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.

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

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

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

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

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

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

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.

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

how did you come up with this solution?

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}

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

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

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

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

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

difference=A[length-1]-A+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

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

}

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

I feel like this is not possible

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

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.

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?

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

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

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

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).

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

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.

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

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

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

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

thx dud..i can figure the solution

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.

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

}

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

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.

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

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.

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 + x.length -1 = 1+ 9 -1 = 9
val absMin = x - (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

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

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

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

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

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 || \$a1 == \$s[\$n - 1])
return 'No local max or min exists';
return (\$a1 > \$s ? '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) * (\$s - \$s)) / 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 - \$s + \$n * (\$s - \$s)) + (abs((2 * \$s - \$s + \$n * (\$s - \$s)) - \$s[\$n - 1]) / 2 * (\$s - \$s));
}
}

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

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.

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

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

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

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

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 > A)
{
if ((A - (len-1)) == A[len-1])
{
cout<< "No local min or max exist"<<endl;
return;
}
int min = (A-(len-1)+ A[len-1])/2;
cout << "Local min : "<< min <<endl;

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

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 == length - 1

Let's say for A = [3, 4, 5] and B = [3, 4, 3], min/max happened at A (A[length-1-1). A - B 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.

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 == length - 1

Let's say for A = [3, 4, 5] and B = [3, 4, 3], min/max happened at A (A[length-1-1). A - B 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.

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.

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

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

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.

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

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

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

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.