Microsoft Interview Question for Software Engineer in Tests


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.

- Abhijit September 18, 2012 | Flag Reply
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;
}

- abhishek September 17, 2012 | Flag Reply
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]

- abhishek September 17, 2012 | Flag
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).

- Anonymous September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no it works fine

- abhishek September 17, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

no it works fine

- abhishek September 17, 2012 | Flag
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 ??

- yugandharr September 24, 2012 | Flag
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

- Psycho September 18, 2012 | Flag Reply
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).

- meh October 15, 2012 | Flag
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

- soni vashisht September 18, 2012 | Flag Reply
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

- ruth542 March 02, 2013 | Flag Reply
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);
	}

}

- Kevin March 07, 2013 | Flag Reply
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)).

- Beginner March 05, 2014 | Flag
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.

- Beginner March 05, 2014 | Flag
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.

- Beginner March 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

are the numbers unique or not?

- gnahzy September 17, 2012 | Flag Reply


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