Amazon Interview Question
Software Engineer / DevelopersCountry: 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