|
Given an array of integers...like 10 12 16 17 24 27 8 6 5 4 2.....
Microsoft Interview Questions and Answers
(Continued from previous question...)
25. Given an array of integers...like 10 12 16 17 24 27 8 6 5 4 2.....
Question:
Given an array of integers...like 10 12 16 17 24 27 8 6 5 4 2....first from 10 to 27 it is in increasing order... .and then decreasing order
starts....so he asked me to find the position from where decreasing starts....it should be done in O(logn).
maybe an answer1:
int 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);
}
}
maybe an answer2:
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 Given an array of integers...like 10 12 16 17 24 == '__main__':
arr = [10, 12, 16, 17, 24, 27, 8, 6, 5, 4, 2]
print solve(0, len(arr), arr) + 1
maybe an answer3:
#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
]);
(Continued on next question...)
Other Interview Questions
| 