Microsoft Interview Question for SDE1s


Country: United States
Interview Type: In-Person




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

public static int FindMinInRSA(int[] arr, int start, int end)
        {
            if (start == end)
                return arr[start];

            if (arr[start] < arr[end])
                return arr[start];

            int middle = (start + end) / 2;

            int small1 = (arr[start] < arr[middle] ? arr[start] : arr[middle]);
            int small2 = (arr[middle + 1] < arr[end] ? arr[middle + 1] : arr[end]);

            if (small1 < small2)
                return FindMinInRSA(arr, start, middle);
            else
                return FindMinInRSA(arr, middle + 1, end);
        }

- Anonymous May 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This question has a trap: whether the sorted array has duplicates. E.g., if the input is {4,1,4,4,4,4,4,4,4}, then this solution will fail. Correct me if I was wrong. Thanks.

- wangpidong October 13, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Given a rotated array that was sorted,
say for example
6,7,1,2,3,4,5
use :

{{
for (i = 0; i < n - 1; i ++)
{
if (a[i+1]<a[i])
break;
}
cout<<"Minimum element is at index"<<i<<" and it's value is"<<a[i];
}}


Time complexity is O(n)

- divinexsoul May 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

awesome,thx

- kalps May 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

correction: min index is at i+1 and value is a[i+1]

- kalps May 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just use bisection and compare to the values at both ends of the array, it is in the book.

- Anonymous May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class MinTest {
    public int findMinOfTwoNumbers(int i, int j)
	{
	    if(i<j)
		   return i;
		else
		   return j;
	}
	
	public void findMin(int[] rsa)
	{
	    int length = rsa.length;
		
		if (length == 0)
		{
		    System.out.println("ERR: 1 Rotated sorted array is empty");
			return;
		}
		
		if (length == 1)
		{
		    System.out.println("The minimum is " + rsa[0]);
			return;
		}
		int min = rsa[0];		
		int i = 0;
		for (i = 0; i < length/2; i++)
		{
		   if (rsa[i] < rsa[length-1-i])
		      min = findMinOfTwoNumbers(min, rsa[i]);
		   else
		      min = findMinOfTwoNumbers(min, rsa[length-1-i]);
		}
		
		if ((length%2) != 0)
		   min = findMinOfTwoNumbers(min, rsa[i]);
		   
		System.out.println("The minimum is " + min);
	}
	
	public static void main(String[] args)
	{
	    MinTest m = new MinTest();
		int [][] testArray = {{},
		                      {1},
							  {1,2},
							  {2,1},
							  {1,2,3},
							  {3,1,2},
							  {2,3,1},
							  {1,2,3,4},
							  {4,1,2,3},
							  {3,4,1,2},
							  {2,3,4,1},
							  {1,1,1,1,1},
		                      {-1},
							  {-1,-2},
							  {-2,-1},
							  {-1,-2,-3},
							  {-3,-1,-2},
							  {-2,-3,-1},
							  {-1,-2,-3,-4},
							  {-4,-1,-2,-3},
							  {-3,-4,-1,-2},
							  {-2,-3,-4,-1},
							  {-1,-1,-1,-1,-1}};
		
		int length = testArray.length;
		
		for(int i = 0; i < length;  i++)
		    m.findMin(testArray[i]);
	}
}

- Anonymous May 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
#include<set>
using namespace std;
set<int> myset;
void binarysearch(int a[],int n)
{
int l=0,mid;
int h=n-1;
while(a[l]>a[h])
{
mid=(l+h)/2;
if(a[mid]>a[h])
l=mid+1;
else
h=mid;
}
myset.insert(a[1]);
myset.insert(a[l]);
set<int> :: iterator it=myset.begin();
cout<<"the minimum element is "<<*it<<endl;
cout<<"the rotation is "<<l<<endl;

}
int main()
{
int a[100];
cout<<"enter the elements";
cout<<endl;
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
binarysearch(a,n);
}

- rajesh May 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// O(log n) steps 
int min (int array[], int left, int right) {
    int middle = (left + right)/2;
    int temp;
    if (issorted(array, left, middle) 
        && issorted(array, middle + 1, right)) {
        return ((array[left] < array[middle+1]) ? array[left] : array[middle + 1]);
    } else if (issorted(array, left, middle)) {
        temp = min (array, middle+1, right);
        return ((array[left] < temp) ? array[left] : temp );
    } else if (issorted(array, middle+1, right)) {
        temp = min (array, left, middle);
        return ((array[middle+1] < temp) ? array[middle+1] : temp); 
    }
}


int issorted (int array[], int left, right) {
    if (array[left] < array[right])
        return 1;
    else 
        return 0;    
}

- Time Pass May 16, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

// You don't need the temp variable. Too lazy to edit !!

- Time Pass May 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Use '<=' in place of '<'

- Time Pass May 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

even though array contains duplicates we can use divide and conquer by little modification

- 11mxian May 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A simple modified binary search would work...

#include<iostream>
using namespace std;
int Min(int arr[],int size);
int main()
{
	int arr[] = {4,5,6,7,8,9,1,2,3};
	int size = sizeof(arr)/sizeof(arr[0]);
	cout<<Min(arr,size);
	return 0;
}
int Min(int arr[],int size)
{
	if(size==1) return arr[0];
	
	int l = 0,h = size-1,m;
	while(l<h)
	{
		if(l+1 == h) return min (arr[l],arr[h]);
		m = l + (h-l)/2;
		if(arr[l]>arr[m]) h = m;
		else if(arr[l]<arr[m]) l = m;
		else return arr[m];
	}
}

- Sarthak Mall June 01, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void findMin(int a[]){
		for(int i=0;i<a.length;i++){
			if(a[i]-a[i+1]>0){
				System.out.print("Min Elem of Arr::"+a[i+1]);
				break;
			}
		}
	}

- SATHISH June 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int searchMin(int[] array, int s, int f){        
        if(s == f)
            return array[s];
        else if(s - f == 1)
            return (array[s] < array[f]? array[s]: array[f]);
        else{
            int mid = (f - s)/2 + s;  
            if(array[mid] < array[mid - 1])
                return array[mid];
            else if(array[mid] < array[s])
                return searchMin(array, s, mid - 1);
            else if(array[f] < array[mid])
                return searchMin(array, mid + 1, f);
            else
                return array[s];
        }   
}

- Novice June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int minIndex (int *arr, int size)
{
        int low = 0;
        int mid = (size/2);
        int high = size-1;

        while (low<high)
        {
                if (arr[mid] > arr[mid+1])
                        return mid+1;
                if (arr[mid-1] > arr[mid])
                        return mid;
                if (arr[low] < arr[high])
                        return low;
                if (arr[low] < arr[mid])
                {
                        low = mid+1;
                }
                else if (arr[low] > arr[mid])
                {
                        high = mid-1;
                }
                mid = low + (high-low)/2;
        }
}

- saurabh June 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findNumOfShifts2(int [] A){
	int start=0;
	int end=A.length-1; 
	while(start<end){
		int mid = start + (end-start)/2;
		if(A[start]>A[start+1])
			break;
		
		if(A[mid]<A[start])
			end=mid;
		else if (A[mid]>A[end])
			start=mid;
		else 
			start=start+1;//fallback to linear search
	}
	return A[(start+1)%A.length]; 
}

Test with:
Input:
{1, 2, 2, 2, 2, 2, 2, 2, 2}

For this input, try to rotate 0, 1, 2, ..., the above code output the correct result, which is 1.

- Anonymous July 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My solution in C++ below.

As mentioned in the question, it's better to write (start + end) / 2 = start + (end - start) / 2 as it doesn't imply an addition of two integers which results could be greater than INT_MAX.

#include <iostream>
#include <vector>

using namespace std;

int findMin(vector<int> L) {
    if (L.size() == 0) {
        // Not supported
    }
    if (L.size() == 1)
        return L[0];
    int start = 0, end = L.size() - 1, middle;
    while ((middle = start + (end - start) / 2) != start) {
        if (L[middle] > L[end]) {
            start = middle;
        } else if (L[start] > L[middle]) {
            end = middle;
        } else {
            // Error, the list is not correct
        }        // At this point, L[start] > L[end]
    }
    return L[end];
}

- Thomas February 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done pretty straightforward. We're basically looking for the point of rotation and the beautiful thing about this case is that one part of the array will always be sorted, given distinct elements.
So we just check if the latter part of the array is sorted, if it's not, we look for the inflection point there and hence the min. If it is, that means that either the inflection point is in the lower part of the array or maybe there's no inflection point at all.

int getMinimum(vector<int> input){
	if(!input.size())
		return -1;
	if(input.size()==1){
		return input[0];
	}

	int start = 0;
	int end = input.size()-1;
	int mid;
	while(start <= end){
		mid = start + (end-start)/2;
		if(start==end){
			return input[start];
		}

		if(input[mid] > input[end]){
			start = mid+1;
		} else {
			end = mid;
		}
	}
}

- imps November 23, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

The point at which rotation has occurred can be found only in linear time. So the entire thing will take O(n), the same as finding min in any array.

- EK MACHCHAR May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

Why don't you use divide and conquer ? .. using that we divide the array into two parts recursively and do that comparison in your conquering step with which you can find the MIN of the array with O(log n).

- code_monkey May 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@code_monkey - if the array contains duplicates, linear search is required.

- Vin May 05, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

My code is below with the algorithm as comments. Works even for the repeated elements.

//Find Min in Rotated Sorted Array
//Example: int array[10] = {7, 8, 9, 10, 11, 12, 3, 4, 5, 6};
// Min in the above array is 3
// Solution: Recursively search (Modified binary search) for the Pivot where is the smallest Element is present
// Algorithm: 
// 1) Find the Mid of the Array 
// 2) call the recursive function on segment of array in which there is a deviation in the order
// If (A[low] > A[mid]) array segment in which deviation in the order present is (low, mid)
// If (A[low] < A[mid]) array segment in which deviation in the order present is (mid + 1, high) 
// Time Complexity: O(logn)
// Space Complexity: is of the recursive function stack that is being used

#define MIN(x,y) (x) <= (y) ? (x): (y)

int MininRotatedSortedArray(int A[], int low, int high)
{
    if(low > high)
        return -1;

    if(low == high - 1)
        return MIN(A[low], A[high]);

    int mid = low + (high - low)/2;

    if(A[low] > A[mid])
        return MininRotatedSortedArray(A, low, mid);
    else if(A[low] < A[mid])
        return MininRotatedSortedArray(A, mid + 1, high);
    else
        return A[mid];
}

- Sriramulu Appana May 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In the last else case i.e a[mid]==a[low] why do we return a[mid]?

- 4m7u1 July 04, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What about the following two cases?
{4,1,4,4,4,4,4,4,4,4}
{1,2,3,4} (i.e., no rotation)

- wangpidong October 13, 2013 | Flag


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