A part of techInterview.org: answers to technical interview questions.
Your host: Michael Pryor
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.
The longest sub sequence that satisfies the problem is the input itself
The longest sub sequence that satisfies the problem is 110100
(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
Wednesday, June 16, 2010
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.
Thursday, June 17, 2010
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.
Space complexity:O(1) as we have used only three variables.
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
I think http://discuss.techinterview.org/default.asp?interview.11.792102.31 gives the answer at last.. right?
This topic is archived. No further replies will be accepted.Other recent topics
Powered by FogBugz