Microsoft Interview Question SDE-2s
Country: 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, 2015public static int findRotation(int[] arr){ if(arr == null){ throw new NullPointerException(): } if(arr.length < 2){ return 0; } if(arr.length == 2){ if(arr[0] < arr[1]){ return 0; } return 1; } int lo = 0; int hi = arr.length -1; int mid; while(lo + 1 < hi){ mid = (lo >> 1) + (hi >> 1); //if in the first half if(arr[mid] < arr[lo]){ hi = mid; } //else in the second half else if(arr[mid] >= arr[hi]){ lo mid; } //otherwise cannot tell else{ return 0; } } return hi; } //testing using JUnit @Test(expected=NullPointerException.class) public void test_null(){ findRotation(null); } @Test public void test_empty(){ assertTrue(findRotation(new int[0]) == 0); } @Test public void test_indeterminate(){ assertTrue(findRotation(new int[]{1}) == 0); assertTrue(findRotation(new int[]{1, 1}) == 0); assertTrue(findRotation(new int[]{1, 1, 1}) == 0); assertTrue(findRotation(new int[]{1, 2, 3, 4}) == 0); assertTrue(findRotation(new int[]{7, 7, 7, 7, 7, 7, 7}) == 0); } @Test public void test(){ assertTrue(findRotation(new int[]{2, 1}) == 1); assertTrue(findRotation(new int[]{2, 3, 1}) == 1); assertTrue(findRotation(new int[]{3, 1, 2}) == 2); } @Test public void lengthTest(){ int[] arr = new int[]{1, 1, 2, 2, 3, 3, 3, 4, 5, 7, 7}; for(int i = 0; i < arr.length; i++){ int[] rotArr = rotate(arr); assertTrue(findRotation(rotArr)==i); } } private int[] rotate(int[] arr, int rot){ int[] rotArr = new int[arr.length]; int position = 0; for(;rot + position < arr.length; position++){ rotArr[position] = arr[rot + position]; } for(int i = 0; i < rot; i++){ rotArr[position] = arr[i]; position++; } return rotArr; }