## Microsoft Interview Question for Software Engineer in Tests

• 0
of 0 votes

Country: United States
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
2
of 2 vote

The above logic applies to array with unique numbers.
But, if the array contains duplicate, then magic numbers can be on both sides of mid.

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````#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;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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]

Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

Comment hidden because of low score. Click to expand.
0
of 0 votes

no it works fine

Comment hidden because of low score. Click to expand.
0
of 0 votes

no it works fine

Comment hidden because of low score. Click to expand.
0
of 0 votes

can some one explain the logic
what is output and how it is ??

Comment hidden because of low score. Click to expand.
0
of 2 vote

Whats the logic behind if(number[mid] == number[mid+1] || number[mid] == number[mid-1]) this?? When we found a match number[i]=i

Comment hidden because of low score. Click to expand.
0
of 0 votes

Doesn't work because array contains duplicates... even if a[3] = 5 > 3, a[4] and a[5] could both be 5, making 5 the magic number(and your algorithm would just ignore it).

Comment hidden because of low score. Click to expand.
0
of 0 vote

I do understand moving to left side, but I am not able to understand why we don't go on left side..what if we find a magic number at index 2 and value 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

can someone explain what magic numbers are? what is the objective here

Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

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)).

Comment hidden because of low score. Click to expand.
0
of 0 votes

Since the magic index (or number) can only be one in the array, you could return if either of your conditions is true.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````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.

Comment hidden because of low score. Click to expand.
-1
of 1 vote

are the numbers unique or not?

Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

### Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

### Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More