Amazon Interview Question SDE1s
Country: India
If the number we're looking for has duplicates, should we return its first occurrence? If so, first thing we need to do is select the correct data structure for this problem, if the array wouldn't be rotated, just sorted, everyone could get to the answer quickly: binary search, that's it. But that's not the case, for this problem I think all we need is a Hash Table, which allows us to find an element very quick, and so its index.
Yes, I know, but either way we cannot use binary search since the array is not completely sorted. So what would be the best approach to this problem? Please guys, don't just publish the code, but also the logic. Thanks
It is sorted, just rotated. Cut the array in half which results in two sets; Set A and Set B. Note that one of the sets will be sorted and the other will not be.
If the number we want is in the sorted set, then we can focus on that set and handle it normally.
If the number is in the unsorted set, then we just have to cut it in half again.
Then repeat the steps over and over until you have your answer. Eventually you are going to end up having the number you want in the sorted set.
This should be O(log(n))
{{
int p[] = {20,30,30,45,60,60,5,17,17,19};
int item = 30; //index of item in the above array is 4 starting from 0
int indexOfItem = -1;
int startIndex = -1;
int length = sizeof(p)/sizeof(p[0]);
bool found = false;
for(int i=0;i<length;i++)
{
if(p[i] == item)
{
if(!found)
{
indexOfItem = i;
found = true;
}
}
if(i+1<length)
{
if(p[i]>p[i+1])
{
startIndex = i+1;
}
}
}
if(indexOfItem>=startIndex)
{
cout<<"Actual Index of the item = "<<indexOfItem-startIndex<<endl;
}
else
{
cout<<"Actual Index of item = "<<indexOfItem+length%startIndex<<endl;
}
}}
I think the solution is still possible by binary search
Step 1. Do a binary search type traversal to determine the array index where the rotation has happened (just a bit tricky).
Step 2. Compare the key with the value at the index of rotation. This indicates in which half we would find the key. Do a binary search in that half to find the index of that key.
Complexity: O(log n)
package gao.zone.study;
import static org.junit.Assert.*;
import java.util.Arrays;
/**
* On a very large rotated sorted array with one or more duplicates, find the
* index of a particular number: 20,30,30,45,60,60,5,17,17,19
* */
public class SearchInRotatedSortedArray {
public static void main(String[] args) {
int[] nums = { 20, 30, 30, 45, 60, 60, 5, 17, 17, 19 };
for (int n : nums) {
int index = findIndex(nums, n);
assertTrue(index >= 0);
assertEquals(n, nums[index]);
}
assertTrue(findIndex(nums, 15) < 0);
assertTrue(findIndex(nums, 25) < 0);
assertTrue(findIndex(nums, 35) < 0);
assertTrue(findIndex(nums, 55) < 0);
assertTrue(findIndex(nums, 65) < 0);
}
private static int findIndex(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (arr[low] <= arr[mid]) {
// left part continues.
if (arr[low] <= key && arr[mid] >= key) {
// key in range low~mid.
return Arrays.binarySearch(arr, low, mid + 1, key);
}
// key in range mid~high.
low = mid + 1;
continue;
}
if (arr[mid] <= arr[high]) {
// right part continues.
if (arr[mid] <= key && arr[high] >= key) {
// key in range mid~high
return Arrays.binarySearch(arr, mid, high + 1, key);
}
// key in range low~high.
high = mid - 1;
}
}
return -(low + 1);
}
}
This is simply returning the current position of the elements in the array, for example for 30 will return 2, which is also false, this because Arryays.binarySearch does not guarantee the first element, will return just an index for the existing element, in this case will return 2 instead of 1. both index 1 and 2 contains the element.
Also the result we need as output is 1(first app of 30)+ 10 (sizeOfArray) - 6(position of smallest element which is 5) -> result is index 5.
Am i saying something wrong here?
Here is an update with my version, modification on yours, i used the method findIndex() to find the index of the min value also, the are 2 special cases when the min is at the beginning or at the end. Tried with 4 diff arrays, worked as expected.
Code is bellow.
package problems.searchs;
import java.util.Arrays;
/**
* On a very large rotated sorted array with one or more duplicates, find the
* index of a particular number: 20,30,30,45,60,60,5,17,17,19
* */
public class RotatedSortedArray {
public static void main(String[] args) {
// for all 4 variant of arrays the result for input 30 will be 6
int[] nums = { 20, 30, 30, 45, 60, 60, 5, 17, 17, 19 };
// int[] nums = { 5, 17, 17, 19, 20, 30, 30, 45, 60, 60 };
// int[] nums = { 20, 30, 30, 45, 60, 60, 70, 76, 80, 5, 17, 17, 19 };
// int[] nums = { 17, 17, 19, 20, 25, 30, 45, 60, 60, 5 };
int minElementPosition = findIndex(nums, Integer.MIN_VALUE);
if (minElementPosition > 0) {
// this is for the case when the list is actually sorted (case 2
// commented, when 5 is at position 0.
if (nums[minElementPosition - 1] <= nums[minElementPosition]
&& minElementPosition == nums.length - 1) {
minElementPosition = 0;
}
}
int input = 30;
int index = findIndex(nums, input);
if (nums[index] != input) {
System.out.println("Number " + input
+ " was not found in the array.");
} else {
// (can be more solutions - this is a valid one, diff made by
// Arrays.binarySearch(..), 5 and 6 are both solutions for input 30
int rotation;
if (minElementPosition > index) {
rotation = nums.length - minElementPosition;
} else {
rotation = -minElementPosition;
}
System.out.println("The searched number can be found at index "
+ (index + rotation));
}
}
private static int findIndex(int[] arr, int key) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
if (arr[low] <= arr[mid]) {
// left part continues.
if (arr[low] <= key && arr[mid] >= key) {
// key in range low~mid.
return Arrays.binarySearch(arr, low, mid + 1, key);
}
// key in range mid~high.
low = mid + 1;
continue;
}
if (arr[mid] <= arr[high]) {
// right part continues.
if (arr[mid] <= key && arr[high] >= key) {
// key in range mid~high
return Arrays.binarySearch(arr, mid, high + 1, key);
}
// key in range low~high.
high = mid - 1;
}
}
return high;
}
}
static int findRotatedArrayIndex(int n , int[] arr) {
int st = 0;
int end = arr.length;
while(st <= end) {
int mid = (st + end)/2;
if(n == arr[mid])
return mid;
if(arr[mid] > arr[st]) {
if(n < arr[mid] && arr[st] < n) {
end = mid - 1;
}
else
st = mid + 1;
}
else {
if(arr[mid]<n && arr[end] > n) {
st = mid + 1;
}
else
end = mid -1;
}
}
return -1;
}
- zhezhaoxu August 27, 2014// binary search int findIndex(int n, int a[], int len) { int lo = 0; int hi = len - 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (a[mid] == n) { return mid; } if (a[mid] >= a[lo]) { if (n < a[mid]) { if (n >= a[lo]) { hi = mid - 1; } else { lo = mid + 1; } } else { lo = mid + 1; } } else { if (n > a[mid]) { if (n < a[lo]) { lo = mid + 1; } else { hi = mid - 1; } } else { hi = mid - 1; } } } return -1; }