techInterview Discussion

A part of techInterview.org: answers to technical interview questions.

Your host: Michael Pryor

Amazon Problem about BitArray

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
d Send private email
Tuesday, June 15, 2010
 
 
Previously: http://discuss.techinterview.org/default.asp?interview.11.792102.31

(No one found an answer. Also, awesome software Joel.)
d Send private email
Tuesday, June 15, 2010
 
 
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
d
Wednesday, June 16, 2010
 
 
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.
Yaxiong Zhao Send private email
Wednesday, June 16, 2010
 
 
>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).
d Send private email
Wednesday, June 16, 2010
 
 
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.
Yaxiong Zhao
Thursday, June 17, 2010
 
 
So what's the answer
Ra Send private email
Sunday, June 27, 2010
 
 
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.
d Send private email
Sunday, June 27, 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.

Time Complexity:O(n)
Space complexity:O(1) as we have used only three variables.
Sarthak Dash Send private email
Thursday, July 01, 2010
 
 
110
d Send private email
Thursday, July 01, 2010
 
 
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
Xiaoyong Feng Send private email
Monday, July 05, 2010
 
 
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.
d Send private email
Monday, July 05, 2010
 
 
noob Send private email
Monday, July 19, 2010
 
 

This topic is archived. No further replies will be accepted.

Other recent topics Other recent topics
 
Powered by FogBugz