Google Interview Question
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.
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.
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.
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.
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.
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;
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 ?
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;
}
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.
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
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)
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)
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]
<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>
easy question if you know math well~
Similar to the intermediate value theorem in real analysis.
Good question~
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.
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);
}
}
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]
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.
import java.util.*;
public class LocalMinima
{
public static void main(String[] args)
{
int numberOfElements = Integer.parseInt(args[0]);
int[] array = new int[numberOfElements];
Scanner scanner = new Scanner(System.in);
for(int index =0; index < numberOfElements; index++)
{
array[index] = scanner.nextInt();
}
System.out.println("Local Maxima is " + FindLocalMimimum(array,0,array.length -1));
}
private static int FindLocalMimimum(int[] array,int low,int high)
{
//int high = array.length - 1;
//int low = 0;
int mid;
int localMinima = -1;
//while(low <= high)
{
if((high - low) <=2) return -1;
mid = (low + high)/2;
System.out.println("Mid " + mid);
if(mid <= 0) return -1;
if(mid >= (array.length - 1)) return -1;
if((array[mid] >= array[mid -1] &&
(array[mid + 1] >= array[mid])))
return array[mid];
//if(array[mid + 1] <= array[mid])
{
localMinima = FindLocalMimimum(array,mid,high);
}
//if(array[mid - 1] <= array[mid])
{
if(localMinima > -1) return localMinima;
return FindLocalMimimum(array,low,mid);
}
}
//return -1;
}
}
The question just asks for one local minimum.
- Anonymous March 25, 2011mid=(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)