techInterview Discussion

You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space algorithm to find the maximum sub sequence which has equal number of 1s and 0s.

Examples
1) 10101010
The longest sub sequence that satisfies the problem is the input itself

2)1101000
The longest sub sequence that satisfies the problem is 110100

Previously: http://discuss.techinterview.org/default.asp?interview.11.792102.31

(No one found an answer. Also, awesome software Joel.)

I have seen that posting already.We need to find only the subsequnce,so moving with pointers don't help as I suppose.Bitwise operators may do some trick

I think you should write "sub string" instead of sub sequence.
For sub sequence, just find the min(num(0), num(1)) then reject the excessive 1's or 0's.

>Bitwise operators

One of the things that really annoys me about one of the prevailing styles of interview questions is that they lead people vastly to overrate the importance of bit-twiddling. Is knowing how to bit-twiddle handy? Sure. Is it game-changing w.r.t. efficient algorithms? Usually not, unless the question was specifically chosen to have a bit-twiddling solution (and this one wasn't).

Interviewers need to find a way to "test" or "differentiate" interviewees. Bit twisting questions are good for that end. After all, most of the interview questions are useless in work.

So what's the answer

Sometimes interviewers pose unsolved questions. What else is there to say? Presumably several algorithms experts have thought about it for longer than a typical interview and gotten nowhere.

maintain two variables say count and position. Set both of them to 0. Set MAX to -INFINITY.
Iterate through the list. For every 0 decrement count by 1 and for every 1 increment count by 1. Increment position by 1 whenever you get 1 or a 0.

When count = 0, (it means equal number of 1's and 0's) compare between MAX and position, set MAX to the maximum of MAX & position.

Iterate through the array in this manner and at the end print the array from start till the MAX value.

Time Complexity:O(n)
Space complexity:O(1) as we have used only three variables.

110

I found a O(n) and O(1) solution as below:
1) Define variables m and n represent the start position and end position of the sub sequence we have selected (from the follows example, you will understand what I just said here),  at the beginning, m, n are set as 0

2) Define variable p as the start position of the sub sequence we are examining currently, and c0 and c1 as the number we have found to 0 and 1 respectively in current sub sequence, at the beginning, p, c0 and c1 are set as 0

3) We examine current sub sequence, when we encounter a 0, increment c0, otherwise increment c1, untill c0 = c1;  Then

4) Compare if p (i.e. the start position for current sub sequence) next n (i.e. the end postion for the sub sequence we have selected),  if they are close neighbour, then we can join the 2 sub sequence, i.e. assign the end position of current sub sequence to n;  Otherwise (they are not equal), if the lengh of current sub sequence greater than the selected, then we select current, i.e. assign m and n with the start and end position of current sub sequence (discard the previous selected).
Then reset c0 and c1 as 0

5) Finally, we found the max sub sequence or there is not one

Post some code. I'm pretty sure there's a communication complexity argument that any streaming algorithm (which this is) requires a super-polylogarithmic amount of space.

I think http://discuss.techinterview.org/default.asp?interview.11.792102.31 gives the answer at last.. right?