Google Interview Question

  • google-interview-questions
    1
    of 1 vote
    38
    Answers

    Suppose we are given an array A[1 .. n] with the special property that A[1] ≥ A[2] and
    A[n − 1] ≤ A[n]. We say that an element A[x] is a local minimum if it is less than or equal
    to both its neighbors, or more formally, if A[x − 1] ≥ A[x] and A[x] ≤ A[x + 1]. For example,
    there are five local minima in the following array:
    9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
    We can obviously find a local minimum in O(n) time by scanning through the array. Describe
    and analyze an algorithm that finds a local minimum in O(log n) time.

    - Anonymous on March 24, 2011 Report Duplicate | Flag
    Google Algorithm



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

The question just asks for one local minimum.
mid=(start+end)/2;
1. if(A[mid-1]>=A[mid] && A[mid+1]>=A[mid]) then A[mid] is a local minimum.
2. else if(A[mid-1]<=A[mid] && A[mid]<=A[mid+1]) end=mid, do recursive search.
3. else if(A[mid-1]>=A[mid] && A[mid]>=A[mid+1]) start=mid, do recursive search
it is O(logn)

- Anonymous on March 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

wont work.
e.g. 1,2,3,4,10,8,11
mid is 4 and as per your logic the search will reduce to 1st half. but the local minimum is 8.

- Tulley on March 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Dont know about the above logic , but Tulleys array is wrong. Read problem : a1> a2.

- Anonymous on March 25, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

You are right, Tulley gave a wrong example. Let's change the example to 2,1,3,4,10,8,11. Based on the logic, mid is 4, 3<4<10, then search the local minimum from the first half, 2,1,3,4. It will find 1 as the local minimum.
In this example there are 2 local minimum 1 and 8. The logic finds 1.

- Anonymous on March 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

apparently your approach is wrong. What if first half of the array is sorted in decreasing order, for example(in above example) 3,2,1,0,-1,8,11. Your code moves to left half [3,2,1,0] where there is no local minima. But the right half contains 1 minima [0,-1,8].

My basic understanding is that NO algorithm exists that can give O(log n) solution for this problem in O(log n). As the array is not sorted, no ordering of elements can be deduced from one comparision, unlike binary search in sorted array.

- LOL on March 28, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

LOL, in your example, 1>0>-1, it will move to the right half, not left half.

- Norman on October 09, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

This solution is correct and will work for all test cases.

- Epic_coder on October 28, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the most important thing there is if we can think the first element is the answer in the problem, like the sequence is 0 1, and 0 <= 1, but there is no element before 0, could we think 0 is the answer. If yes, then the algo given by the author is right, else it's wrong.

- remlostime on November 01, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

What if 6 3 5 4 8.

This program does not count if it is the local maximum. It do not fall
under any of the conditions.

- KK on April 02, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there is a local maximum you can go either left side or right side. It is guaranteed to have a local minimum.

int lo = 0, hi = n-1;
while (lo < hi - 1) {
int mid = lo + (hi - lo) / 2;
if (A[mid-1] >= A[mid] && A[mid] <= A[mid+1]) return mid;
else if (A[mid-1] <= A[mid] && A[mid] <= A[mid+1]) hi = mid;
else if (A[mid-1] >= A[mid] && A[mid] >= A[mid+1]) lo = mid;
else hi = mid;
}
return -1;

- zx on December 26, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

In this array: {9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9} I can count six local minimals.

value => position
7 => 1
1 => 4
4 => 8
3 => 10
3 => 11
6 => 14

Am I right ?

- m@}{ on March 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

yes ... you are right. The minimum of array will be one of the local minima and we have to return any of them. Can we find Min of an array in log(n) time??

- Anonymous on March 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

where this question asked? Google India or US?

- Anonymous on March 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

we can do it O(logn) time

- WgpShashank on March 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Do you mind to share?

- anon on March 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Seems WgpShashank DOES NOT know the answer himself :D

- anonymous on March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findLocalMinima (int* pGivenArray, int* localMinArray, int* minimaCount, int start, int end)
{
	int mid;
	if (end-start >= 2)
	{
		mid = (end+start)/2;
		if ((pGivenArray [mid-1] >= pGivenArray [mid]) && 
			(pGivenArray [mid] <= pGivenArray [mid+1]))
		{
			localMinArray [++(*minimaCount)] = pGivenArray [mid];
		}
		findLocalMinima (pGivenArray, localMinArray, minimaCount, start, mid);
		findLocalMinima (pGivenArray, localMinArray, minimaCount, mid, end);
	}
}


int main ()
{
	int givenArray [] = {9,1,11,12,16,13,14,15,16,17,18,19,20,25,2,22};
	int minimaArray [10] = {0};
	int minimaCount = -1, i;
	findLocalMinima (givenArray,minimaArray,&minimaCount,0,15);
	while(minimaCount >= 0)
	{
		printf ("[%d]", minimaArray[minimaCount--]);
	}
	printf ("\n");
	return 0;
}

- Tulley on March 24, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This recursion solution is doing better than scanning the array. You will still need to check every elements in the array. Still O(n), not O(lgn)

Maybe I'm stupid, but I don't think there is any possible way you can find local min in O(lgn) without an auxilary data structure and a preprocessing on the input array.

- Anonymous on March 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Anonymous: u r correct. Its not O(logn). i also realized the same after writing this solution.

- Tulley on March 24, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I did not understand the question. They say that A[1]>=A[2] and A[n-1]<=A[n]. In this array first condition is satisfied but not the second one.
9 7 7 2 1 3 7 5 4 7 3 3 4 8 6 9
When they say A[n-1]<=A[n] shouldn't it be in increasing order except the first element?

- Anonymous on March 25, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think this question is either wrong, or having missing conditions. the following array does not have a local minimum. yet, it satisfies the conditions given in the question:

9, 10, 11, 12, 13, 12, 11, 9

- loser on March 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

what happened to A[n-1] <= A[n]?

- Anonymous on March 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this:
findLocalMin(start, end, array)
if start > end return None
mid = array[(start+end)/2]; st = array[start]; en = array[end];
if mid > both st and en: findLocalMin(start, mid-1, array) or findLocalMin(mid+1, end, array) # we have at least two local minima
if start > mid > end findLocalMin(mid+1, end, array) #
if end > mind > start findLocalMin(start,mid-1, array)
if mid < both:
if mid < array[mid+1] and array[mid-1] return mid
if array[mid-1] > mid > array[mid+1] findLocalMin(mid+1,end,array)
if array[mid+1] > mid > array[mid-1] findLocalMin(start,mid-1,array)

- Anonymous on March 27, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

the above logic was kinda buggy, but the idea is the same. Here is working Python code for the O(lgn) solution:

def findLocalMin(start, end, array):
	if start > end:
		return None
			
	m = (start+end) / 2
	mid = array[m]
	st = array[start]
	en = array[end]

	print "array:" , array[start:end + 1] # to trace what's happening
	
	after = array[m+1]
	before = array[m-1]
	
	if mid <= before and mid <= after: # found local minimum
		return mid
		
	if before >= mid and mid >= after: # V-shape on right
		return findLocalMin(m, end, array)
		
	if after >= mid and mid >= before: # V-shape on left
		return findLocalMin(start,m,array)
	
	if before <= mid and after <= mid: # at least two local minima, choose one
		return findLocalMin(m,end,array)

if __name__ == "__main__":
	#a = [9,7,7,2,1,2,7,5,4,7,3,4,4,8,6,9]
	a = [2,1,3,4,10,8,11]
	print findLocalMin(0, len(a) - 1, a)

- Babak on March 27, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Seems ur logic is wrong, indeed. Check out this example:

3, -5, 1, 0, -3, -2, -1

Your search moves to right as before >= mid and mid >= after. But no minima is there. But, one in right half exist there [3,-5,1]

- anon on March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

oh... i meant left half with respect to middle element 0.

- anon on March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

sorry, i did mistake. your approach seems correct to me now. however, i believe we can relax the conditions in your code as below:

if mid >= after
    return findLocalMin(m+1, end, array)
if mid >= before
    return findLocalMin(start,m-1,array)

Pls verify if that is correct. Thanks.

- anon on March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

<pre lang="" line="1" title="CodeMonkey77119" class="run-this">/* The class name doesn't have to be Main, as long as the class is not public. */
class Main
{

public int getOneLocalMinimum(int lowIndex, int highIndex) {
if (lowIndex > highIndex) {
return -1;
}
if (lowIndex == highIndex) {
return lowIndex;
}
if (lowIndex + 1 == highIndex) {
if (elements[lowIndex] < elements[highIndex]) {
return lowIndex;
}
return highIndex;
}
int midIndex = (lowIndex + highIndex) / 2;
if ((elements[midIndex] <= elements[midIndex - 1])
&& (elements[midIndex] <= elements[midIndex + 1])) {
return midIndex;
}
if (elements[midIndex] >= elements[midIndex + 1]) {
return getOneLocalMinimum(midIndex, highIndex);
} else {
return getOneLocalMinimum(lowIndex, midIndex);
}
}
public static void main (String[] args)
{
int arr[] = { 1, 0, -1, 0, 1, -2, 0 };
System.out.println(new LocalMinimum(arr).getOneLocalMinimum(0,
arr.length - 1));
}
}

</pre>

- Anonymous on March 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

easy question if you know math well~
Similar to the intermediate value theorem in real analysis.
Good question~

- Anonymous on March 30, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your smart solution for such easy problem, dude?

If you dare to challenge, post your answer (NOT code, the idea only). Otherwise, no need to spend your time typing here.

- anon on March 30, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

it is similar to binary search, you just need to modify it a little bit.

- Anonymous on April 03, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a[1]>=a[2] && a[n-1]<=a[n];
// it means there is a local minima between a[2] to a[n-1]
if(a[n/2]<=a[n/2+1])
//it means there is a local minima between a[n/2] ans a[2];
else there is a local minima between a[n/2+1] ans a[n]

now recursively solve it O(lg n) solution;

- pankaj on April 15, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To get results on O(log n), the list must be sorted, else no matter what we write the worst case scenario will be O(n).

- SAN on April 18, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

mid = sizeof(A)/2
recursive call

if(A[mid]>A[1]){
//becasue the value turn up, there will be a local min
find(A,0,mid) }
else{//
find(A[],mid,sizeof(A)-1)
}

- Anonymous on May 01, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int find(int[] arr, int start, int end){

int mid = (start + end)/2;
if(mid==0 || mid == arr.length-1) return -1;

if((arr[mid] <= arr[mid-1] && arr[mid] <= arr[mid + 1]) ||
(arr[mid] <= arr[mid-1] && arr[mid] <= arr[mid + 1]) )
return arr[mid];
//ascending
else if(arr[mid] > arr[mid]-1 && arr[mid] < arr[mid+1]){
return find(arr, start, mid);
}

//descending
else{
return find(arr, mid, end);
}
}

- Anonymous on August 28, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The logic for my code is as follows: Given the condition that A[0] >= A[1] and A[n-1] <= A[1], it is guaranteed that a minima exists. This is because for a minima to not exist, the sequence has to be strictly decreasing but the special property negates it. So a transition from strictly decreasing to increasing/remain same has to happen somewhere. Even if there are multiple minimas, each minima is a transition. The following code just looks for a transition. This can be done in O(log n) time.
Python Code:

#!/usr/bin/env python

A = [9,7,7,2,1,3,7,5,4,7,3,3,4,8,6,9]

low = 0
high = len(A) - 1
found = False
trans = 0

while not found:
    trans = (high + low)/2
    if A[trans - 1] >= A[trans]:
        low = trans
    if A[trans] <= A[trans+1]:
        high = trans
    if high == low:
        found = True

print 'Local minima', A[trans-1:trans+2]

- amh on September 16, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Splay trees can be helpful here. Though it does not give guaranteed insertion of O(logn) but the average case is O(logn). Also, if the array definitely has local minimun, then splay tree's insertion time will be definitely less than O(logn). A node of splay tree will contain a hashmap of value and it's count. Thus, for the local minimun, the count of the root of node will become 3 and that will be in O(logn) time.

- Sanchay on January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findMin(int i,int j,int arr[])
{
if(a[i]<a[j])
min=a[i];
else if(a[i+1]<a[j])
min=a[i+1];
if(j-i >=2)
{
findMin(i,(i+j)/2,arr);
findMin(((i+j)/2)+1,j,arr);
}

}

I donno whether this runs in O(log n)

- Ganesh R on November 07, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book walking you through 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