Interview Question


Country: United States




Comment hidden because of low score. Click to expand.
4
of 8 vote

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 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, if you know the length of the Array Binary search gives LogN complexity.

- Abhi January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's why i suggested to use vector<char>. you can know the vector size. And, if you will use C++ standard 11 then even you can use array.

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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..

- teli.vaibhav January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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.

- Anonymous January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

Oh look Mr. Wise Ass poops in.. if you have some technical wisdom then please preach else go fart elsewhere..

- teli.vaibhav January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

#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!!

- Bijendra January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Array is of unknown size ??

find_first() uses linear search ??

- Abhi January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is the Algorithm you have used to search for the first 1 ?

- Abhi January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I guess, find_first_of uses linear search though not fully sure

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 :-)

- Abhi January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ?

- Abhi January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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).

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@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???

- Bijendra January 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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).

- isandesh7 January 31, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I guess, find_first_of uses linear search though not fully sure

- Bijendra January 28, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@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.

- Biru January 29, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Biru : Good answer.

- Abhi January 29, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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)

- trunks7j January 29, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More