Amazon Interview Question
Software Engineer / DevelopersTeam: Kindle
Country: India
Interview Type: Phone Interview
@Kyle: Its a good solution. but in step 1 instead of progressing in log(i) to the base 2, you could take base 10. You will reach the end sooner. i.e. 10^1, 10^2..... Assume the number you are searching is in a 1000,000
@Mani - Correct powers of 10 would work also but, I chose base 2 because it allows you to use the shift operator instead, and if you have to worry about overflow you'll be able to index the largest number possible.
Slight adjustment should probably be 2^1-1, 2^2-1, ..., 2^32-1, ... This way you'll be able to check the top end, otherwise you'll over flow and miss the last 2^xx range.
1. Binary search - to find the number
2. To find the last index of the number, traverse till the next number changes
3. Return the index
1. We do not know the length of the array.
2. your solution is of O(n). It can be solved in o(log n)
@Rahul
Doing a binary search is n log n
and finding the last occurrence of the number is negligible
how my solution is O(n), can you please explain?
@Rahul
Doing a binary search is log n
and finding the last occurrence of the number is negligible
how my solution is O(n), can you please explain?
Consider the cases when array is filled up with 10^9 5's and you are searching for 5.
In fact- the case when all the elements are same (say, 'a') and you are searching for 'a'.
Your approach will be O(N).
Input is in sorted order
As per my knowledge, in binary search we do compare first element, middle element and last element.
So if they are same then we can have special case to find it in O(1)
What do you say?
Hmm... But what about the case when all but the first and the last entry are same!
[2 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 7]
Again your approach is O(N).
Hint: For searching element 'k', think of *binary-searching* for consecutive position:
[ Y, i ] and position [ j, Z ] where, A[Y] < k, A[Z] > k and A[i] == A[j] == k
Algorithm:
* Initialize lo to 0, hi to 1.
* Do hi = hi * 2 while data[hi] <= x
* Then do binary search between lo and hi for the first element greater than x
The best tutorial on binary search I ever read is on TopCoder (search in google with "topcoder" and "binary search" keywords - can't do links here)
int findLastOccurrence(int[] arr, int num){
int i = 0;
int index = 0;
while(arr[index] <= num) {
index = 1 << i;
++i;
}
int left = index/2 ;
int right = index;
while(left < right){
int mid = (left + right)/2;
if(arr[mid] == num){
if( (arr[mid + 1] )!=num){
return mid;
}else{
left = mid + 1;
}
}else if(arr[mid] < num){
left = mid + 1;
}else{
right = mid - 1;
}
}
Small Error in the line 13 (13th line of code)
if( (arr[mid] + 1)!=num) ==> if( (arr[mid + 1])!=num)
Let me know if it works !
int function(int a[],int size,int key)
{
int mid,first=0,last = size-1,index;
mid = (first+last)/2;
while(first < last)
{
if(a[mid] == key)
{
while(mid < last)
{
if(a[mid] == key)
{
index = mid;
mid++;
}
else
return index;
}
}
else if(a[mid] < key)
first = mid+1;
else
last = mid-1;
mid = (first+last)/2;
}
return 0;
}
Apply binary search repeatedly until the match is not found.
int find_last_occurance(int key, int *p , int length)
{
int start_index = -1;
int last_index = -1;
int end_index = length -1;
while(1){
printf(">>>> starting the search in array [%d .. %d] <<< \n",start_index+1,end_index);
start_index = search(key,p,start_index+1 , end_index);
if(start_index == -1){
return last_index;
} else {
last_index = start_index;
}
}
}
Everyone here has answered assuming its finite series and you know the length.
Since questions says it's infinite series , binary search is not a possibility. If it is infinite series and sorted then O(n) is the best solution I can think of. But even brute force answer leads to O(n) only.
public class indexvaluereturn
{
static int[] b = new int[15];
static public int count;
public int i,j,k;
public int indexreturn(int x){
int[] a = {1,2,2,3,3,3,4,6,6,6,6,6,8};
int length = a.length;
for(j=0;j<length;j++){
if(a[j]==x)
k = j;
}
System.out.println(k);
return 0;
}
public static void main(String argp[]){
indexvaluereturn k = new indexvaluereturn();
k.indexreturn(3);
}
}
#include <iostream>
using namespace std;
int getLastIndex(char *inputNumbers,int number)
{
int sortedArray[9]={0};
char strNumber[2];
int count = 0;
while(*inputNumbers)
{
memset(strNumber,'\0',2);
strncpy(strNumber,(const char *)inputNumbers,(size_t)1);
int value = atoi(strNumber);
sortedArray[value]=count;
inputNumbers++;
count++;
}
return sortedArray[number];
}
int main(int argc, char *argv[])
{
char inputNumbers[256]={0};
int number = 0;
cout<<"Enter the Sequence of Number in sorted manner (E.g. 1223344556666) : ";
cin>>inputNumbers;
cout<<"Enter the number to check the index from above sequence : ";
cin>>number;
int indexLocation = getLastIndex(inputNumbers,number);
cout<<"The last index location : "<<indexLocation<<endl;
exit(0);
}
A very dirty implementation written in C, but keeps the O(logn) efficiency.
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/*
There is a sorted array of infinite numbers (can contain duplicates).
Given a number. Find the last occurring instance of that number
in the array.
*/
int find_last(int* a, int size, int num)
{
int pos = 0;
int power = 1;
while(pos <= size)
{
// check if we found the number
if (a[pos] == num)
break;
// check if we passed the number
if (a[pos] > num)
{
pos = pow(2, power-1);
break;
}
// if we're not there yet, make a step
power++;
pos = pow(2, power);
}
// now, where did we leave off...
// if we didn't find the number yet,
// do a little binary search
if (a[pos] != num || pos > size)
{
int l, r;
if (pos > size)
{
l = pow(2, power-1);
r = size;
}
else
{
l = pos;
r = pow(2, power);
if (r > size)
r = size;
}
int mid = l + (r - l)/2;
// lets loop until we find the number
while (1)
{
mid = l + (r - l)/2;
// take care of corner cases
if (a[l] == num)
{
pos = l;
break;
}
else if (a[r] == num)
{
pos = r;
break;
}
else if (a[mid] == num)
{
pos = mid;
break;
}
// too far?
if (num > a[mid])
l = mid;
// not far enough?
else if (num < a[mid])
r = mid;
// i guess we didn't find what we came for...
if (l+1 == r && a[l] != num && a[r] != num)
return -1;
}
}
// by now we should have found our number,
// lets find the last occurence
while (a[pos+1] == num && pos <= size)
pos++;
return pos;
}
int main()
{
int array[] = {0, 1, 1, 2, 3, 4, 4, 5, 6, 7, 8};
int size = (int)(sizeof(array)/sizeof(int));
int location = find_last(array, size-1, 4);
printf("location: %d\n", location);
}
After reading all the comments, I feel the answer is not perfect!
Point to be noted here is that the input is unlimited. There is no end to it, say you are reading a stream of data from some source. So finding the end (whether actual end or where the number becomes greater than what we were searching for), is not possible. Hence, we cannot apply binary search directly!
I suggest the following solution:
1. Take i=0
2. If 2^i <= key && 2^(i+1) > key, then we have found the range, else increment i.
3. Once the range is found (say indexes r1 and r2), there are two conditions that are possible
a. value at r1 == key, or
b. value at r1 is less than key.
if condition a then,
we can do a binary search* to find the last index of the key.
if condition b then,
we can do a binary search to find some index of key (to make it like condition a)
and then do a binary search* to find the last index.
Note: binary search* => a modified version of binary search where we find the index of input change, to find the last index.
I think this will cover the all the cases of input and give a O(log n) solution. If I am missing anything or have made a mistake, please leave a comment.
1) Use Binary search to get index of the first occurrence of x in arr[]. Let the index of the first occurrence be i.
2) Use Binary search to get index of the last occurrence of x in arr[]. Let the index of the last occurrence be j.
3) Return (j – i + 1);
/* if x is present in arr[] then returns the count of occurrences of x,
otherwise returns -1. */
int count(int arr[], int x, int n)
{
int i; // index of first occurrence of x in arr[0..n-1]
int j; // index of last occurrence of x in arr[0..n-1]
/* get the index of first occurrence of x */
i = first(arr, 0, n-1, x, n);
/* If x doesn't exist in arr[] then return -1 */
if(i == -1)
return i;
/* Else get the index of last occurrence of x. Note that we
are only looking in the subarray after first occurrence */
j = last(arr, i, n-1, x, n);
/* return count */
return j-i+1;
}
/* if x is present in arr[] then returns the index of FIRST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int first(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == 0 || x > arr[mid-1]) && arr[mid] == x)
return mid;
else if(x > arr[mid])
return first(arr, (mid + 1), high, x, n);
else
return first(arr, low, (mid -1), x, n);
}
return -1;
}
/* if x is present in arr[] then returns the index of LAST occurrence
of x in arr[0..n-1], otherwise returns -1 */
int last(int arr[], int low, int high, int x, int n)
{
if(high >= low)
{
int mid = (low + high)/2; /*low + (high - low)/2;*/
if( ( mid == n-1 || x < arr[mid+1]) && arr[mid] == x )
return mid;
else if(x < arr[mid])
return last(arr, low, (mid -1), x, n);
else
return last(arr, (mid + 1), high, x, n);
}
return -1;
}
/* driver program to test above functions */
int main()
{
int arr[] = {1, 2, 2, 3, 3, 3, 3};
int x = 3; // Element to be counted in arr[]
int n = sizeof(arr)/sizeof(arr[0]);
int c = count(arr, x, n);
printf(" %d occurs %d times ", x, c);
getchar();
return 0;
}
Scala:
def lastRecurringInstance(xs: Array[Int], i: Int, currIdx: Int, idx: Int): Int = xs match {
case Array() => idx
case Array(x, y@_*) if(x > i) => idx
case Array(x, y@_*) if(x == i) => lastRecurringInstance(y.toArray, i, currIdx+1, currIdx)
case Array(x, y@_*) if(x < i) => lastRecurringInstance(y.toArray, i, currIdx+1, idx)
}
Since the array is 'unlimited' in size we need to find a valid 'end' before we start searching.
- Kyle November 21, 20121. Find an end (check 2^1,2^1,2^2,2^3...) if it's bigger than the number searched or you get an exception that's your end.
2. Do a binary search range 2^(i-1) - 2^i for your number when you find the value save the index but keep searching via binary search. Cover examples like [1,2,(100,000 2's), 3,4,5,..................]
3. When your finished with all binary searches in the found range the last seen index is the largest location of that number.