Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
Better formatting:
int rotation_index(const vector<int>& arr, int range_start, int range_end) {
if (arr.size() < 2) return 0;
if (range_end - range_start <= 1) return range_start;
int first = arr[0];
int mid = (range_start+range_end)/2;
int prev_elem = arr[mid];
if (mid < first) return rotation_index(arr, range_start, mid)
else if (mid > first) return rotation_index(arr, mid, range_end);
}
Binary Search based algo.
Java Code
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Arrays;
public class SearchMinIndexInRotatedSortedArray {
public static int search(List<Integer> a,int lo, int hi){
int mid = ( lo + hi) >>> 1;
if( hi - lo == 1){
if(a.get(lo) < a.get(hi))
return lo;
else
return hi;
}
else if( hi == lo){
return hi;
}
if( a.get(lo) <= a.get(mid)){
if( a.get(mid) <= a.get(hi) ){
return lo;
}
else{
return search(a, mid, hi);
}
}
else{
return search(a, lo, mid);
}
}
public static void main(String[] args){
List<Integer> a = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5,6,7,8,9,10));
List<Integer> b = null;
b = new ArrayList<Integer>();
for(int i=0;i< a.size(); i++){
b.clear();
b.addAll(a);
Collections.rotate(b, i);
System.out.println("Searching in: " + b + " index of min: " + search(b, 0, b.size()-1));
}
}
}
Output of above program:
Searching in: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] index of min: 0
Searching in: [10, 1, 2, 3, 4, 5, 6, 7, 8, 9] index of min: 1
Searching in: [9, 10, 1, 2, 3, 4, 5, 6, 7, 8] index of min: 2
Searching in: [8, 9, 10, 1, 2, 3, 4, 5, 6, 7] index of min: 3
Searching in: [7, 8, 9, 10, 1, 2, 3, 4, 5, 6] index of min: 4
Searching in: [6, 7, 8, 9, 10, 1, 2, 3, 4, 5] index of min: 5
Searching in: [5, 6, 7, 8, 9, 10, 1, 2, 3, 4] index of min: 6
Searching in: [4, 5, 6, 7, 8, 9, 10, 1, 2, 3] index of min: 7
Searching in: [3, 4, 5, 6, 7, 8, 9, 10, 1, 2] index of min: 8
Searching in: [2, 3, 4, 5, 6, 7, 8, 9, 10, 1] index of min: 9
int FindIndexOfRotation(int a[],int start,int end)
{
if(start == end-1)
{
if(a[start]<a[end])return start;
return end;
}
int mid=(start+end)>>1;
if(a[start]<a[mid])
{
if(a[start]<a[end])
return start;
else
return FindIndexOfRotation(a,mid,end);
}
else if(a[mid]<a[end])
{
return FindIndexOfRotation(a,start,mid);
}
else
return mid;
}
let me know any bug in this
there will be a problem regarding to your code if an array given like this:
{2, 8, 9, 1 , 2, 2}
public class pivotSearch{
public static void main(String [] args)
{
int []arr={4,5,6,7,8,9,10,11,12,13,1,2,3};
int ind=piv(arr,0,arr.length-1);
int key=10;
System.out.println("The array is pivoted at :"+arr[ind]+" index: "+ind);
System.out.println("The array contains :"+key+" at "+pivotedSearch(arr,key,ind));
}
public static int pivotedSearch(int []data,int key,int pivot)
{
if(data[pivot]==key) return pivot;
else if(key>data[0])
return binSearch(data,key,0,pivot-1);
else
return binSearch(data,key,pivot+1,data.length-1);
}
public static int binSearch(int []data,int key,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;
if(data[mid]==key) return mid;
else if(data[mid]<key) return binSearch(data,key,mid+1,high);
else return binSearch(data,key,low,mid-1);
}
public static int piv(int []data,int low,int high)
{
int mid=(low+high)/2;
if(low>high) return -1;
if(data[mid]>data[mid+1])
{
return mid+1;
}
else if(data[low]>data[high])
{
return piv(data,mid+1,high);
}
else {
return piv(data,low,mid-1);
}
}
}
int FindIndexOfRotation(int a[],int start,int end)
{
if(start == end-1)
{
if(a[start]<a[end])return start;
return end;
}
int mid=(start+end)>>1;
if(a[start]<a[mid])
{
if(a[start]<a[end])
return start;
else
return FindIndexOfRotation(a,mid,end);
}
else if(a[mid]<a[end])
{
return FindIndexOfRotation(a,start,mid);
}
else
return mid;
}
let me know if there is any bug in this
it is sufficient to find the Minimum element of the array as its position tells how many times array is rotated...the code is following
public int rotate(int[] arr){
int min=arr[0];
int i;
for(i=0;i<arr.length;i++){
if(arr[i]<min){
min=arr[i];
}
}
return i;
}
public int rotate(int[] arr){
int min=arr[0];
int i,j;
for(i=0;i<arr.length;i++){
if(arr[i]<min){
min=arr[i];
j=i;
}
}
return j;
}
is so there a truly working solution for O(log n) time and be able to cover the corner cases like: {2, 8, 9, 1, 2, 2} ??
def rotationIndex(a: Array[Int]): Int = {
val len = a.length-1
var curr = 0
val frst = a(0)
var nxt = a(1)
var asc = true
if(frst != nxt){
asc = if(nxt < frst) false else asc
}else {
var i = 1
while(frst == nxt && len >= i){
i = i+1
nxt = a(i)
}
asc = if(nxt < frst) false else asc
}
if(asc){
while(a(curr) < a(curr+1)){
curr = curr+1
}
}else {
while(a(curr) > a(curr+1)){
curr = curr+1
}
}
curr
}
Binary search
- Martin October 06, 2012