interview Q:Given an input array of size unknown with all 1's in the beginning and 0's in the end. find the index in the array from where 0's start

Question

I was asked the following question in a job interview.

Given an input array of size unknown with all 1's in the beginning and 0's in the end. find the index in the array from where 0's start. consider there are millions of 1's and 0's in the array.i.e array is very big..e.g array contents 1111111.......1100000.........0000000.On later googling the question, I found the question on http://www.careercup.com/question?id=2441 .

The most puzzling thing about this question is if I don't know the size of an array, how do I know if *(array_name + index) belongs to the array?? Even if someone finds an index where value changes from 1 to 0, how can one assert that the index belongs to the array.

The best answer I could find was O(logn) solution where one keeps doubling index till one finds 0. Again what is the guarantee that the particular element belongs to the array.

EDIT: it's a c based array. The constraint is you don't have the index of end elem (can't use sizeof(arr)/sizeof(arr[0])). what if i am at say 1024.arr[1024]==1. arr[2048] is out of bound as array length is 1029(unknown to the programmer). so is it okay to use arr[2048] while finding the solution?It's out of bound and it's value can be anything. So i was wondering that maybe the question is flawed.

Answer 1

If you don't know the length of the array, and can't read past the end of the array (because it might segfault or give you random garbage), then the only thing you can do is start from the beginning and look at each element until you find a zero:

int i = 0;
while (a[i] != 0) i++;
return i;

And you'd better hope there is at least one zero in the array.

If you can find out the length of the array somehow, then a binary search is indeed more efficient.

Ps. If it's a char array, it would be easier and likely faster to just call strlen() on it. The code above is pretty much what strlen() does, except that the standard library implementation is likely to be better optimized for your CPU architecture.

Answer 2

I would go with a Binary Search in order to find the 0.

At first you take the middle, if it is 1 you go in the right side otherwise in the left side. Keep doing this untill you find the first 0.

Now, the problem statement sais that : Given an input array of size unknown with all 1's in the beginning and 0's in the end. The way an Array is represented in the memory is 1 element after another, therefore since you know that there are 0's at the end of the array, if your algorithm works correctly then *(array_name + index) will surely belong to the array.

Edit :

Sorry, I just realised that the solution only works if you know the size. Otherwise, yes doubling the index is the best algorithm that comes to my mind too. But the proof of the fact that the index still belongs to the array is the same.

Edit due to comment:

It states that at the end of the array there are 0's. Therefore If you do a simple

int i;
while(i)
  if( *(array_name+i) != 1 )
       return i;

It should give you the first index, right? Now since you know that the array looks like 1111...000000 you also know that atleast 1 of the 0's and that is the 1st one, surely belongs to the array.

In your case you do the search by doubling the index and then using a binary search between index and index/2. Here you can't be sure if index belongs the the array but the first 0 between index and index/2 surely belongs to the array ( the statement said there is atleast one 0 ).

Uppss... I just realised that if you keep doubling the index and you get out of the array you will find "garbage values" which means that they might not be 0's. So the best thing you can do is instead of checking for the first 0 to be checking for the first element which is not 0. Sadly there can be garbage values with the value of 1 ( extremly small chances but it might happen ). If that's the case you will need to use a O(n) algorithm.

Answer 3

If you don't know the size of the array you can start with index = 1; At each step you check if 2 * index is bigger than the length of the array - if it is or if it is zero - now you have a boundary to start the binary search; otherwise index = 2 * index.