## Interview Question

Software Engineer Interview*(Student Candidate)* Menlo Park, CA

Answer## Nothing unexpected, I solved all the problems but I think I

was too slow on the first one, which goes like: Given an array of numbers, they are arranged so that the a[0] is in the 1st bucket, a[1]a[2] are in the 2nd bucket, a[3]a[4]a[5] is in the 3rd bucket and so on. The question is then: given a number, you need to return if it is in any bucket or not.

## Interview Answer

7 Answers

Sorry I have missed out something really important about the question.

All the numbers in one bucket are larger than that of the previous bucket.

So ALL numbers of bucket 3 will be bigger than ANY number of the bucket 2 and so on.

The number given to the function may or may not be in the array.

Just find the numbers in the array smaller than the given number. Find the minimum number of buckets that those smaller numbers would fill up, and your given number goes in the next one. Linear time.

Obviously if the number is not in the array at all, then it's not in any of the buckets.

Relation between size of the array and number of buckets. Let n be the array size. Let m + 1 be the number of buckets. In the first bucket, there is one element, in the second bucket, there are 2 elements, ..., in the m-th bucket, there are m element and in the (m+1)-th bucket, there are r elements where 1<=r<=m+1. So we have m(m+1)/2 + r = n. In O notation, we have m = O(sqrt(n)).

Let x be the number we are looking for. We could do a binary search on the buckets. Take the middle bucket. Compare x to all elements in that bucket. If x is one of the element, return true. If x is greater than all elements in that bucket, search for x in the buckets greater than the middle bucket. If x is smaller than all elements in the middle bucket, search for x in the buckets smaller than the middle bucket. If x is smaller than some element and greater than some element, then x cannot be found, return false.

We can refine the binary search by doing a skewed binary search. Instead of taking the middle bucket, we can consider a bucket more towards the right part.

We can use binary search using the last element in each of the buckets to find the smallest element bigger than x which we are looking for.

If we have m = O(sqrt(n)) buckets (see an answer above), then we can find that number in O(logm) time, index of the last element in i-th bucket is i(i+1)/2 -1.

After finding the bucket with properties I've described above it's enough to browse all elements in this and the previous buckets to determine if x is or is not in the whole array (I leave a proof as an exercise).

Because bucket's size is O(sqrt(n)) then the total complexity is O(sqrt(n) + logm) = O(sqrt(n) + logn) = O(sqrt(n)).

This is a better solution than the one above which is O(logn * sqrt(n)) in pesimistic case.

If the numbers in buckets are also sorted, then you can first do a binary search on the first elements of the buckets to find the candidate bucket, and then do another binary search within the bucket. Total complexity O(log(n)).

Find the number using binary search, then you will know the index, say it's i. Using a iteration to calculate which bucket it is in. The trick is: let Bk be the start index of buket k, the recursion is Bk = Bk-1 + k-1, k starts from 1. Base case is B1 = 0. Since k is what you are looking for, you have to build the solution from bottom up, until Bk > i, then A[i] is in the kth bucket. The code looks like:

Bucket(int i){

int k = 1;

int b = 0;

while( b>i)

b += k++;

return k;

}

## Add Answers or Comments

To comment on this, Sign In or Sign Up.

If the number is in a the array, of course the it's in a bucket, right? Perhaps the question is in what bucket? 1st, 2nd,...?