Microsoft Interview Question
Software Engineer in TestsCountry: United States
Interview Type: In-Person
#include <stdio.h>
int main() {
int number[] = {-10, -5, 2, 2, 2, 2, 4, 7, 9, 12, 13};
int lo = 0;
int hi = (int)sizeof(number)/(int)sizeof(int)-1;
int mid = (lo+hi)/2;
if(number[lo] == lo && number[lo+1] == lo+1) {
printf("Magic number is : %d\n", number[lo]);
return 0;
}
if(number[hi] == hi && number[hi-1] == hi-1) {
printf("Magic number is : %d\n", number[hi]);
return 0;
}
while(lo <= hi) {
printf("%d %d\n", mid, number[mid]);
if(mid > number[mid])
hi = mid-1;
else if(mid < number[mid])
lo = mid+1;
else if(mid == number[mid]) {
if(number[mid] == number[mid+1] || number[mid] == number[mid-1]) {
printf("Magic number is : %d\n", number[mid]);
break;
}
}
mid = (lo+hi)/2;
}
return 0;
}
Apply Binary search with rule : if mid < number[mid]
then magic number lies on rhs of mid , so lo = mid+1
else mid > number[mid ], hi = mid-1;
else
if mid = number[mid], then check the numbers on index+1 and index-1, if they are same as number[mid], then return numer[mid]
I think above logic is not correct
1 2 2 2 3 4 7 7
If we take index starts with 1, for the above sorted array you have magic number both at the left of mid(2) and right if mid(7).
Whats the logic behind if(number[mid] == number[mid+1] || number[mid] == number[mid-1]) this?? When we found a match number[i]=i
Please correct me if I am wrong!
public class MagicNumber {
public static void findMagicNumber(int[] array) {
if (array == null || array.length == 0) {
return;
}
int low = 0;
int high = array.length - 1;
while (low <= high) {
if (array[low] == low) {
System.out.println("Magic number:" + low);
}
if (array[high] == high) {
System.out.println("Magic number:" + high);
}
low++;
high--;
}
}
public static void main(String[] args) {
int[] array = {-10,-5,2,2,2,2,4,7,9,12,13};
findMagicNumber(array);
}
}
This is n/2 solution and is correct and better than a linear search (n). However itsnot better than apply binary search logic (Log(N)).
public class Problem3 {
public static void main(String[] args) {
MagicIndex m = new MagicIndex();
int[] arr = { -20, -10, -1, -3, 1, 3, 5, 7, 11 };
System.out.println(m.magicIndex(arr, 0, arr.length - 1));
}
}
class MagicIndex {
public int magicIndex(int[] arr, int low, int high) {
int mid = (high - low) / 2 + low;
if (arr[mid] == mid) {
return mid;
} else if (arr[mid] < mid) {
low = mid + 1;
} else if (arr[mid] >= mid) {
high = mid - 1;
}
return magicIndex(arr, low, high);
}
}
A slight variation in computing mid to avoid exceeding index range. Log(N) solution.
The above logic applies to array with unique numbers.
- Abhijit September 18, 2012But, if the array contains duplicate, then magic numbers can be on both sides of mid.