Microsoft Interview Question
Country: -
In this problam we can use the ternary search algorithm, because our function is unimodal
This is my simple python sol.
def solve(left, right, arr):
'''Finds max element in an array'''
if right - left <= 2:
t = arr[left:right + 1]
return left + t.index(max(t))
# devide arr to three segments [left, m1], [m1, m2], [m2, right]
m1 = (2 * left + right) / 3
m2 = (left + 2 * right) / 3
# values in arr forms unimodal function, so
# we can assume that if arr[m1] <= arr[m2]
# our max lies in [m1, right]
if arr[m1] <= arr[m2]:
return solve(m1, right, arr)
else:
return solve(left, m2, arr)
if __name__ == '__main__':
arr = [10, 12, 16, 17, 24, 27, 8, 6, 5, 4, 2]
print solve(0, len(arr), arr) + 1
Sorry for my bad English )
public static void main(String[] args) {
int arr[] = {10, 12, 16, 17, 24, 27, 8, 6, 5, 4, 2};
int last = java.lang.Integer.MIN_VALUE;
for (int i = 0; i < arr.length; i++)
{
if (arr[i] > last)
{
last = arr[i];
}
else
{
System.out.println("Value: " + arr[i] + " index: " + i );
break;
}
}
}
#include<stdio.h>
#include<conio.h>
int max(int a[],int,int);
int main()
{
int a[6]={12,13,14,10,6,1};
int len;
int i;
printf("%d",max(a,0,5));
getchar();
getchar();
return 0;
}
int max(int a[],int s,int e)
{
int mid=(s+e)/2;
if(s<=e){
if(a[s]>a[s+1])return a[s];
if(a[e]>a[e-1])return a[e];
if(a[mid]>a[mid+1] && a[mid]>a[mid-1])
{
return a[mid];
}
else if(a[s]>a[mid])
{
return max(a,s,mid-1);
}
else
{
return max(a,mid+1,e);
}}
else
return -1;
}
#include <stdio.h>
int findIncPos(int arr[], int left, int right)
{
int Lval;
int Rval;
int CurVal;
int mid = left + ((right - left) + 1)/2;
int nextLeft = left;
int nextRight = right;
if (1 == mid)
return mid;
Lval = arr[mid - 1];
Rval = arr[mid + 1];
CurVal = arr[mid];
if (Lval < CurVal)
if (Rval > CurVal)
nextLeft = mid+1;
else
return mid + 1;
else
if (Rval < CurVal)
return mid;
else
nextRight = mid - 1;
return findIncPos(arr, nextLeft, nextRight);
}
int main()
{
int array[] = {10, 3,2,1};
int rightIdx = (sizeof(array)/sizeof(array[0])) - 1;
int pos = findIncPos(array, 0, rightIdx);
printf("Postiion N Val of order change is %d, %d \r\n", pos+1, array[pos]);
}
<pre lang="" line="1" title="CodeMonkey42219" class="run-this">#include <stdio.h>
int findIncPos(int arr[], int left, int right)
{
int Lval;
int Rval;
int CurVal;
int mid = left + ((right - left) + 1)/2;
int nextLeft = left;
int nextRight = right;
if (1 == mid)
return mid;
Lval = arr[mid - 1];
Rval = arr[mid + 1];
CurVal = arr[mid];
if (Lval < CurVal)
if (Rval > CurVal)
nextLeft = mid+1;
else
return mid + 1;
else
if (Rval < CurVal)
return mid;
else
nextRight = mid - 1;
return findIncPos(arr, nextLeft, nextRight);
}
int main()
{
int array[] = {10, 3,2,1};
int rightIdx = (sizeof(array)/sizeof(array[0])) - 1;
int pos = findIncPos(array, 0, rightIdx);
printf("Postiion N Val of order change is %d, %d \r\n", pos+1, array[pos]);
}
</pre><pre title="CodeMonkey42219" input="yes">Please post incase this fails for ne input..</pre>
1. unlike only one partition, any other partition will lead to exctly one partition sorted
2. chk if sorted partition is increasing or decreasing
3. if increasing search in right partition
4 else search in left sub array(left partition)
BS(lo, hi)
m = (lo + hi)/2
if(a[m-1] <a[m] && a[m+1] < a[m])
return m
if(a[m-1] <a[m] && a[m+1] > a[m])
BS(m+1, hi)
if(a[m] < a[m-1] && a[m] > a[m+1])
BS(lo, m-1)
public class FindRotation {
public int findPos(int[] array) {
if(array == null || array.length < 3) {
throw new IllegalArgumentException("invalid array size");
}
int start = 0;
int end = array.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(mid == 0 || mid + 1 >= array.length) {
break;
} else if(array[mid - 1] < array[mid] && array[mid + 1] < array[mid]) {
return mid;
} else if(array[mid - 1] < array[mid] && array[mid + 1] > array[mid]) {
start = mid + 1;
} else if(array[mid - 1] > array[mid] && array[mid + 1] < array[mid]) {
end = mid - 1;
} else {
break;
}
}
return -1;
}
}
public class FindSplitPos {
public int findPos(int[] array) {
if(array == null || array.length < 3) {
throw new IllegalArgumentException("invalid array size");
}
int start = 0;
int end = array.length - 1;
while(start <= end) {
int mid = start + (end - start) / 2;
if(mid == 0 || mid + 1 >= array.length) {
break;
} else if(array[mid - 1] < array[mid] && array[mid + 1] < array[mid]) {
return mid;
} else if(array[mid - 1] < array[mid] && array[mid + 1] > array[mid]) {
start = mid + 1;
} else if(array[mid - 1] > array[mid] && array[mid + 1] < array[mid]) {
end = mid - 1;
} else {
break;
}
}
return -1;
}
}
public static int find(int[] data) {
return find(data, 0, data.length - 1);
}
static int find(int[] data, int start, int end) {
if (end > start) {
int mid = start + (end - start) / 2;
int v = data[mid];
if (v < data[mid + 1])
return find(data, mid + 1, end);
else if (mid == 0)
return 0;
else if (data[mid - 1] > v)
return find(data, start, mid);
else
return mid;
} else
return -1;
}
#include<stdio.h>
#include<conio.h>
int max(int a[],int,int);
int main()
{
int a[6]={12,13,14,10,6,1};
int len;
int i;
printf("%d",max(a,0,5));
getchar();
getchar();
return 0;
}
int max(int a[],int s,int e)
{
int mid=(s+e)/2;
if(s<=e){
if(a[s]>a[s+1])return a[s];
if(a[e]>a[e-1])return a[e];
if(a[mid]>a[mid+1] && a[mid]>a[mid-1])
{
return a[mid];
}
else if(a[s]>a[mid])
{
return max(a,s,mid-1);
}
else
{
return max(a,mid+1,e);
}}
else
return -1;
}
Binary search.
Not tested:
- Anonymous October 02, 2011int findDirectionSwitch(int[] arr) { return findDirectionSwitch(arr, 0, arr.length); } int findDirectionSwitch(int[] arr, int startIndex, int stopIndex) { if (stopIndex - startIndex < 3) { // throw error or return -1 to symbolize no answer; return -1; } int middleIndex = (stopIndex - startIndex) / 2 + startIndex; // Note: i could have done less than previous // I am technically detecting the one before the decreasing start one. // That is why when I find it I have to return +1. bool biggerThanPrevious = arr[middleIndex] > arr[middleIndex - 1]; bool biggerThanNext = arr[middleIndex] > arr[middleIndex + 1]; if (biggerThanPrevious && biggerThanNext) { return middle + 1; } if (biggerThanPrevious) { // Note I didn't do middle+1 here because I like to keep 3. return findDirectionSwitch(arr, middle, stopIndex); } else { // Note I didn't do middle-1 here because I like to keep 3. return findDirectionSwitch(arr, startIndex, middle); } }