## Microsoft Interview Question for SDE1s

• 1
of 1 vote

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

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

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.

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)

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

awesome,thx

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]

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.

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

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

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

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

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

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

Use '<=' in place of '<'

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

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

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

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

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

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.

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

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

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.

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

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

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

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

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

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

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

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

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.