Interview Question

Intern Interview

-Los Angeles, CA

Google

Find the max value in an array. The array is "semi-sorted". Here is an example: { 1 3 4 7 9 10 12 13 12 6 3 } As you can see, the array increases and then decreases at one point (13).

AnswerAdd Tags

Interview Answers

19 Answers

4

Brute force solution can be ofcourse O(N). But we can make it better: mid = (start + end )/2 if mid > mid + 1 && mid > mid - 1 return mid else if mid mid -1 search mid -> end else if mid > mid + 1 && mid mid

Mo on

3

It is necessary to check two elements on each side of our middle element to find out where the array increases , where decreases, and where the peak is. And only then we can guarantee something about our max.

Sonya on

3

private static int recFindPeak(int[] a, int start, int end) { if(start == end) return a[start]; int mid = (start+end)/2; if((a[mid] > a[mid+1])&&(a[mid] > a[mid-1])) return a[mid]; else if(a[mid] > a[mid-1]) return recFindPeak(a, mid+1, end); else return recFindPeak(a, start, mid-1); }

GReeky on

2

In your test case, I see that the numbers increase, decrease, increases, decreases and so on. I thought the question says the list is semi sorted. So my program assumes that the numbers increase and then decrease. We need to find the peak. At least that is my understanding.

Mo on

2

No, your O(logn)-approach doesn't work. Try this: 1 5 8 10 9 8 7 6 5 4

Sonya on

3

The previous O(log n) approach doesn't handle arrays of odd length. int findPeak(int * array, int start, int end) { if ((start == end) || ((start == (end - 1)) && (array[start] > array[end]))) return array[start]; if ((start == (end - 1)) && (array[start] > array[end])) return array[end]; int middle = floor((start + end) / 2); if (array[middle] > array[start]) return (findPeak(array, middle, end)); else return (findPeak(array, start, middle)); } Remember to include math.h for the floor function.

Varsha on

0

It seems, that it doesn't matter if the array is of odd or even length(btw, my example is not odd :)). This approach doesn't work when the max element is in the first half of your array and the middle element is greater than the first one. We cannot guarantee that if the middle element is greater than the first, our array increases monotonically from x[1] to x[middle] and we should search the max element in the range from middle to end.

Sonya on

1

The maximum is obviously just the inflection point in the list... some of the posted solutions here are absurdly complex for this.

nilkn on

0

My codes: int findPeak(vector num) { if (num.empty()) return 0; int lower = 0; int upper = num.size()-1; while (lower num[mid+1]) return num[mid]; else if (num[mid-1] < num[mid] && num[mid] < num[mid+1]) lower = mid+1; else upper = mid-1; } }

brady on

0

1. Walk from begin to mid comparing a[i] a[j] and stop decrementing j when this condition fails. 3. If a[i] < a[j], then return a[j], else return a[i].

Anonymous on

0

1) find the pivot of the highest number of the semi sorted list ,using binary search on the array.(logn) 2) From their do the linear serach for finding max ,also compare with last element of the semi sorted list.

Anonymous on

0

strange, some lines missing for above solution: shouldn't be one line : if((end-start)==1 && arr[end] arr[start]) but: if((end-start)==1 && arr[end]<=arr[start]) { return arr[start]; }

Anonymous on

0

def maxInSemiSortedArray(inputData): low, high = 0, len(inputData) -1 while(low inputData[mid-1] and inputData[mid] > inputData[mid+1]: return inputData[mid] elif inputData[mid] < inputData[mid+1]: low = mid + 1 else: high = mid -1

Simple Python solution on

0

def maxInSemiSortedArray(inputData): low, high = 0, len(inputData) -1 while(low inputData[mid-1] and inputData[mid] > inputData[mid+1]: return inputData[mid] elif inputData[mid] < inputData[mid+1]: low = mid + 1 else: high = mid -1

Simple Python solution on

0

public static Integer getMax(int[] arr){ int max = Integer.MIN_VALUE; int start = 0; int end = arr.length -1; while(start max){ max = arr[mid]; System.out.println("max :"+max); } if( arr[mid+1] > arr[mid]){ start = mid+1; }else if( arr[mid] > arr[mid-1]){ System.out.println("arr[mid]"+arr[mid]+"arr[mid-1] :"+arr[mid-1]); return arr[mid]; } else if(arr[mid] < arr [mid-1]){ end = mid -1; } } System.out.println("Max :"+max); return max; } public static void main(String[] args){ //int[] arr = new int[]{1,3,5,4,2}; int[] arr = new int[]{1,2,4,6,7,8,5,3}; System.out.println("Max is:"+getMax(arr)); }

Shri on

0

some codes are messed up above. Here is the clean code. public static Integer getMax(int[] arr){ int max = Integer.MIN_VALUE; int start = 0; int end = arr.length -1; while(start max){ max = arr[mid]; System.out.println("max :"+max); } if( arr[mid+1] > arr[mid]){ start = mid+1; }else if( arr[mid] > arr[mid-1]){ System.out.println("arr[mid]"+arr[mid]+"arr[mid-1] :"+arr[mid-1]); return arr[mid]; } else if(arr[mid] < arr [mid-1]){ end = mid -1; } } System.out.println("Max :"+max); return max; } public static void main(String[] args){ //int[] arr = new int[]{1,3,5,4,2}; int[] arr = new int[]{1,2,4,6,7,8,5,3}; System.out.println("Max is:"+getMax(arr)); }

Shri on

2

O(logn) approach: int max_value_in_semisorted_array(int* arr, int start, int end) { if (start == end) return arr[start]; int middle = (end + start) / 2; if (arr[middle] > arr[start]) return max_value_in_semisorted_array(arr, middle, end); else return max_value_in_semisorted_array(arr, start, middle); }

Dídac Pérez on

0

@Mo - This won't be work for an array where the max element is hidden in the first / second half of the main array. Eg: {1,3,9,1,-2,6,2,2,5,-1}

Dee on

1

Simply walk the array to find the max in O(n) time. Compare the current max to the next element all the way until the end of the array.

Anonymous on

Add Answers or Comments

To comment on this, Sign In or Sign Up.