Amazon Interview Question Software Engineer / Developers
Country: United States
@ eyeonu.imtiyaaz: Can you please be little more clear on what do you mean by sorted array implemented as ring buffer? Does that mean that the least element can occur at any position and as it's a ring buffer you can traverse starting from the least element position to get the ascending list?
@CodeSpace: What do you mean by 'inversely rotated/half rotated? Can you explain what are you trying to do in those 4 if statement above? Is that a simple binary search that you are doing or have you modified BS for the ring buffer stuff?
I have added some additional comment. This is a regular binary search with modifications to handle a rotated sorted array. e.g {5,4,3,2,1,9,8,7,6}
@The Artist - say the array is of fixed size n. When you are done filling the array from 0 to n-1, the next insertion would take place at the zeroth position. For example, you have array like this -
Values 1 2 3 4 5 6 7 8 9 10
Array Index 0 1 2 3 4 5 6 7 8 9
Now, if values 11, 12 and 13 are inserted, your array would like like -
Values 11 12 13 4 5 6 7 8 9 10
Array Index 0 1 2 3 4 5 6 7 8 9
That being said, the answer to your first question is yes, the least element can occur at any position. For the question about traversal, I mentioned it that we have to keep it less than n, that is, the linear time. So, traversal should be avoided and as CodeSpace mentioned, binary search is the solution with some modification.
int findElement(int [] a, int start, int end, int value)
{
if (start > end)
{
return -1;
}
int mid = (start+end)/2;
if (a[mid]==value)
{
return mid;
}
if (a[mid] >= a[start]) // first half is sorted
{
if (value>=a[start] && value<a[mid])
{
return findElement(a, start, mid-1, value);
}
else
{
return findElement(a, mid+1, end, value);
}
}
else
{
if (value>a[mid] && value<=a[end])
{
return findElement(a, mid+1, end, value);
}
else
{
return findElement(a, start, mid-1, value);
}
}
}
- CodeSpace November 02, 2012Using a modified binary search to find the index of a number within a sorted array. Will return -1 if the index was not found Edge cases: * circular array null or empty * circular array with 1 element * circular array not rotated. e.g {1,2,3,4,5,6,7,8,9} * circular array is inverted. e.g {9,8,7,6,5,4,3,2,1} * circular array half rotated e.g {5,6,7,8,9,1,2,3,4} * number is not in circular array int findIndex(int[] array, int num){ if(array != null && array.length > 0) return(search(array, num, 0, array.length - 1)); return(-1); } int search(int[] array, int num, int start, int end){ int mid = (start + end) / 2; if(array[start] == num) return(start); if(array[end] == num) return(end); if(array[mid] == num) return(mid); if(end - start <= 1) return(-1); if(array[mid] > array[start] && array[start] < num && array[mid] > num) return(search(array, num, start, mid)); if(array[mid] < array[start] && (array[start] > num || array[mid] < num)) return(search(array, num, start, mid)); if(array[mid] < array[end] && array[mid] < num && array[end] > num) return(search(array, num, mid, end)); if(array[mid] > array[end] && (array[mid] > num || array[end] < num)) return(search(array, num, mid, end)); return(-1); }