## Facebook Interview Question

Software Developers**Country:**United States

**Interview Type:**Phone Interview

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.

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

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

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.

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

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;

}

}

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

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

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

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

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

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.

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

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

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

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

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.

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.

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.

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

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

.

- Imran Khan March 31, 2015