Microsoft Interview Question
SDE1sCountry: United States
Interview Type: In-Person
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)
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]);
}
}
#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);
}
// 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;
}
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];
}
}
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];
}
}
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;
}
}
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.
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];
}
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;
}
}
}
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.
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).
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];
}
- Anonymous May 17, 2013