Microsoft Interview Question
SDE1sTeam: Microsoft CRM
Country: India
Interview Type: Phone Interview
@Gurpreet Singh, the answer is fine. But,
How do u know the 'start' element? First we have to find that.
Also we don't need to pass the 'end' element, because always the element which is previous to 'start' is the 'end'
int[] num = new int[] {8,8,9,1,3,5,7}; should output 0 for Search(num, 8, 0, 6); but it output 1 instead.
Start with 0. like I did. The number of times the array is rotated doesn't matter as we are taking care of it in the condition. There is a requirement to pass the end element. As it differs based on which part of the array the value belongs to. If you see the code, the end value is changing.
Before writing program for binary search ,please keep in mind that the array should be sorted. Your code is fine but array should be sorted.
The solution is incorrect.
Try the below input array for the same test case
int[] num = new int[] { 4, 4, 4, 4, 5, 6, 1, 2, 3, 4, 4 };
Complexity : O(N)
$inputArray = array(4, 4, 4, 4, 5, 6, 1, 2, 3, 4, 4);
function getRotationLength($inputArray) {
$orderingChangeLocation = 0;
for($i =0 ; $i < (count($inputArray)-1); $i++) {
if ($inputArray[$i] > $inputArray[$i+1]) {
$orderingChangeLocation = $i+1;
}
}
return $orderingChangeLocation;
}
function getNoPosition(array $inputArray, $rotatedLength = 0, $inputNumber) {
$arraySize = count($inputArray);
$inputNoIndex = -1;
for ($j =0 ; $j < ($arraySize-1); $j++) {
$index = ($rotatedLength + $j)% $arraySize;
if ($inputArray[$index] == $inputNumber) {
$inputNoIndex = $j;
break;
}
}
return $inputNoIndex;
}
$roationLength = getRotationLength($inputArray);
print_r(getNoPosition($inputArray, $roationLength, 5));
Apologies for not taking into consideration duplicate values. Please look at the modified code below:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace binarySearchRoated
{
class Program
{
static void Main(string[] args)
{
int[] num = new int[] { 4, 4, 4, 4, 5, 6,9, 1, 1, 2, 3,4 };
int item=9;
int j=FindPivot(num,0,num.Length-1);
if (num[j] <=item && item <=num[num.Length-1])
Console.WriteLine(Search(num, item, j, num.Length-1));
else
Console.WriteLine(Search(num, item,0, j-1));
Console.WriteLine(j);
}
private static int FindPivot(int[] num, int start, int end)
{
if (num[start] < num[end] || start ==end)
return start;
int mid = (start + end )/ 2;
if (num[mid] >= num[end])
return FindPivot(num, mid + 1, end);
else
return FindPivot(num, start, mid - 1);
return mid+1;
}
private static int Search(int[] num, int item, int start, int end)
{
int mid=0;
if (item == num[start])
return start;
if (end < start)
return -1;
mid = (start + end) / 2;
if(num[mid]==item)
return mid;
if(num[mid]>item)
return Search(num, item, start, mid - 1);
else
return Search(num, item, mid + 1,end);
}
}
}
I have not look at how well this would perform. If someone else has a better answer, please share it. Also, I have validated the above with few case but not all. Please let me know if this breaks.
I might over complicated it but it works
O(n)
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
int findX(int A[],int x,int candidate,int index,bool rotated,int size){
if((A[index]==x && candidate == -1) || (A[index]==x && rotated == true )){
candidate =index;
}
//printf("%d \n",A[index]);
if(index >= size-1){
return candidate;
}
if(A[index + 1] < A[index] ){
rotated = true;
}
return findX(A,x,candidate,index +1,rotated,size);
}
int main(void){
int A[]={ 4, 5, 6, 1, 2, 3, 4,4 };
int size =(sizeof(A)/sizeof(A[0]));
int index=findX(A,8,-1,0,false,size);
printf("index %d",index);
return 0;
}
Hmm, it works great!!! The only problem is that it is not returning the positing of the first occurrence of 4. In the above input, it should return 6, but it returns 7. : ( similar issue was with the code I first posted when duplicates existed.
You're right. It should return when on the first occurrence of 4 if it's rotated.
Here's the fix,
int findX(int A[],int x,int position,int started_index,bool rotated,int size){
if(A == NULL) return -1;
if(started_index > size-1){
return position;
}
if((A[started_index]==x && rotated == true)){
return started_index;
}
if((A[started_index]==x && position == -1) ){
position =started_index;
}
if(!rotated){
if(started_index - 1 >=0 && A[started_index] < A[started_index -1])
rotated = true;
}
return findX(A,x,position,started_index +1,rotated,size);
}
}
It's very much similar to Bin search. One point to be noted is to check if the right side of the mid or left side of mid is sorted.
1. If the element is equal to a[mid] then return mid
2. If the right side of mid is sorted (meaning a[mid]<a[high],
a. If x > a[mid] and x< a[high] then x lies between mid and high
b. Else x lies between low and mid-1
3. If the left side of mid is sorted (meaning a[low] < a[mid]),
a. If x < a[mid] and x >a[low] then x lies between low and mid
b. Else x lies between mid and high
public int find(int[] a, int x) {
int low = 0;
int high = a.length - 1;
int mid = 0;
while (low <= high) {
mid = (low + high) / 2;
if (a[mid] == x)
return mid;
if (a[mid] <= a[high]) {
if (x > a[mid] && x <= a[high])
low = mid + 1;
else
high = mid - 1;
} else {
if (x < a[mid] && x >= a[low])
high = mid - 1;
else
low = mid + 1;
}
}
return -1;
}
Looked promising. :( Didn't work for the following input
{ 4, 4, 4, 5, 6, 1, 2, 3, 4, 4 }
Thanks for pointing out. I did not add the code for returning the lowest position of the element. I think the following piece of code will help in fixing it.
if (a[mid] == x) {
while (mid > 0)
if (a[mid - 1] == x)
mid--;
return mid;
}
Test this.
int find(int* a, int x, int n) {
int low = 0;
int high = n - 1;
int mid = 0;
int pre, next;
while (low <= high) {
mid = (low + high) / 2;
pre = (mid + n - 1) % n;
next = (mid + 1) % n;
if (a[mid] == x) {
if(a[pre] != x)
return mid;
else
high = pre;
} else {
if (a[next] <= a[high]) {
if (x >= a[next] && x <= a[high])
low = next;
else
high = pre;
} else {
if (x <= a[pre] && x >= a[low])
high = pre;
else
low = next;
}
}
}
return -1;
}
Try this
int find(int* a, int x, int n) {
int low = 0;
int high = n - 1;
int mid = 0;
int pre, next;
while (low < high) {
mid = (low + high) / 2;
pre = (mid + n - 1) % n;
next = (mid + 1) % n;
printf("h=%d, l=%d, mid=%d, p=%d, nxt=%d\n", high, low, mid, pre, next);
if (a[mid] == x) {
if(a[pre] != x)
return mid;
else
high = pre;
} else {
if (a[next] <= a[high]) {
if (x >= a[next] && x <= a[high])
low = next;
else
high = pre;
} else {
if (x <= a[pre] && x >= a[low])
high = pre;
else
low = next;
}
}
}
if(low == high && a[low] == x)
return low;
return -1;
}
A={ 4, 4, 4, 5, 6, 1, 2, 3, 4, 4 }
B=A+A={ 4, 4, 4, 5, 6, 1, 2, 3, 4, 4 ,4, 4, 4, 5, 6, 1, 2, 3, 4, 4 }
if list is sorted is ascending order then find the switch element i.e., 1
if we know number of elements in the array then
start=switch element;
end =B[switch element pos+n-1];
binarysearch(search_element, start, end);
This successfully identifies the most left index of 4. I also did several test like:
{ 4, 4, 4, 4, 5, 6, 1, 2, 3, 4, 4} and
{ 0, 3, 4, 4, 5, 6, 1, 2, 3, 4, 4} and it also works. I hope it helps.
int main(){
int num[] = { 1, 4, 4, 4, 5, 6, 1, 2, 3, 4, 4};
int index = -1;
indexOf(4,num,0, 11, index);
cout << index << endl;
return 0;
}
void indexOf(int num, int numList[], int start, int end, int& posIndex ){
print(end-start, numList);
// Base case
if ( start > end)
return;
// Get middle
int mid = (end - start)/2;
if ( numList[mid] == num){
posIndex = mid;
}
// Special Case
else if (mid == 0 && numList[mid+1]==num){
posIndex = mid+1;
}
// Check if it is on the right
if ( numList[mid] > num && num <= numList[end]){
indexOf(num, numList, mid + 1, end, posIndex);
}
else{
// Else go to the left
indexOf(num, numList, start, mid-1, posIndex);
}
}
Maybe I misunderstood but the question clearly says that a sorted int array is given and everyone seemed taking input array which is not sorted.
Hi everyone, I wrote a function thtat I think will work on all cases. but I'm using iteration and not recursion. it's in C#
class Program
{
static void Main(string[] args)
{
//int[] arr = { 10, 11, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
//int[] arr = { 11, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 };
int[] arr = { 3, 4, 5, 6, 7, 8, 9, 10, 11, 1, 2 };
Console.WriteLine(Functions.Find(arr, 2));
}
public static class Functions
{
public static int Find (int[] arr, int item)
{
int candidate = -1;
int l = 0, r = arr.Length - 1, mid;
while (l <= r)
{
mid = (l + r) / 2;
if (arr[l] == item)
return l;
if (arr[mid] == item)
candidate = mid;
if (arr[l] <= arr[mid]) // right side is out of order
{
if (arr[l] < item && item <= arr[mid])
r = mid - 1; //go left
else
l = mid + 1; //go right
}
else // left side is out of order
{
if (arr[mid] < item && item < arr[l])
l = mid + 1; //go right
else
r = mid - 1; //go left
}
}
return candidate;
}
}
Enjoy :) Basically the idea is: operate always on ascending subarray:
// Idea: find ascending subarray and operate on it
int FindElement(int *arr, int begin, int end, int element)
{
int iResult = -1;
int med = -1;
if (arr && begin <= end)
{
while (begin <= end)
{
med = (begin + end) / 2;
if (arr[med] == element)
{
iResult = med;
}
if (arr[med] <= arr[end])
{
if (element > arr[med] && element <= arr[end])
{
begin = med + 1;
}
else
{
end = med - 1;
}
}
else
{
if (element < arr[med] && element >= arr[begin])
{
end = med - 1;
}
else
{
begin = med + 1;
}
}
}
}
return iResult;
}
Hi guys,
It looks like there is only O(n) solution for arrays where arr[left] = arr[mid] = arr[right]
2, 2, 2, 2, 3, 1, 2
or
2, 3, 1, 2, 2, 2, 2
Test binary search for these arrays. You don't know where is begin of shifted array on left or on right and which side to choose for the next iteration.
Here is the logic to search any element in such a array
You can see that although the array is rotated N times, but actual rotation will happen only N mod L(size of the input array) times.
Assumptions : sorting order is known to us, and so rotation side, (left or right, i am assuming left here)
Find(A, i, j, Key)
If i == j
if A(i) == key
return i;
else return Key Not Found
else if j = i+1
check whether A(i) or A(j) are each to key, if both of them, then return i, if one of them then return that, else return Key Not Found
else
q = i + (j-i)/2
if A(i) > A(q)
if key < A(q) or ( key > A(q) and key > A(i))
Call Find (A,i,q-1,key);
else if key > A(q) and key < A(i))
Call Find (A,q+1,j,key);
else if key = A(q) and A(q-1) <> key
return q;
else if key = A(q)
call Find(A, i, q-1, key)
else
if Key > A(q) or (Key < A(q) and key < a(i))
call Find (A,q+1,j,Key)
else if Key < A(q) and key > a(i)
call Find (A,i,q-1,Key)
else if key = A(q) and A(q-1) <> key
return q;
else if key = A(q)
call Find(A, i, q-1, key)
end
end
end
end
Complexity
Time : O(log(n))
Space : O(1)
I think we can not go for the binary search logic because of the "rotated sorted" constrain and number will not be seniority between one sorted set and another sorted set
So we can add all the checked values from the array into hashTable with key as their index , and when we found duplicated values, return key from hash table for that value (O(1)). So, the loop will be ended as soon as we got duplicated values. This will work for any kind of input values.
Its a modified version of binary search
- Gurpreet Singh September 04, 2014using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace binarySearchRoated
{
class Program
{
static void Main(string[] args)
{
int[] num = new int[] { 4, 5, 6, 1, 2, 3, 4,4 };
int i = Search(num, 6, 0, 7);
}
private static int Search(int[] num, int item, int start, int end)
{
if (end < start)
return -1;
int mid = (start + end) / 2;
if(num[mid]==item)
return mid;
if (num[mid] < item && item <= num[end])
return Search(num, item, mid + 1, end);
else
return Search(num, item,start, mid - 1);
}
}
}