## Microsoft Interview Question for SDE-2s

• 0

Country: United States
Interview Type: Phone Interview

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

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)

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

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

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

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

Finding the pivot element in an unsorted array(now that it is rotated) is the challange. Its not of order logn anymore.

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

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

}

}

}

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

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

}

}

}

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

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

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

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

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

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

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

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.

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

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

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

``````public static int GetAscendingRotation(int[] A)
{
int p1 = 0, p2 = 1;
while(p2 < A.Length)
{
if(A[p1] > A[p2])
{
return p2;
}
}

return 0;
}``````

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

``````int findRotation (int a[]){

int n=0;
for(int i=0;i<a.length-1;i++){

if(a[i]<a[i+1]){

n++;
}else {
break;
}
}

if(n==a.length) {
return 0;
}

return a.length-n;

}``````

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

``````int findPivot(int a[], int n)
{
if (n <= 0)
return -1;
int start = 0;
int end = n-1;
while(a[start] > a[end])
{
int mid = (start+end)/2;
if (a[mid] > a[end])
start = mid+1;
else
end = mid;
}
return start;
}``````

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.