## Google Interview Question for Software Engineer / Developers

Country: Israel
Interview Type: In-Person

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

My solution is between O(n) and O(logn). Check my website for detail: allenlipeng47.com/PersonalPage/index/view/128/nkey

1. Every time, check the middle element. If middle element is both smaller than left and right element, return middle.
2. Or if left of middle element is both smaller than left and middle element, there must be a local min in left part. Go left part.
3. Or if right of middle element is both smaller than right and middle element, there must be a local min in right part. Go right part.
4. Despite the above 3 cases, we should both check left and right part.

``````package feb;

public class LocalMin {

public static void main(String[] args) {
int[] arr = { 11, 5, 12, 7, 4, 0, 6 };
int result = localMin(arr);
System.out.println(result);
}

public static int localMin(int[] arr) {
return localMinUtil(arr, 0, arr.length - 1);
}

/*
* Return local minimum in arr[left,...,right]
*/
private static int localMinUtil(int[] arr, int left, int right) {
if (right - left < 2) {
return -1;
}
int mid = (left + right) >> 1;
if (arr[mid] < arr[mid - 1] && arr[mid] < arr[mid + 1]) {
return mid;
}
if (arr[mid - 1] < arr[mid] && arr[mid - 1] < arr[left]) {
// There must be localMin in arr[left,...,mid]
return localMinUtil(arr, left, mid);
}
if (arr[mid + 1] < arr[mid] && arr[mid + 1] < arr[right]) {
// There must be localMin in arr[mid,...,right]
return localMinUtil(arr, mid, right);
}
int result = localMinUtil(arr, left, mid);
if (result != -1) {
return result;
}
return localMinUtil(arr, mid, right);
}

}``````

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

not working for

``int[] arr = { 1, 3, 3, 4, 5, 7, 8, 9 };``

it should return arr[0]=1, instead, it return -1.
because

``````if (right - left < 2) {
return -1;
}``````

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

``if (right - left < 2)``

``````// consider left and right edge
if (right - left == 1 && left==0) {
return arr[left]<arr[right]? arr[left]:-1;
}

if (right - left == 1 && right==arr.length-1) {
return arr[left]>arr[right]? arr[right]:-1;
}``````

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

For case 4, go either side will be ok.
so that the overall runtime is O(logn).

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

Binary search will not work since the array is not sorted. Going to the right half of the array for example might not yield a Local Minimum, whilst one may exist in the left half, which is totally missed. Try this array out: 6 2 4 2 8 6 4 1 9 5 4 3 2 2

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

Just realized that I missed the "distinct numbers" clause. My example above is not a valid one.

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

If there are multiple "local minimum", what should I do? Return all of them, or just one of them is enough?

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

Edited.

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

The trivial solution requires the complexity O(n), is it correct? What do you mean by "trivial solution"

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

Correct, edited again, sorry. I think "trivial solution" should be pretty obvious.

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

Hint: Use binary search.

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

Hello

The trivial one requires O(2n). If I gives a solution of O(n), is it OK?

Or I really need to provide a solution such as O(log(n))?

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

Here is my solution. Time complexity O(logn).

``````public class FIndLocalMinimum{
public int localMinimum(int [] arr, int left, int right){
if(left == right) return left;
if(right - left == 1) {
if(arr[left] < arr[right])
return left;
else
return right;
}
int mid = left + (right - left) / 2;
int result = -1;
if(arr[mid - 1] > arr[mid] && arr[mid + 1] > arr[mid])
result = mid;
else{
if(arr[mid - 1] < arr[mid])
result = localMinimum(arr, left, mid - 1);
else if(arr[mid + 1] < arr[mid])
result = localMinimum(arr, mid + 1, right);
}
return result;
}
public static void main(String [] args){
FIndLocalMinimum c = new FIndLocalMinimum();
int [] test = new int[7];
test[0] = 11;
test[1] = 5;
test[2] = 12;
test[3] = 7;
test[4] = 4;
test[5] = 0;
test[6] = 6;
System.out.println(c.localMinimum(test, 0, test.length - 1));
}
}``````

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

It doesn't work for { 1, 3, 2, 4, 5, 7, 8, 9 }

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

Considering the 2 edges are the option, your code works.

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

Binary search O(logn)

``````public static int findLocalMin(int[] arr){
return (arr.length == 0) ?
Integer.MIN_VALUE
:findLocalMin(arr, 0, arr.length-1);
}

private static int findLocalMin(int[] arr, int l , int r){
int m = l + (r-l)/2;
if (m == 0 || m == arr.length - 1){
return arr[m];
}
if (arr[m-1] > arr[m] && arr[m] < arr[m+1]){
return arr[m];
}
else if (arr[m] > arr[m+1]){
return findLocalMin(arr, m+1, r);
}
else{
return findLocalMin(arr , l , m-1);
}
}``````

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

Just tried with {11, 5} and your code is returning 11. I think you need to modify the recursion termination condition (m==0 doesn't return the correct result in this case).

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

You are program fails for the input
{30, 10, 20, 25, 14, 12, 8}

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

Another solution is we use index i to iterate arr from beginning to end. Difference is that we should try to compare arr[i] and arr[i+1]. If arr[i]<arr[i+1], then i should jump 2 to forward.
In this way, iteration could be done faster.

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

This is my solution:

``````import java.io.*;

public class FindLocalMinimum{
public static void main(String args[]){
// int [] array = {11, 5, 12, 7, 4, 0, 6};
// int [] array =  { 1, 3, 2, 4, 5, 7, 8, 9 };
int [] array = {6 ,2 ,4 ,2 ,8 ,6 ,4 ,1 ,9, 5, 4, 3, 2, 2};

System.out.println(findLocalMin(array, 0, array.length-1));
}

public static int findLocalMin(int[] array, int l, int r){
System.out.println("findLocalMin" + l + " " + r);
if(l > r){
return -1;
}

if(l == r){
if(l == 0 && l+1 < array.length){
return (array[l] < array[l+1] ? l : -1);
} else if(l == array.length-1){
return (array[l] < array[l-1] ? l : -1);
} else{
return (array[l] < array[l-1] && array[l] < array[l+1])? l : -1;
}
}

int mid = l + (r-l)/2;
System.out.println("mid:" + mid + " " + array[mid]);

if(mid == 0){
return array[mid] < array[mid+1] ? mid : -1;
} else if(mid == array.length-1){
return array[mid] < array[mid-1] ? mid: -1;
} else{
if(array[mid] < array[mid-1] && array[mid] < array[mid+1]){
return mid;
} else{
int leftIndex = findLocalMin(array, l, mid-1);

if(leftIndex == -1){
return findLocalMin(array, mid+1, r);
} else{
return leftIndex;
}
}
}
}
}``````

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

``````// Local minimum

// On high level binary search is used:
// 1) escape long streak of monotone values,
// 2) degenerates to gradient-descent on ranges with 2 or 3 elements

#include <iostream>

//int L = 8;
//int arr[] = { 1, 3, 2, 4, 5, 7, 8, 9 };
//int L = 7;
//int arr[] = { 30, 10, 20, 25, 14, 12, 8 };
int L = 3;
int arr[] = { 3, 2, 1 };

int indexMinimum(int a[], int al) {
int lb = 0;
int ub = al-1;
while (lb < ub) {
int mid = lb + (ub - lb + 1)/2;
if (a[lb] < a[mid]) {
ub = mid-1;
}
else {
lb = mid;
}
}
return lb;
}

int main() {
int index = indexMinimum(arr, L);
std::cout << "arr[" << index << "] = " << arr[index] << std::endl;
}``````

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

fails for {2, 0, 1, 3, 4}

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

``````#include<stdio.h>
#include<string.h>
#include<math.h>
int main()
{
int arr[10]={24,2,23,4,45,1,34,45,46,56};
int i;
for(i=1;i<=10;i=i+2)
{
if(arr[i]<arr[i-1]&&arr[i]<arr[i+1])
printf("\t%d",arr[i]);
}
printf("\n");
return 0;
}``````

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

Define two consecutive elements a[i], a[i+1] of the array to be a "falling edge" if a[i] > a[i+1] and a "rising edge" if a[i] < a[i+1]. The idea behind successfully applying binary search is that a local minimum is located inbetween a falling and a rising edge.

A rising edge at the beginning of the array is already a local minimum by definition. The same goes for a falling edge at the end of the array.

So for the general case, we can assume that the part of the array our binary search is looking at has a falling edge at its left (lower) and a rising edge at its right (upper) end. Now inspect two elements near the middle and check whether they are a falling or a rising edge. If falling, a local minimum must be located to the right of the middle. If rising, then to the left of the middle.

``````def lmin (a):
if a[0] < a[1]:
return 0
if a[-1] < a[-2]:
return len (a) - 1

# l points to a falling edge
# r points to a rising edge
l = 0
r = len (a) - 1

while r - l != 2:
m = (l + r) // 2
if a[m] < a[m + 1]:
r = m + 1
else:
l = m

return l + 1``````

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

// only needs to find the first local minimum and not all the local minimums present
public static void findLocalMin(int[] a, int low, int high) {

int mid = low + (high - low) / 2;
if (a[mid]!=a[0] && a[mid]!=a[a.length-1]) {
if (a[mid] < a[mid + 1] && a[mid] < a[mid - 1]) {
System.out.println("First Local minimum found is: " + a[mid] + " at position: " + mid);
} else if (a[mid - 1] < a[mid]) {
findLocalMin(a, low, mid);
} else {
findLocalMin(a, mid + 1, high);
}
} else {
if (a[low] < a[low+1]) {
System.out.println("Local minimum is the first element: " + a[low]);
} else if (a[high] < a[high-1]) {
System.out.println("Local mimimum is the last element of the array: " + a[high]);
} else {
System.out.println("no local minimums were found in the inputted array");
}
}

}

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.