## Amazon Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**Phone Interview

This could be sollution whith O(logn) efficency

```
public static int SearchRotatedSortedArray(int l, int d, int[] array, int toFind) {
if (l >= d) {
return -1;
}
if (array[l] == toFind) {
return l;
}
if (array[d] == toFind) {
return d;
}
int mid = (l + d) / 2;
if (array[mid] == toFind) {
return mid;
}
if ((array[mid] > toFind && toFind > array[l]) || (array[mid] < toFind && array[d] < toFind)) {
return SearchRotatedSortedArray(l, mid - 1, array, toFind);
} else {
return SearchRotatedSortedArray(mid + 1, d, array, toFind);
}
}
```

public class RotatedSortedArray {

static int findMin(int arr[], int low, int high) {

if (high == low) return low;

if (high < low) return low;

int mid = low + (high - low) / 2;

if (arr[mid + 1] < arr[mid] && high > mid) {

return mid + 1;

}

if (arr[mid - 1] > arr[mid] && mid > low) {

return mid;

}

if (arr[high] > arr[mid]) {

return findMin(arr, low, mid);

} else {

return findMin(arr, mid, high);

}

}

static int findPosRotatedArray(int arr[], int low, int high, int num) {

int pos = findMin(arr, low, high);

if (arr[pos] < num && num > arr[high]) {

return binarySearch(arr, num, pos - 1, low);

} else {

return binarySearch(arr, num, high, pos);

}

}

static int binarySearch(int arr[], int num, int high, int low) {

if (high < low) {

return -1;

}

int mid = low + (high - low) / 2;

if (num == arr[mid]) {

return mid;

} else if (num > arr[mid]) {

return binarySearch(arr, num, high, mid + 1);

} else {

return binarySearch(arr, num, mid - 1, low);

}

}

public static void main(String[] args) {

int arr1[] = {5, 6, -2, -1, 1, 2, 3, 4};

System.out.println(findMin(arr1, 0, arr1.length - 1));

System.out.println(findPosRotatedArray(arr1, 0, arr1.length - 1, 2));

}

}

```
package algorithms.sorting;
import java.util.Arrays;
public class P2 {
public static void main(String[] args) {
Integer[] words = new Integer[]{
5, 6, -2, -1, 1, 2, 3, 4
};
int foundIndex = findElement(words, -2);
if(foundIndex == -1) {
System.out.println("Not Found");
}
else {
System.out.println("Found at : " + String.valueOf(foundIndex) + " : Word : " + words[foundIndex]);
}
}
private static int findElement(Integer[] words, Integer element) {
int mid = words.length / 2;
if(words[mid].equals(element)) {
return mid;
}
if(words.length == 1) {
return -1;
}
if(words[mid] > element && (words[mid] < words[0] || element > words[0])) {
return findElement(Arrays.copyOfRange(words, 0, mid), element);
}
else {
return findElement(Arrays.copyOfRange(words, mid + 1, words.length), element);
}
}
}
```

We can do this using the binary search approach as following:

- Joe April 18, 2017