Microsoft Interview Question for Software Engineer / Developers

Country: India
Interview Type: Written Test

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

Its easy you can implement binary search . You do two binary search. First for elements at even position(index_even = 2*i) and another one for elements at odd position(index_odd = 2*i+1).

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

``````public static int alternateBinarySearch(int[] array, int i)
{
int low1=0, high1= (int)Math.ceil(((double)array.length)/2)-1, mid1;
int low2=0, high2= array.length/2-1, mid2;

if(array[array.length-1]==i)
return array.length-1;

if(array[array.length-2]==i)
return array.length-2;

if(array[0]==i)
return 0;

if(array[1]==i)
return 1;

while(low1<high1-1||low2<high2-1)
{
mid1=(high1+low1)/2;
mid2=(high2+low2)/2;

if(array[2*mid1]==i)
return mid1*2;
else if(array[2*mid1]>i)
high1= mid1;
else
low1= mid1;

if(array[2*mid2+1]==i)
return mid2*2+1;
else if(array[2*mid2+1]>i)
high2= mid2;
else
low2= mid2;
}
return -1;
}``````

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

``````here is what we can do
low1 = 0;  // even indexes
low2 = 1; // odd indexes
len = arr.length;
if (len%2 ==)  {
high1 = len-2;
high2  = len-1;
}
else {
high1 = len-1;
high2  = len-2;
}

// search in even indexes
int idx = search (low1, high1, value, true);  // true to say it is for even indexes
if (idx == -1) {
idx = search (low2, high2, value, false)
}
return idx;
}

int search (int low, int high, int value, boolean even) {
while (low < high) {
int mid = (low+high)/2;
if (even && mid %2 != 0) {  // if index is even and mid is not even, make mid as even
mid = mid-1;
}
else if (!even & mid%2 == 0) { // if index is odd and mid is even, make mid as odd.
mid = mid -1;
}
if (a[mid] == value) {
return mid;
}
else if (a[mid] < value) {
low = mid+2;
}
else {
high = mid-2;
}
return search (low, high, value);
}
return -1;``````

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

--> we are calling binary search two times , first on elements at even position and then for elements at odd position
--> we can also merge both the conditions in one call but that was getting complex and wouldn;t improve performance anyway....

Time complexity here is O(logn) , Space complexity O(1)

``````#include<stdio.h>
#include<stdlib.h>

int search(int arr[],int element,int start,int end);

int main()
{
int arr[] = {12,2,16,5,18,32,33,38,34,39};
int length = sizeof(arr)/sizeof(int);

//suppose we are searching for 16;
int element = 39;

printf("\n Search Trace \n");

// We will apply binary search seperately on list of elements at even position
//and then at list of elements at odd position

int evenStart = 0;  //start of list of even elements
int oddStart = 1;   //start of list of odd elements
int end = length-1;
int evenEnd;    //end of list of even elements
int oddEnd;     //end of list of odd elements

if(end%2==0)
{
evenEnd = end;
oddEnd = end - 1;
}
else
{
oddEnd = end;
evenEnd = end - 1;
}

int pos;

pos = search(arr,element,evenStart ,evenEnd );

if(pos == -1)
pos = search(arr,element,oddStart,oddEnd );

if(pos == -1)
printf("\n\nElement not in list ");
else
printf("\n\nPositio of element : %d in list is %d",element,pos );

return 0;
}

//basic binary search

int search(int arr[],int element,int start,int end)
{

printf("Start : %d \t End : %d\n\t\t",start,end);

if(start > end)
return -1;

int mid = (start + end)/2;

if(start%2 == 0) //if start is even then making sure that middle element is also at even position
{
if(mid%2 != 0)
mid++;
}
else            //if start is odd then making sure that middle element is also at odd position
{
if(mid%2 == 0)
mid++;
}

if(element == arr[mid])
return mid;

int pos;

//since we have odd and even elements we do mid+2 and mid-2 to make
//sure start and end are always odd or even

if(element > arr[mid])
pos = search(arr,element,mid+2,end);
else
pos = search(arr,element,start,mid-2);

return pos;

}``````

Ouput :
Search Trace
Start : 0 End : 8
Start : 6 End : 8
Start : 10 End : 8
Start : 1 End : 9
Start : 7 End : 9

Positio of element : 39 in list is 9

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

``````int
bsearch(int arr[], int lindex, int rindex, int target) {
if (lindex > rindex) return -1;
int n = (rindex - lindex) / 2 + 1;
int mid;
if (is_even(n)) {
mid = (lindex + rindex) / 2 - 1;
} else {
mid =  (lindex + rindex) / 2;
}
if (arr[mid] == target) {
return mid;
} else if (arr[mid] > target) {
return bsearch(arr, lindex, mid - 1);
} else {
return bsearch(arr, mid + 1, rindex);
}
}

int
search(int arr[], int n) {
int retv = bsearch(arr, 0, n);
if (retv >= 0) return retv;
retv = bsearch(arr, 1, n - 1);
if (retv >= 0) return retv;
return -1;

}``````

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

bool findnum(num,start,end)
if start > end return false
else
if(num == a[(start + end)/2]
return true
else if(num < a[(start + end)/2]
return findnum(num,start,(start + end)/2 -1]
else
return findnume(num,(start + end)/2 +1 , end)

This must work !!

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.

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.