Interview Question
Country: United States
This solution could have been much better if you take
vector<char> sequence.
and, apply binary search on it.
Then it will be O(logN)
The question is vague.. What do you mean by an array of 0s and 1s of UNKNOWN size? If I am to write a method to implement the required functionality, I would have to pass the given array as argument and if I am a java coder array.length should simply give me the size.
I am guessing a stream on 0s and 1s would make more sense here, in which case even using a Vector may not be the best of solutions as the size of the data stream could eat up all the main memory crashing our program..
And that is precisely the reason you were never clear a Google interview my Dear. You need to treat the question as it is, stop talking things like I will pass to a function and array.length etc etc. Talk like someone who knows how to implement his own Algorithm.
#include <string>
#include <iostream>
using namespace std;
int main()
{
size_t sz = 0;
char sequence_1[] = {'0', '0', '0', '0', '0', '0', '1', '1', '1', '1'};
char sequence_2[] = {'1', '1', '1', '0', '0', '0', '0'};
char sequence_3[] = {'0', '0', '0' ,'0'};
//case 1
string seq = string(sequence_1);
sz = seq.find_first_of('1');
if(sz != std::string::npos)
cout<<"Occurence of 1 in sequence array 1 : "<<sz<<"\n";
else
cout<<"1 not found in sequence array 1!!\n";
//case 2
seq = string(sequence_2);
sz = seq.find_first_of('1');
if(sz != std::string::npos)
cout<<"Occurence of 1 in sequence array 2 : "<<sz <<"\n";
else
cout<<"1 not found in sequence array 2!!\n";
//case 3
seq = string(sequence_3);
sz = seq.find_first_of('1');
if(sz != std::string::npos)
cout<<"Occurence of 1 in sequence array 3 : "<<sz<<"\n";
else
cout<<"1 not found in sequence array 3!!\n";
return 0;
}
Output:
Occurence of 1 in sequence array 1 : 6
Occurence of 1 in sequence array 2 : 0
1 not found in sequence array 3!!
Read the program carefully -
1. Array is mentioned as unknown size
2. Since it is just a sorted sequence of 0 and 1, why to waste more memory, so char array is fine
3. Write if more confusion is there?
If it uses linear search what's the big deal in that question ?? You will do it on O(N) complexity. My solution will do in less searches. May be there is a better solution as well. Let's wait and see :-)
Your solution will also do in O(N). How??
Lets consider worst case, in first iteration O(n/2) and then in linear search it is O(n/2).
Final = O(n/2) + O(n/2) = O(n)
and, even O(n/2) is O(n) but i wrote O(n/2) just to explain. Plus, in your solution ... how are you checking if array is finished in case if there is no 1 in the array.
Maybe there will be better solution than these two. Let me think more.
I am intentionally not checking for the end of the array. In case you know the end of the array easy solution is to do a Binary search, isn't it ?
I guess, cleaner and efficient solution would be
1. take vector<char> sequence
2. push as much as 0 and 1 you want to push
3. you can get the size of vector from sequence.size()
4. apply binary_search on the vector
Complexity would be O(logN).
@Abhi : answering to your "I am intentionally not checking for the end of the array. In case you know the end of the array easy solution is to do a Binary search, isn't it ?"
I wanted to say, how many times you will run the loop if you don't have array size?? i mean, how end of array will be identified in your case???
We cannot do it O(log N) ... for log n we need to divide and conquer .. which means you need to divide the given problem into 2 nearly equal sub-problems..
Here we do not know the size of the problem and hence we cannot do a binary search and achieve LogN. in fact you can't even talk about log n since n could possibly be infinity.
What we can do is.
Take a small step. Check for condition.
Take an exponentially larger step. Check for condition.
If condition is true at any step.
Restart the procedings from the previous step.
012345678910111213
00000000000 0 0 0 1 1111111111111111111111111111111111111111111111111111
Step size - 2**0 You land at 1
Step size = 2**1 You land at 2
Step size = 2**2 You land at 4
Step size = 2**3 You land at 12
Step size = 2**4 You land 28 where you get a 1 preceeded by 1 or go out of array.
The reset step size = 1 and start from 12 again.
You land at 13.. There you get the first 1.
Complexity still stays.. O(log m)... m being the postion of the first 1.
..x............x...............................X..o..o..m................................
see the following array.. x is the places we made the comparisons.
since we are making exponentional jumps.. it is safe to say that we will reach the Big X in something nearly equal to log m steps.... then some number of exponential jumps away from m. distance between X and m is not comparable to n and is far less.. so even if we take linear jumps from here we will still be in log m complexity.
there fore complexity is O(log m).
@Abhi, since you don't know the size of the array, when you do A[2^k] might throw an exception. So, here is a better version, with LogN complexity -
1. Keep on looking for A[2^(K-1)] - A[2^K]. If A[2^K] throws an exception, then size of the array is 2^(K-1) to 2^K. Keep on looking from mid = (2^(K-1)+2^K)/2 to 2^K or 2^(K-1) to mid to find the first occurrence of 1. If A[2^K] is 1 and A[2^(K-1)] is 0, then let 2^K = max, 2^(K-1) = min.
2. When the first occurrence of 1 is found using the variation of Binary search above, let min be the index where we found 0, and max be the index where we found 1.
3. Perform a binary search for the string "01'. If the mid is "00", then take right half, and if mid is "11", take left half. Keep on taking halves until you find "01". mid + 1 index will be the solution.
This is better than the vector approach, since the length of array is not known.
My solution is similar to Abhi's except that it recurses with a power of 2 search instead of switching to linear once a 1 is found. I'm not positive but I think it is faster on average case. Complexity should still be log n. Below is an implementation in Python:
import random
def findIndex(L, offset=0, tries=0):
skip, curr, last = 0, 0, 0
while True:
tries = tries + 1
if L[curr] == 1:
if last >= curr - 1:
return offset + curr, tries
return findIndex(L[last:curr], last + offset, tries)
elif curr == len(L) - 1:
return len(L), tries
last = curr
curr = min(len(L) - 1, 2 ** skip)
skip = skip + 1
length = 1000 * 1000 * 100
position = random.randint(0, length)
L = [0] * position
L.extend([1] * (length - position))
print "found position at %s in %s tries" % findIndex(L)
Since the Array is of unknown size you cant use Binary search. Use a variation of it. Assume 1st element is 1, if it is not search for the 2nd element, if that is not 1 search for 4th. Like this you search elements at 1,2,4,8,16,32... location till you find the first 1. Assume you find the first 1 at Kth location than you do a linear search from k/2th location till you find first 1.
- Abhi January 28, 2013