Microsoft Interview Question for SDE1s


Team: Microsoft CRM
Country: India
Interview Type: Phone Interview




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

Its a modified version of binary search
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, 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);
}

}
}

- Gurpreet Singh September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

your code will fail for input array num[]={ 3, 4, 5, 6, 1, 2 } and item = 2

- db September 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

db, please look at the modified code below

- singhguru2001 September 11, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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'

- jeevanus September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you please elaborate "previous to 'start' is the 'end'" part.

- Monkey_In_The_Middle September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

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

Yes. There is an issue with the above code if there exists duplicate values. There is another code mentioned below which is tested for duplicates. Please look at it and let me know if you have any questions.

- singhguru2001 September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Gurpreet Singh September 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

When i said 0, i meant the 0th element in the array*

- Gurpreet Singh September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks Gurpreet Singh,
I was very confused to find the first element during the interview. Just now started to practice coding. I never thought it would be very simple.

- jeevanus September 04, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Kamala September 05, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The question says the sorted array is rotated by N. So Gurpreet solution is a slightly modified version of the conventional binary search.

- Anonymous September 05, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

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

Question says sorted array. Your example array isn't sorted.

- Naveen September 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Praveen Pandey September 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Gurpreet Singh September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Anonymous September 07, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- singhguru2001 September 07, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

}

}

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

Thanks!! But I see that you are searching for the element linearly. We could just write a for loop for doing the same rather than going through the pain of recursion. Don't you think so?

- singhguru2001 September 08, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- arsragavan September 09, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Looked promising. :( Didn't work for the following input

{ 4, 4, 4, 5, 6, 1, 2, 3, 4, 4 }

- singhguru2001 September 09, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- arsragavan September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- lalit September 12, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- lalit September 12, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- amaankhanpro September 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- biscayne3 September 15, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Naveen September 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Naveen, Sorted array which is rotated. If it was sorted and not rotated, we wouldn't be trying to find a better way. We would have used binary search.

- Anonymous September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- eylonsa September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

mydevpath.wordpress.com/2014/09/17/find-index-of-lookup-value-in-an-int-array/

- Philip September 29, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

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

- AK October 26, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- zprogd February 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Check my solution

- sonesh June 07, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- sonesh June 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Jerry March 24, 2016 | 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