Microsoft Interview Question
SDE-2sCountry: United States
Interview Type: Phone Interview
Algorithm
1. Find the pivot element index in the array (pivot element is the first smallest element in the array input)
2. Subtract : array.length - pivot_elem_index to get the number of rotations.
Step 1: Find Pivot Index
public static int pivot(int a[]){
int low = 0; int high = a.length -1;
while(a[low] > a[high]){
int mid = (low+high) >> 1;
if(a[mid] > a[high]){
low = mid+1;
}
else{
high = mid;
}
}
//System.out.println("pivot : "+a[low]);
return low;
}
Step 2 : (a.length - low) = No of rotations
import java.util.Scanner;
public class arr {
public static void main(String[] args) {
int a[]= new int[100];
int n=1;
Scanner j= new Scanner(System.in);
for(int i=0;i<10;i++){
a[i]=j.nextInt();
}
for(int i=0;i<10;i++){
if(a[i]<a[i+1]){
n++;
}
else
{
n=10-n;
System.out.println(n);
break;
}
}
}
}
import java.util.Scanner;
public class arr {
public static void main(String[] args) {
int a[]= new int[100];
int n=1;
Scanner j= new Scanner(System.in);
for(int i=0;i<10;i++){
a[i]=j.nextInt();
}
for(int i=0;i<10;i++){
if(a[i]<a[i+1]){
n++;
}
else
{
n=10-n;
System.out.println(n);
break;
}
}
}
}
import java.util.Scanner;
public class arr {
public static void main(String[] args) {
int a[]= new int[100];
int n=1;
Scanner j= new Scanner(System.in);
for(int i=0;i<10;i++){
a[i]=j.nextInt();
}
for(int i=0;i<10;i++){
if(a[i]<a[i+1]){
n++;
}
else
{
n=10-n;
System.out.println(n);
break;
}}}}
import java.util.Scanner;
public class arr {
public static void main(String[] args) {
int a[]= new int[100];
int n=1;
Scanner j= new Scanner(System.in);
for(int i=0;i<10;i++){
a[i]=j.nextInt();
}
for(int i=0;i<10;i++){
if(a[i]<a[i+1]){
n++;
}
else
{
n=10-n;
System.out.println(n);
break;
}}}}
The idea is to use a the binary search
public int GetNumShifts(int[] a)
{
if (a == null || a.Length == 0)
return 0;
int index = GetIndexMaxValue(a);
return (index + 1) % a.Length;
}
private int GetIndexMaxValue(int[] a)
{
int start = 0;
int end = a.Length - 1;
while (a[start] > a[end])
{
int middle = (start + end) / 2;
if (a[middle] > a[middle + 1])
return middle;
if (a[start] > a[middle])
end = middle - 1;
else
start = middle + 1;
}
return end;
}
As others have already suggested, we can use a modified binary search to find the pivot point. Here is a sample working code in C. Its self explanatory so I'm not going into the details.
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
bool findRotationIdx(int *A, int length)
{
printf("length of array is %d \n", length);
if(length == 0)
{
printf("Empty array \n");
return false;
}
if(length == 1)
{
printf("Index is %d", length-1);
return true;
}
int l = 0;
int h = length-1;
int m = 0;
while(l<=h)
{
m = (l+h)/2;
if(l==h)
{
//match
printf("Rotation index is %d \n",l);
return true;
}
else if (A[l] < A[m])
{
//pivot is in upper half
l = m+1;
}
else
{
h = m-1;
}
}
return true;
}
int main()
{
int A[10] = {6,7,8,9,10,11,1,2,3,4};
int B[7] = {6,7,1,2,3,4,5};
bool retVal = findRotationIdx(B, (sizeof(B)/sizeof(int)));
if (!retVal)
{
printf("Error in array, kindly check \n");
}
return 0;
}
Use a variation of the binary search to find the index where arr[i-1] > arr[i] and then return i. Complexity O(log n), memory (O(1)
- zortlord June 25, 2015