Amazon Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
How about val == arr[mid] case? You can't cut either 1st or 2nd half, e.g. {0,1,2,2,2,2,2,2,3} and locate 2.
this should solve it
int finder(int arr[], int start, int end, int val)
{
int mid=(end-start)/2+start;
if(start==end)
{
if(arr[start]==val)
return start;
else
return -1;
}
//is first half sorted?
if(arr[start]<= arr[mid]){
if(arr[start]<= val && val<=arr[mid])
return finder(arr, start, mid, val);
else{
int x = finder(arr, mid+1, end, val);
if(x>-1)
return x;
else
return finder(arr, start, mid, val);
}
}
else //the second half of array is sorted
{
if(arr[mid+1]<= val && val<=arr[end])
return finder(arr, mid+1, end, val);
else{
int x = finder(arr, start, mid, val);
if(x>-1)
return x;
else
return finder(arr, mid+1, end, val);
}
}
}
public static int findIndexB(int arr[] ,int start,int end,int val){
int mid = (end + start)/2;
if(start == end){
if (arr[start] == val )
return start;
else
return -1;
}
if( val <= arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndexB(arr,mid+1,end,val);
}
public static int findIndex(int arr[], int start, int end, int val)
{
int mid=(end+start)/2;
if(start==end)
{
if(arr[start]==val)
return start;
else
return -1;
}
//is first half sorted?
if(arr[start]<= arr[mid])
{
if(arr[start]<= val && val<=arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndex(arr, mid+1, end, val);
}
else //the second half of array is sorted
{
if(arr[mid+1]<= val && val<=arr[end])
return findIndexB(arr, mid+1, end, val);
else
return findIndex(arr, start, mid, val);
}
}
9, 9, 9, 8, 10, << input you posted is not sorted.
Can we assume that array was already sorted and then this was rotated to the right by a certain distance?
It is. Originally you have an array {1,2,3,3,9,9,9,8,10,12,13}, and it's then rotated right by 9, so it becomes {3, 9, 9, 9, 8, 10, 12, 13, 1, 2, 3} (the first element from the original array, is moved to index 9, generally new_index = (original_index + 9) % array_size.
Take a single pass through to find both the rotation point (assume non-zero rotation) and the first index of the value, and the total length.
If the first index is after the rotation point, subtract the rotation point.
If the first index is before the rotation point, add the index to the total length minus the rotation.
#!/usr/bin/env python
def find_index(elements, value):
rotation = 0
first = -1
max = 0
length = 0
for i, val in enumerate(elements):
length += 1
if rotation == 0 and max > val:
rotation = i
else:
max = val
if first == -1 and value == val:
first = i
elif rotation != -1 and value == val:
return i - rotation
return length - rotation + first
if __name__ == '__main__':
print find_index([3,8,9,9,9,10,12,13,1,2,3], 3)
This prints out 2 (0-indexed).
1. FindIndexes(A, number)
2. if number > A[0]
3. for i=0 to n - 1 && number > A[i]
4. if A[i] == number
5. print i break;
5. else if number < A[0]
6. for i = n-1 down to 0 && number < A[i]
7. if A[i] == number
8. print i break;
9. else
10. print 0
I don't think this handles, say, finding 4 in the list [3, 4, 5, 6, 1, 2, 3] properly. It would return 1, I think, and the correct answer is 4 (original list is [1, 2, 3, 3, 4, 5, 6]. What languages is this btw?
if i am not wrong, question was to find the index after rotation. do we need to find the index before rotation. if that is the case my program doesnt handle. It is not any programming language i just wrote down the algorithm
First - Bring back the original array (un-rotate)
1. find the initial offset (the point of rotation, or first instance of min value) at index, say I - this takes O(n)
2. Divide the array in place - from 0 to I-1 and I to length -1
3. Rotate both arrays (swap first and last) - this takes O(n/2) so O(n)
4. Rotate the final array - still O(n)
Search -
1. Use Binary search to find index of any item on the array in step 4 above - O(logn) - say j
2. Add initial offset (I) , this is your final answer - I+j
Time - O(n)
Space - O(1)
public static int findIndexB(int arr[] ,int start,int end,int val){
int mid = (end + start)/2;
if(start == end){
if (arr[start] == val )
return start;
else
return -1;
}
if( val <= arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndexB(arr,mid+1,end,val);
}
public static int findIndex(int arr[], int start, int end, int val)
{
int mid=(end+start)/2;
if(start==end)
{
if(arr[start]==val)
return start;
else
return -1;
}
//is first half sorted?
if(arr[start]<= arr[mid])
{
if(arr[start]<= val && val<=arr[mid])
return findIndexB(arr,start,mid,val);
else
return findIndex(arr, mid+1, end, val);
}
else //the second half of array is sorted
{
if(arr[mid+1]<= val && val<=arr[end])
return findIndexB(arr, mid+1, end, val);
else
return findIndex(arr, start, mid, val);
}
}
int a[] = {3, 8, 9, 9, 9, 10, 12, 13, 1, 2, 3};
int cA = (sizeof(a)/sizeof(*a)), e = 3, ct = 0, ct2 = 0;
int st = -1, st2 = -1;
int k = 0;
for (int i = 0; i < cA; i ++){
if (a[i] == e){
st = i;
break;
}
}
if (st >= 0){
int i = st;
while (a[i] == e){
ct ++;
i ++;
}
if (st == 0){
i = cA - 1;
while (a[i] == e && i > st + ct){
ct2 ++;
st2 = i;
i --;
}
}
}
k = ct + ct2;
int r[k];
for (int i = 0; i < ct; i ++){
r[i] = st + i;
}
for (int i = 0; i < ct2; i ++){
r[ct + i] = st2 + i;
}
for (int i = 0; i < k; i ++){
printf("%d, ", r[i]);
}
int a[] = {3, 8, 9, 9, 9, 10, 12, 13, 1, 2, 3};
int cA = (sizeof(a)/sizeof(*a)), e = 3, ct = 0, ct2 = 0;
int st = -1, st2 = -1;
int k = 0;
for (int i = 0; i < cA; i ++){
if (a[i] == e){
st = i;
break;
}
}
if (st >= 0){
int i = st;
while (a[i] == e){
ct ++;
i ++;
}
if (st == 0){
i = cA - 1;
while (a[i] == e && i > st + ct){
ct2 ++;
st2 = i;
i --;
}
}
}
k = ct + ct2;
int r[k];
for (int i = 0; i < ct; i ++){
r[i] = st + i;
}
for (int i = 0; i < ct2; i ++){
r[ct + i] = st2 + i;
}
for (int i = 0; i < k; i ++){
printf("%d, ", r[i]);
}
public static int FindElement(int[] A, int s, int e, int elem)
{
if (s > e)
return -1;
int mid = s + (e - s) / 2;
if (elem == A[mid])
return mid;
if ((elem < A[mid] && elem >= A[s]) || (elem > A[mid] && elem > A[e]))
return FindElement(A, s, mid - 1, elem);
if ((elem > A[mid] && elem <= A[e]) || (elem < A[mid] && elem < A[s]))
return FindElement(A, mid + 1, e, elem);
return -1;
}
find(start,end,Array,x){
int mid= (start+end)/2;
if(A[start]==x) return start;
if (A[end]==x) return end;
if(end-start <=1) return -1;
if( (A[start]<x && A[mid]<x) || (A[start]>x && A[mid]<x) ) return find(mid,end,A,x);
if( (A[start]<x && A[mid]>=x) || (A[start]>x && A[mid]>=x) ) return find(start,mid,A,x);
}
#include<stdio.h>
#include<conio.h>
int bs(int input[],int data,int low,int high)
{
int mid;
if(low > high)
return -1;
if (low==high && input[low]==data)
return low;
mid = low+ (high-low)/2;
if( input[mid]==data)
return mid;
else if( input[low] <= input[mid-1] )
{
if(data >= input[low] && data <= input[mid-1])
return bs(input,data,low,mid-1);
else
return bs(input,data,mid+1,high);
}
else
{
if(data >= input[mid+1] && data <= input[high])
return bs(input,data,mid+1,high);
else
return bs(input,data,low,mid-1);
}
}
int main()
{
int input[]={3, 9, 9, 9, 10, 10, 12, 13, 1, 2, 3};
int no;
int searchData;
no = sizeof(input)/sizeof(int);
printf("Enter data : ");
scanf("%d",&searchData);
printf("Found at %d",bs(input,searchData,0,no-1));
getch();
}
Algorithm: As the pattern of array is Increasing sorted Order and at any point there will be small element and again it starts Increasing in Sorted Order.
We could find the break in Sorted array pattern using Custom Binary Search with logic as comparing 3 number pattern if increasing sorted order is maintained.
Now once the break is found we could check in both halves using Binary Search.
Algorithm: As the pattern of array is Increasing sorted Order and at any point there will be small element and again it starts Increasing in Sorted Order.
We could find the break in Sorted array pattern using Custom Binary Search with logic as comparing 3 number pattern if increasing sorted order is maintained.
Now once the break is found we could check in both halves using Binary Search.
I found a very interesting solution to this problem. I guess its the logic that matters :
int getMidBSearch(int[] arr,int lb,int ub,int oldMid) {
if(lb>=ub)
{
System.out.println("returning : "+(lb));
return lb+1;
}
else
{
int newMid=(lb+ub)/2;
if(arr[lb]<arr[newMid] && arr[oldMid]<arr[newMid])
{
lb=newMid;
}
else
{
ub=newMid;
}
getMidBSearch(arr, lb, ub,newMid);
}
}
Call the above method like : int n = getMidBSearch(a, lb, ub,0);
This will divide the array into two non-equal parts and we will get the two sorted lists, one goes from 0..n and another from n+1...arr.length-1. Then,
1. Check if element to be searched lies in list one or 2nd
2. Based on point#1, call a binary search again (Since we have two sorted lists now)
A binary search is performed twice - once to find the index from where the two lists are divided, and another time to find the element in the list.
Please let me know your comments on this.
Binary Search O(lg(N)) solution:
int BinarySearch(vector<long> source, int toSearch)
{
int lower, middle, upper;
lower = 0;
upper = source.size() - 1;
while (lower <= upper) {
middle = lower + (upper - lower) / 2 + (upper - lower) % 2;
if (toSearch == source[middle])
return middle;
else if (toSearch == source[lower])
return lower;
else if (toSearch == source[upper])
return upper;
else if (source[lower] <= source[middle]) {
// 15 16 19 20 25 30 1 3 4 5 7 10 14
// L M U
// 4 8 9 9 9 10 12 13 1 2 2 3
// L M U
if (toSearch > source[middle]) // Ex: toSearch>30; toSearch=13
lower = middle + 1;
else if (toSearch > source[lower]) // Ex: toSearch=20; toSearch=9
upper = middle - 1;
else // Ex: toSearch=5; toSearch=2
lower = middle + 1;
} else { // Middle < Lower
// 15 16 19 20 25 30 1 3 4 5 7 10 11 14
// L M U
// 4 8 9 9 9 10 12 13 1 2 2 3
// L M U
if (toSearch < source[middle]) // Ex: toSearch=1
upper = middle - 1;
else if (toSearch < source[upper]) // Ex: toSearch=10; toSearch=2
lower = middle + 1;
else // Ex: toSearch=20; toSearch=12
upper = middle - 1;
}
}
return -1;
}
forget the first two lines
you are left with what actually is the question
You just have have index the element in array
Probably be it with a quick sort search
public int indexFun(int[] arr, int start, int end, int number)
{
if(arr[start] == number)
{
return start;
}
if(arr[end] == number)
{
return end;
}
if(start == end)
{
return -1;
}
int mid = ( start + end ) / 2;
if((arr[mid]<=arr[start] && (number<=arr[mid]|| number>=arr[start]))||
(arr[mid]>=arr[start] && number>=arr[start] && number <=arr[mid]))
{
return indexFun(arr, start, mid, number);
}
else
{
return indexFun(arr, mid+1, end, number);
}
}
How does this account for rotation?
I tried it with input 3,4,5,1,2,3,3,3,3. The correct answer is 2. I tried this code and it returned 0.
Still returns 0 when I compiled and tested the update. I understand how you might do a quick-sort style solution, but only after unshifting the sorted array. See my Python example of making a single linear pass for what I think solves it in O(n). O(log N) might be possible but only after unshifting, I think, so I suspect O(n) is the most efficient.
Binary Search (sorta)
Start in the middle of the array, since this is sorter and rotated one half of the array MUST be completely sorted; the other half we have no clue. To test which half is the sorted half, check if the beginning of the array is less than the middle value; if so then this is the sorted half, and check if the search value is between the first element and the middle element. If so, recurse on this half of the array, else recurse on the the other half.
Now if it turns out the second half is the sorted half, test if the value to are looking for is between the middle value and the last value. If it is, recurse on this half, else the other. Continue until you find what you are looking for.
Now since at every step you are tossing half the array you are doing a binary search aka O(log N)
Now I didn't take time to debug this...but it gives my general approach
- Anonymous August 04, 2014