## Amazon Interview Question for Software Engineer / Developers

• 1
of 1 vote

Comment hidden because of low score. Click to expand.
3
of 3 vote

Longest subsequence -> any i,j where i!=j

Needs to test every combination of i,j assuming O(1) for each step. Or else, you're not validating the answer at all. Hence O(n) impossible.

O(n^2) is the minimum.

Comment hidden because of low score. Click to expand.
1
of 1 vote

SAT: needs to check every possible assignment for satisfaction, hence O(2^n) is the minimum. WHERE'S MY MILLION DOLLARS?

Comment hidden because of low score. Click to expand.
0
of 0 votes

It is possible to have a solution less than O(n^2).

Comment hidden because of low score. Click to expand.
0
of 0 votes

Write the 0/1 String in your board.
Now your target is to erase some 0 and one such that we have equal number of zero and one left in the board
The remaining number in the board is the "Sequence". Note we are not altering the order and We are not suppose to return a substring
Now question is what to erase and what not ?
Let we have X number of ONE and Y number of Zero.?
If X == Y , Cool ! Equal number of Zero one Found! Ans is Full number
IF X < Y : Less One ! erase (Y-X) Number of Zero anywhere.. Cool: Ans is 2*X
If Y > X: Less Zero! Erase (X-Y) Number of One from the board! Ans is 2*Y

Complexity : O(N)
The code is as below:

``````#define MIN(a,b) ((a < b)?a:b)
int MaximalSubSequenceOfEqualNumberOFZeroOne(int *a, int n){
int countOne=0,countZero=0;
for(int i=0;i    if(a[i]==1) countOne++;
}
countZero = n-countOne;
return 2 * MIN(countZero,countOne);
}

int main(){
int a[]={1,0,1,0,1,0,1,0,0,1,0,0,0};
printf("Ans:%d",MaximalSubSequenceOfEqualNumberOFZeroOne(a,sizeof(a)/sizeof(a)));
}``````

Comment hidden because of low score. Click to expand.
1
of 3 vote

O(n^2) solution s[i] - sum of all numbers from position 0 to position i inclusive

``````Compute s[i] in O(n)
int ans = 0;
for (int i=1; i<n; ++i){
for (int j=0; j<i; ++j){
if ((i-j)%2 == 0) {
if ((s[i]-s[j]) == (i-j)/2){
if (i-j > ans){
ans = i-j;
}
}
}
}
}``````

Please comment. Anyone got something faster?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Stupidest answer :)

Comment hidden because of low score. Click to expand.
0
of 0 votes

``if ((i-j)%2 == 0) {``

Essentially what you're doing in above step is counting if the number of elements between i & j (both inclusive). Shouldn't that be

``(i-j+1)%2 == 0``

Try

``10``

as input. The above code might not give the expected result.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Aren't you calculating only substring with equal 1 and 0. Question asks about sub-sequence.!!

Comment hidden because of low score. Click to expand.
0
of 0 vote

Examples:
10101010
11000000000111
110001
11000100

stored in 0-based array.

Algorithm:
1. Initialize StartIndex = 1, which represents at what index the longest subsequence starts. Initialize 'StopAt" = 0, representing the index you started counting from.
2. Walk through each item in the array left to right.
a) if you see a 1, increment startIndex.
b) if you see a 0, decrement startIndex, with exception.
Exception. If startIndex is StopAt or startIndex > currentIndex, store the StartIndex and the current index-1 (or count) in a List. Reset StopAt to currentIndex and StartIndex to currentIndex + 1.

3. Repeat until you reach the end. When you reach the end, do one final push to the List. If a StartIndex in the list follows an endIndex, merge them two.

The list seems to be necessary to account for a situation like 1100000000111 where an algorithm that simply decrements or increments startIndex would fail.

Not the prettiest algorithm, but it works. I think.

Comment hidden because of low score. Click to expand.
0
of 0 votes

cant understand. seems good.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````// returns an int array representing start and end index of the subsequence.
public int GetLongestSubSequence(bool[] sequence)
{
if (sequence.length < 2) return new int[]{-1,-1};
int startIndex = 1;
int stopAt = 0;
bool firstChar = sequence;
Queue<int> possibleSubSequences = new Queue<int>();

for(i = 1; i < sequence.Length; i++)
{
if (sequence[i] == firstChar)
{
startIndex++;
}
else if (startIndex == stopAt)
{
possibleSubSequences.Enqueue( new int[]{startIndex, i-1});
startIndex = i+1;
stopAt = i;
firstChar = sequence[i];
}
else
{
startIndex--;
}
if (startIndex < i && i == sequence.Length)
{
possibleSubSequences.Enqueue( new int[]{startIndex, i});
}
}
int EndIndex = -1;
StartIndex = -1;
while (possibleSequences.Count > 0)
{
int[] ps = possibleSequences.Dequeue();
if (ps-1 != lastEndIndex)
{
startIndex = ps;
}
endIndex = ps;
}

return new int[]{startIndex, endIndex};

}

}``````

Here's code for it. I simplified it by keeping track of the first bit instead of operating on special casing the '0' case.

Worst case is O(n + n/2) == O(n), represented by string O110011001100110.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Uses Ω(n) space up to log factors.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I doubt if your method works for below input 010010110010

max length begins at 2 and ends at 11 (total length = 10), but I think your approach gives [1,8] - sub optimal solution.

Plz run your code with this input, and plz explain how it is working. I couldn't grasp the last "if" part inside the for() loop. Thanks.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yep, bug in my code. swap the 'if' block with the 'else if' block, and it should work.

Comment hidden because of low score. Click to expand.
0
of 0 votes

After swapping the blocks, this is my trace for 010010110010: for brevity, let x=startindex, y=stopAt, z=firstChar, ps=PossibleSequence.
Values noted are at the end of each iteration of the for loop.

Start
-----------

0. x=1, y=0, z=0, ps=null

for loop begins --
1. x=0, y=0, z=0, ps=null
0. x=3, y=2, z=0, ps={0,1}->null
0. x=4, y=2, z=0, ps={0,1}->null
1. x=3, y=2, z=0, ps={0,1}->null
0. x=4, y=2, z=0, ps={0,1}->null
1. x=3, y=2, z=0, ps={0,1}->null
1. x=2, y=2, z=0, ps={0,1}->null
0. x=9, y=8, z=0, ps={0,1}->{2,7}->null
0. x=10, y=8, z=0, ps={0,1}->{2,7}->null
1. x=9, y=8, z=0, ps={0,1}->{2,7}->null
0. x=10, y=8, z=0, ps={0,1}->{2,7}->null

so, this would return indexes 0,7 which is correct.

The last IF in the FOR is a special case to choose whether to enqueue or not enqueue the last subsequence.

I think the code still stands up with this bug fix. Nice find!

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yeah, I see what you're saying now. even that bug fix doesn't work. optimal is 1,10. rats.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Good effort SomeGuy

Comment hidden because of low score. Click to expand.
0
of 0 votes

Dude, it is not O(1) in space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

my version:
1. count 1s and 0s and get min => 2*min is the length of the subsequence
2. according to min, we can say which digit is less frequent
3. find the first index of the less frequent digit.
4. starting from that index, while min > 0, count 0s and 1s; min--; if #0s = #1s {break;}
5. in general, start index of the subsequence is the start index of the less frequent digit and the last is the current index from step 4. of course, there are some special cases and we have to subtract/add from/to first/current index from step 4.

Comment hidden because of low score. Click to expand.
0
of 0 votes

It's not any convincing algorithm. If you dare to claim your approach works, plz code it, and post it here. I'll find many bugs in your code fore sure :D

Comment hidden because of low score. Click to expand.
0
of 0 votes

No need for arrogance. If you have a good solution, post it instead.

Comment hidden because of low score. Click to expand.
0
of 0 votes

No need for arrogance. If you have a good solution, post it instead.

Comment hidden because of low score. Click to expand.
0
of 0 votes

it looks like my solution does not work for sparse values.
eg.: 1000000000000000001010100000000001
but I think the correct solution can be based on "maximum sum contiguous subsequence problem"...

Comment hidden because of low score. Click to expand.
0
of 0 votes

You are almost there. Let me give the finishing touch.

You should also remember the last index of less frequent digit.

Let me explain algorithm with an example.

100010000101010001001

Count(0) = 14
Count(1) = 7
First index of 1 = 0
Last index of 1 = 20
Last index - First index + 1 = 21 >= 2 * 7=14

Hence, we should find out next range, where we could get optimal solution.

Increment first index until you get next less frequent digit

Decrement last index until you get next less frequent digit

first index = 4
last index = 17

Three options here
21 - 4 + 1 = 18 >= 2 * 6 (you discounted one side)
17 - 0 + 1 = 18 >= 2 * 6 (you discounted one side)
17 - 4 + 1 = 14 < 2 * 5 (you discounted two side)

Now Let's repeat the same with new range
first index = 4
last index = 17

Time complexity is O(n), space complexity is O(1).

Comment hidden because of low score. Click to expand.
0
of 0 votes

RAKESH, that's not an algorithm, and it doesn't lead to one. (In general there are many different combinations of advancing the left and right endpoints.)

Comment hidden because of low score. Click to expand.
0
of 0 votes

No, you always prune your search range and finally gets the solution.

Consider here

Three options here
21 - 4 + 1 = 18 >= 2 * 6 (Move left pointer)
17 - 0 + 1 = 18 >= 2 * 6 (Move right pointer)
17 - 4 + 1 = 14 < 2 * 5 (Move both the pointers)

First one, obviously you won't get solution, because count of 0's and 1's are not equal.

Similarly for second.

Only, by going with third range, you would get the solution.

If at all among the three options, you get more than one valid range, then choose the one with max number of elements.

There are special cases, like with in a range, if count of less frequent digit is more than other

Give me an example, where this solution doesn't work, if you try to prove it.

Comment hidden because of low score. Click to expand.
0
of 0 votes

I've no clue how this sort of range pruning works for this problem! Before designing a solution you should work out with both random and some particular patterns at least.

Try very simple input: 11111100000000000

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) TC and O(1) SC.

No one has done the trick

:(

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````private void findIndex() {
int numOf1 = 0, numOf0 = 0;
int findOccurence, index = 0, lookFor;
for(int i: input){
if(i==0){
numOf0++;
}else{
numOf1++;
}
}
if(numOf0 == numOf1){
System.out.println("sub sequence is "+input.length);
System.exit(0);
}
if (numOf0 > numOf1){
findOccurence = numOf0 - numOf1;
lookFor = 0;
} else {
findOccurence = numOf1 - numOf0;
lookFor = 1;
}
for( int i=input.length-1;i>=0;i--){
if (input[i]==lookFor){
findOccurence--;
if(findOccurence==0){
index=i;
break;
}
} else {
findOccurence++;
}
}
System.out.println("Max sub sequence is "+index);
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Finds the maximum prefix.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes, Once you have the index, loop through the array and print numbers upto the index-1.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Sorry buddy, this doesn't work.
Try with input int [] input = new int[]{0,1,1,1,0,1,0};
Your answer is index = 2 which gives {0,1} as the answer. But the max is {1,0,1,0}

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is not O(1) in space, but is O(n) in time. We maintain an invariant which is difference between number of zero's and one's starting from the index 0, while calculating this we also remember, the max end index of required subsequence if it were to start from any other index i other than 0.

``````package careercup.amazon;

import java.util.HashMap;
import java.util.Map;

class Position {
public Position(int start,int end)
{
this.start = start;
this.end = end;
}
int start, end;
@Override
public String toString()
{
return "start="+start+ " end="+end+"\n";
}
}
class MaxOneZero
{
public static void main(String[] args)
{
String input = "1101000";
Map<Integer, Position> m = new HashMap<Integer, Position>();
int inv = 0;
m.put(0, new Position(0,0));
for (int i =0;i<input.length();i++){
if (input.charAt(i) == '0'){
inv++;
} else {
inv --;
}
if (m.containsKey(inv)){
Position p = m.get(inv);
p.end = i;
} else {
m.put(inv,new Position(i+1,i+1));
}
}
System.out.println("\n"+m);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

even without hashing with O(N) memory you can achieve the solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<iostream>
using namespace std;

void subSeq_1_0(int *ar, int size)
{
int min0=-1;
int min1=-1;
int c1=0;
int c0=0;

for(int i=0;i<size;i++)
{
if(min0==-1 && ar[i]==0)min0=i;
else if(min1==-1 && ar[i]==1)min1=i;

if(ar[i])c1++;
else c0++;
}
int start,n;
if(c0>c1)
{
n=c1*2;
if((n+min1)>size)
start = size-n;
else
start = min1;
}
else
{
n=c0*2;
if((n+min0)>size)
start=size-n;
else
start=min0;
}

cout << "Longest subsequence of length: "<<n<<endl;
for(int i=0;i<n;i++)cout<<ar[i+start]<<endl;
}
int main()
{
int ar[] = {1,1,1,1,1,0,0,1,0,0};
int size = sizeof(ar)/sizeof(int);

int ar1[] = {0,0,0,1,1,0,0,1,0,0};
int size1 = sizeof(ar1)/sizeof(int);
int ar2[] = {1,1,1,1,1,1,1,1,1,1};
int size2 = sizeof(ar2)/sizeof(int);

subSeq_1_0(ar,size);
subSeq_1_0(ar1,size1);
subSeq_1_0(ar2,size2);
cin.get();
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

Did you try 1 0 1 1 1 1 1 1 0 0 1 1? it looks not working

Comment hidden because of low score. Click to expand.
0
of 0 vote

Raa, what did the interviewer want you to return from your function? A pointer to the first and last character in the subsequence, or just the size of the subsequence?

Comment hidden because of low score. Click to expand.
0
of 0 vote

My approach:
- Assuming its a string containing binary values.
- Find the no. of 1's. Complexity O(n)
- if no. of 1's = n/2 then return the full string
else if no. of 1's < n/2 then max possible subset is (no. of 1's) * 2. Lets keep this as 'm'
else if no. of 1's > n/2 then max possible subset is (n - (no. of 1's)) * 2. Lets keep this as 'm'
- So now we know the maximum possible subset with equal no. of 1's and 0`s which can be formed with the given string.
- Now have 3 variables, noOfZeros and noOfOnes
Start form zeroth index and move with the window size 'm', ie initially read 0 to 'm' index and update the 2 variables.
- Now noOfZeros = noOfOnes then return the lower and higher indices
else if noOfOnes > noOfZeros then maxPossibleSubset in this window is noOfZeros
else maxPossibleSubset in this window is noOfZeros.
In this step save the lower and higher indices of the window
- Now move the windoew to the next index, ie move the windoew right by 1 and continue the same.
Update the maxPossibleSubset and the lower and higher indices only if current maxPossibleSubset is greater than the previous.
- After scanning through the full array we will have the data of which window is possible to have the max no. of 0's n 1's.
So scan through that window alone to form the string with the help of maxPossibleSubset.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice Approach. But it does not work for following case:
001111100

Comment hidden because of low score. Click to expand.
0
of 0 vote

initially take the full string if 0's are more then start pruning frm that end frm where 0's can be reduced and if both sides have 1 then take both cases and in first case prune frm left and in other prune frm right

continue these steps untill 0's and 1's become equal and campare the length of all strings answer the maximum one

Comment hidden because of low score. Click to expand.
0
of 0 vote

How about maintaining a counter and increasing it for every 1 and decreasing it for every 0? Store the start index and everytime the counter becomes zero, store the end index. continue increasing the end index till end of string. the largest diff between start and end index will give the substring.

Ex 001010101001

here a to a = 1-1+1-1+1-1+1-1-1+1 =0

Comment hidden because of low score. Click to expand.
0
of 0 votes

this is o(n^2).
because you should check every index as the start of substring.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Algo
step 1) count 0's and 1's say it is m and n respectively
2) say m>n in that case we want to get rid of m-n 0s from end than 1's. iterate from back and keep a counter for both of them and just do that

JUST O(N) AND NO EXTRA SPACE :-)

Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please elabaorate your idea ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

@Amit
Your solution will not work for 0010100

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n^2) solution s[i] - sum of all numbers from position 0 to position i inclusive

``````Compute s[i] in O(n)
int ans = 0;
for (int i=1; i<n; ++i){
for (int j=0; j<i; ++j){
if ((i-j)%2 == 0) {
if ((s[i]-s[j]) == (i-j)/2){
if (i-j > ans){
ans = i-j;
}
}
}
}
}``````

Please comment. Anyone got something faster?

Comment hidden because of low score. Click to expand.
0
of 0 votes

No offense but this code is no faster than the basic brute-force method and uses O(n) extra space which is not necessary.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Are you sure that the solution has to be in O(1) space ? There is a solution for this problem in O(N) time and space.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Traverse the array once to count n(0) & n(1). If n(0)=n(1), return the entire array.
If n(1) > n(0) :
Find i as index of first o which is occuring
Find j as index of last o which is occuring
Now, outside this window there are only leading & terminating 1's
Count how many 1's lie between i & j : say k.
Then include n(0)-k 1's from either the terminating or leading 1's.

Does it look okay ?

Comment hidden because of low score. Click to expand.
0
of 0 votes

Won't work for sequence 0111111111110. where answer is 2

Comment hidden because of low score. Click to expand.
0
of 0 vote

it can be solved in O(n) time ..
first find two extreme zero's and check if the number of ones's inside them are less than the total number of zero's.if yes them find extra number of ones's on either side to equate the number of 0's and 1's,else start pruning the string frm one side until u encounter the numbers to be equal.
my code below has done the same all what is needed to be appended is that pruning from left side as well so as to get the longest string with same number of 1's and 0's.
import java.io.*;
import java.lang.reflect.*;
import java.lang.*;
class substring{
public static void main(String args[])
{
//System.out.println("code wrks fr string with number of one's more than number of zero's");
String s=args;
char[] str=s.toCharArray();
//System.out.println(Array.getLength(str));
//int len=str.length();
int i,c=0,so=0,sz=0,ls,zf,zl,alfa=0,ss,se,ss1,se1;
//while(str[i]!=null){i++;}
int len=Array.getLength(str);
int z=0,o=0,omz=0;
for(i=0;i<len;i++)
{
if (str[i]=='0')
{
z++;
}
else
{
o++;
}
}
i=0;
while(str[i]!='0')
{
i++;
}
zf=i;ss=i;
i=len-1;
while(str[i]!='0')
{
i--;
}
zl=i;se=i;
ls=zl-zf+1;
if(o>z)
{
omz=o-z;
//System.out.println("no is 1's "+zf);
//System.out.println("no is 0's "+zl);
//System.out.println("no is 1's minus no. of 0's "+omz);
for(i=zf;i<=zl;i++)
{
if(str[i]=='1')
so++;
}
sz=ls-so;
//System.out.println("no of ones inside extreme zero's"+so);
if(so<=sz)
{
alfa=sz-so;
if(((len-1)-se)>=alfa)
{
se=se+alfa;
}
else
{
se=len-1;ss=ss-(alfa-((len)-se));
}
for(i=ss;i<=se;i++)
System.out.print(str[i]);
}
else
{
//System.out.print(so+" ");
//System.out.println(sz);
int i1;
i=len-1; alfa=o-z;
//System.out.print(o+"is 1's");
//System.out.println(z+"is 0's");
//System.out.print(alfa+" is alfa ");//System.out.println(sz);
while((alfa!=0))
{
if(str[i]=='1')
{
alfa--;i--;
}
else {alfa++;i--;}
}
if(i==-1){System.out.println("full string exhausted");}else{se=i;}
for(i1=ss;i1<=se;i1++)
System.out.print(str[i1]);
}
}
else return;

}
}

note:one thing more can be appended is if string has just one 0 or one 1.then answer can be given too easily so a check can be put ri8 in the start.
i had coded fr this sumtime back so have just put my code here in a partial cumplete manner acording to the demand of the question but i hope i have made my idea clear to do this question in O(n) time and O(1) space... if sum1 has any prob then let me knw ,i can explain the logic a bit more vividly .

Comment hidden because of low score. Click to expand.
0
of 0 vote

count occurrences of 1 s1
count occurrences of 0 s0
check which is smaller s1 or s0
1. if s0 == s1 print entire string

2. if s0 < s1
find d = s1 - s0
say first zero is at x location
print sub sequence from x to size-(d-x)

3. if s1 < s0
find d = s0 - s1
say first one is at x location
print sub sequence from x to size-(d-x)

Complexity O(n) for count O(n) for finding first occurrence and printing :)

thus it will always be O(n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

000111100
s0 = 5, s1 = 4
d=1
x = 3, size-(d-x) = 9-(1-3)=11
optimal solution does not begin at x.

Comment hidden because of low score. Click to expand.
0
of 0 vote

i guess if we are talking of subsequence than its length can be calculated as
2*min(no of 0's,no of 1's)

because for subsequence u can take into account all the 1's or 0's whichever is mininum

But the problem becomes harder in case of substring containing equal no of 1's and 0's

Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar variation:

Count number of one's (call it M).
and number of zero's (call it K). - this can be done in one pass (in O(n))
and fixed memory space.

Now - let T = min(M,K). Surely the result is of size 2*T.
Iterate the string from start to the index Z until you count T zero's
and T one's (by definition of T,M,K - you will reach such an index Z).
This is done again in O(n) time and a fixed memory space.

return the sub string from start to Z.

Comment hidden because of low score. Click to expand.
0
of 0 votes

Consider the case: 1000000001, obvious, the longest target is 10 or 01 of length 2 not 4

Comment hidden because of low score. Click to expand.
0
of 0 votes

Question asks for subsequence.

Answer for your example will be 1001

Comment hidden because of low score. Click to expand.
0
of 0 vote

1. count the number of 0s, denoted as n0.
2. count the number of 1s, denoted as n1.
3. MinNum=Min(n0,n1), so, the maximum sub string should no longer than 2*MinMum.
4. Suppose the MinNum is n0. Then find the first 0 and last 0 in the sub string. Then count the number of 1s between this two 0s. if num of 1s between this two 0s is equal to n0, then we are done.
otherwise,
if num of 1s is larger than n0, get rid of any 0 of those two boundary 0s and substring before it if it is beginning 0, or substring following it if it is end 0. then find substring in new generated string, go to step 1.
if num of 1s is smaller than n0, then search the substring before the first 0 and last 0, until we find the answer.

coz it is a little recursive, Im not sure about time complexity.

Comment hidden because of low score. Click to expand.
0
of 0 votes

In step 4 of the two "if"s, how do you know that which side of 0 should be get rid of?

Comment hidden because of low score. Click to expand.
0
of 0 vote

well i think u are also gonna end up with if else ladder along with recursive soln.
because if not the case than u have to think that upto which point or which 1's u need to skip from both ends

Comment hidden because of low score. Click to expand.
0
of 0 vote

From TopCoder Forum by "konqueror"

The following solution assumes that the given array is an integer array (instead of a char array) for ease of exposition. Later, we will show how we can modify it to use a char array instead.

The outline of the solution:
1) Transform the (integer) array (modify in place) to an equivalent (integer) array
2) Perform computation on the array
3) Restore array.
So, in effect you would have used only O(1) additional space.

We shall cheat a little bit and use indexing in the range [0...n] instead of [0...n-1]. We assume that the given (integer) array actually occupies indices [1...n]. This makes things easier to understand. At the end, this will be irrelevant.

Step 1(transformation):
A[i] = (i==0)?0:((A[i]==0?1:-1) + A[i-1])
In words, A[i] = (number of zeroes - number of ones) in the first i places of the (original) array. At the end of step 1, you have an array of integers. The task is to find out
max{y-x | A[y] = A[x] }

Notation:
First(t) = min{ x | A[x] = t} if t appears in A, infinity if t doesn't appear in A
Last(t) = max{ x | A[x] = t} if t appears in A, -infinity if t doesn't appear in A
D(t) = Last(t) - First(t)
L = max{ D(t) | integer t}

First and Last correspond to the indices of the first and last occurences respectively of their argument.We call integer T good if D(T) = L. Our task is to compute L. If we identify *one* good integer, g, then, we can compute L = D(g) in linear time(trivially), with O(1) additional space.

Let END = A[n]. Assume END > 0. (if END < 0, we flip 0s and 1s, solve (since flipped END > 0) (and flip back). END = 0 is trivial: L = n).
Observation 1: First(x) > First(y) if x > y >= 0. Trivial.
Observation 2: First(x) > First(y) if 0 >= y > x. Trivial.
Observation 3: If t > END, then t is not good. Since First(t) > First(END) and Last(t) < Last(END).
Observation 4: If t < -1, then t is not good. Since END > 0, Last(-1) > Last(x) for x < -1. Follows from observation 2.
Observation 5: Last(0) < Last(1) <.. < Last(END). Suppose 0 < x+1 <= END and Last(x) > Last(x+1). Then, clearly, A[Last(x)...n] does not contain x+1. Hence, it surely cannot contain END (since END >= x+1 and the values in A move only +1/-1 at a time(no jumps)), a contradiction.
Observation 6: First(0) < First(1) < .. < First(END). Follows from observation 1.

Observation 5 and 6 are the crux of the linear time solution we propose. In short, we can compute Last(i) and First(i) for 0<=i<=END in one pass.
Observations 3 and 4 allow us to limit the search of a good candidate to [0, END] and {-1}
Also, First(x) and Last(x) can be computed in O(n) time for any x trivially.

Step 2(Computing optimum):
int first = First(END), last = Last(END), x = END-1;
int L = last-first;
while(x >= 0) {
while(A[last] != x) last--;
while(A[first] != x) first--; //(this is wrong, we will show how to fix it below)
L = max(L, last-first);
x--;
}
L = max(L, Last(-1) - First(-1));

But, there is a mistake. Can you spot it ?
The problem occurs for cases like 10000.. . In such cases, first(t) = last(t) for t>0. for t=0, however, first(t)=0, last(t)=2. (The code shown above does not handle this case). So, how do we fix it ? We realize that stepping through first(t) (in decreasing order of t) is nothing but stepping through prefix maximums. Position i is a prefix maximum if A[i] > A[j] for j < i. We can compute prefix maximums in one linear pass and mark some positions (with say most significant bit) as prefix maximums. Moving the variable "first" is equivalent to moving to the next lower prefix maximum (or -1).

Step 3(Restore Array): Trivial:
(A[i] == A[i-1] + 1)? (A[i] = 0) : (A[i] = 1); (1<=i<=n)

This concludes the solution, given integer array.

How do we make it work with a char array ?
1) Compute END (O(1) additional space, O(n) time). (assume END > 0 from here on, else flip, etc..)
2) Mark prefix maximums with char '2'. Note only original '0's can become '2'. ('0' corresponds to depth +1 and '1' to depth -1)
3) Initialize first, last and x in line 1 of step 2. (O(n) time, O(1) additional space).
4) Replace the line:
while(A[last] != x) last--;
with
int diff = 0; while(diff != 1) { diff += (A[last]=='1'?-1:1); last--; }

5) Replace the line:
while(A[first] != x) first--;
with
--x; while(x >= 0 && A[x] != '2') x--;

Comment hidden because of low score. Click to expand.
0
of 0 vote

O(n) solution in C#
private int[] getsub01(int[] n)
{

int count1 = 0, count0 = 0;
int i=0,start1=0,last1=0,last0=0;
foreach (int num in n)
{
if (num == 0)
{
count0++;
last0=i;
}
else
{
if(count1==0)
start1=i;
count1++;
last1=i;
}
i++;
}
int count = 0;

if (count0 == count1)
return n;
if(count0==0 || count1==0)
return null;

int rest = count0 > count1 ? 0 : 1;
int last = count0 > count1 ? last1 : last0;
int oth=rest==0?1:0;
count = counter(n, oth, 0, last);

if(counter(n,rest,0,last)==count)
return subarray(n,0,last);
else if(counter(n,rest,0,last)<count)
{
int inc=(count1*2)- subarray(n,0,last).Length;
if(inc+last<=n.Length-1)
return subarray(n,0,last+inc);

}
else{
int s=0,l=last;

while(counter(n,rest,s,l)>count)
{

s=s+1;
count = counter(n, oth,s, l);

}

return subarray(n, s, l);

}
return n;
}

private int counter(int[] n,int num,int start,int end)
{
int count=0;
for(int j=start;j<=end;j++)
{
if(n[j]==num) count++;
}

return count;
}

private int[] subarray(int[] n, int start, int end)
{
int len = end - start + 1;

int[] sub=new int[len];

for (int i= start,j=0; i <= end; i++,j++)
{
sub[j] = n[i];
}

return sub;
}

Comment hidden because of low score. Click to expand.
0
of 0 votes

dude can u please ur logic?
understand long code is painful :(

Comment hidden because of low score. Click to expand.
0
of 0 votes

*understanding

Comment hidden because of low score. Click to expand.
0
of 0 votes

it gives incorrect answer in some cases....for an array 0000110101111 it gives entire array as an answer...but it should be 000011010111...

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think This Logic Might Work

1. count number of 0's called num_o o(n)
2. count number of 1's called num_1 o(n)
3. find the min of two O(1)
4. length or Bubble is of length is twice the min
5. start from first and copy all the array of size of length and count number of 0s and 1's if equal then done else shift the bubbel one int to right and check it again.

At the end you will have the solution in o(n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

thats O(n*(min(num_o,num_1))
not O(n)

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think This Logic Might Work

1. count number of 0's called num_o o(n)
2. count number of 1's called num_1 o(n)
3. find the min of two O(1)
4. length or Bubble is of length is twice the min
5. start from first and copy all the array of size of length and count number of 0s and 1's if equal then done else shift the bubbel one int to right and check it again.

At the end you will have the solution in o(n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

for 10001, it doesn't work.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````solution may be
int flag=0;
int postion=-1;
while(i<size)
{
if(flag==0)
ppstion=flag;
else if(arr[i])
flag++;
else
flag--;
}
printf("the array is i=0 to i=postionn");``````

}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````at the postion of
ppstion=flag;
it is
postion=i;``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

public void find(int[] a)
{
int count0 = 0, count1 = 0, maxChk, maxOccr;

int size = a.length;

for(int i=0;i<size;i++)
{
if(a[i]==0)
count0++;
else
count1++;
}

if(count1>count0){
maxChk = 1;
maxOccr = count0;
}else{
maxChk = 0;
maxOccr = count1;
}

int pivot=0;
int curr1 = 0;
int curr0 =0;

for(int i=0;i<size;i++)
{

if(a[i]==0)
curr0++;
else
curr1++;

if(maxChk==1)
{
while(curr1>maxOccr)
{
if(a[pivot]==0)
{
curr0--;
maxOccr--;
}else
{
curr1--;
}

pivot++;
}
}

if(maxChk==0)
{
while(curr0>maxOccr)
{
if(a[pivot]==1)
{
curr1--;
maxOccr--;
}else
{
curr0--;
}

pivot++;
}
}

if(maxOccr==curr0 && maxOccr==curr1)
{
System.out.println("start index = "+pivot+" , end index = "+i+", size = "+(2*maxOccr));
return;
}
}

}

Comment hidden because of low score. Click to expand.
0
of 0 votes

There are only 2 passes...o(n) time complexity
No additional storage except few state variables.... o(1) space

Comment hidden because of low score. Click to expand.
0
of 0 votes

abe sale compile kiya tha kya ...

Comment hidden because of low score. Click to expand.
0
of 0 votes

abe sale compile kiya tha kya ...

Comment hidden because of low score. Click to expand.
0
of 0 votes

for input string 1010001, this return the last "01" when the correct answer is the first "1010"

Comment hidden because of low score. Click to expand.
0
of 0 vote

int 1_count = 0;
int 0_count = 0;
int max_len = 0;
int end = -1;

for(int i = 0 ; i < n ; i++){
if(a[i] == 0) 0_count++;
else 1_count++;

if(1_count != 0 && 0_count != 0){
if(min(0_count,1_count) > max_len){
max_len = min(0_count, 1_count);
end = i;
}
}
}

int start = end - (2 * max_len) + 1;

Comment hidden because of low score. Click to expand.
0
of 0 vote

How can we be so sure of substring having twice the length..
For Eg. 10100001 ..the ans will be 1010 isnt it?
and its length is 4 ..not twice of min(len_0, len_1) which is 3X2=6.

Comment hidden because of low score. Click to expand.
0
of 0 votes

how about using a stack
algorithm

push a,0 to stack(i.e push element, its index to a stack)

for (i=1 to a.length-1)
{
if(a[i] == stack[top] push(a[i],i)
else pop();
}

//now you are left with elements and its indices in stack which break occurences of sequence with equal no of 0's and 1's

pop eachelemt in stack and find for the max difference of indexes which should give the result..

Comment hidden because of low score. Click to expand.
0
of 0 votes

using a stack wouldn't be O(1) space

Comment hidden because of low score. Click to expand.
0
of 0 votes

``````public class  MaxSubsequenceOfOneAndZero
{
public static void main(String[] args)
{
int[]arr={0,1,1,1,1,1,1,1,1,0,1,0,0,0};
System.out.println("Hello World!");
int temp=0;
int seq=0;
for(int loop=0;loop<arr.length;loop++)
{
if(arr[loop]==1)temp = temp+1;
else temp=temp-1;
System.out.println(temp);

if(temp == 0)
seq=loop;
}

System.out.println("Seq = "+seq);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

Does it work for the the array 0 0 0 1 1 0 0

Comment hidden because of low score. Click to expand.
0
of 0 vote

is any solution exist in given constraints? or shall i call Petr Mitrichev :P

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we solve this by using RegExp?? any idea?

Comment hidden because of low score. Click to expand.
0
of 0 vote

Using a stack. stack has only 2 member, 1 is value (0 or 1), 1 is number of value.

Comment hidden because of low score. Click to expand.
0
of 0 vote

whenever 0 comes subtract and whenever 1 comes add it.
using DP extra space o(n) find at each positon its value.
now stores this DP values in a hash map
whenever a equal value occurs check lowest index for that value and this value and if that's the max i.e length is greater than previous length den store it in max
after parsing the total input
return max

Comment hidden because of low score. Click to expand.
0
of 0 votes

It works great :)

Comment hidden because of low score. Click to expand.
0
of 0 votes

what's time complexity? is it better than O(n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

Flawed Logic
Counter Example:
Input:00000100000
does not return any index for storing in HashMap

Comment hidden because of low score. Click to expand.
0
of 0 vote

I will give my solution by stating example:

Input: 1 0 0 1 1 0 0 1 1 1

now create another auxillary array of same size as Input. Now traverse the input and keep taking the cummulative sum where consider 0 = -1

so for given input, auxillary array will have following values:

Input: 1 0 0 1 1 0 0 1 1 1
aux : 1 0 -1 0 1 0 -1 0 1 2

now take 2 pointers one at the start of aux and one at the end of aux. Now the purpose of moving start and end would be to bring { aux[end] - aux[start] =0 }

there are some decisions to be taken:

while(end>start)
{
if(aux[end] - aux[start] == 0)
{
break;
}
else
{
if(aux[end] - aux[start]>0)
{
if(aux[end-1] - aux[start] >= aux[end] - aux[start+1])
{
start = start + 1; // Take the value which is min
}
}
else
{
if(aux[end-1] - aux[start] >= aux[end] - aux[start+1])
{
end = end - 1; // Take the value which is min
}
}
}

final solution:
startIndex = start +1;
EndIndex = end;

Comment hidden because of low score. Click to expand.
0
of 0 vote

Some problem in above logic, so correcting that:

Input: 1 0 0 1 1 0 0 1 1 1

now create another auxillary array of same size as Input. Now traverse the input and keep taking the cummulative sum where consider 0 = -1

so for given input, auxillary array will have following values:

Input: 1 0 0 1 1 0 0 1 1 1
aux : 1 0 -1 0 1 0 -1 0 1 2

now take 2 pointers one at the start of aux and one at the end of aux. Now the purpose of moving start and end would be to bring { aux[end] - aux[start] =0 }

there are some decisions to be taken:

while(end>start)
{
if(aux[end] - aux[start] == 0)
{
break;
}
else
{
if(aux[end] - aux[start]>0)
{
if(aux[end-1] - aux[start] >= aux[end] - aux[start+1])
{
start = start + 1; // Take the value which is min
}
else
{
end = end -1;
}
}
else
{
if(aux[end-1] - aux[start] >= aux[end] - aux[start+1])
{
end = end - 1; // Take the value which is min
}
else
{
start = start +1;
}
}
}

final solution:
startIndex = start +1;
EndIndex = end

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````Assume input is 11010

c0: count of 0 counted from beginning.
c1: count of 1 counted from beginning.
c0': if current element is 0, then c0'=c0-1, otherwise c0'=c0.
c1': if current element is 1, then c1'=c1-1, otherwise c1'=c1.

(c0,c1) c1-c0     (c0',c1')  c1'-c0'
1 (0,1)    1        (0,0)      0
1 (0,2)    2        (0,1)      1
0 (1,2)    1        (0,2)      2
1 (1,3)    2        (1,2)      1
0 (2,3)    1        (1,3)      2

if for i and j (j>i), c1[j]-c0[j] = c1'[i]-c0'[i], then a subsequence of equal 0's and 1's is found from i to j. For example, (1,4),(2,3)....

int f(int* a, int n)
{
Hash<int,int> h = new Hash<int, int>();
int c0=0;
int c1=0;
int max=INT_MIN;

for(int i=0;i<n;++i)
{
if(a[i]==0)
c0++;
else
c1++;

int diff = c1-c0;
if(h.ContainKey(diff))
{
int len=i-h[diff]+1;
if(len>max)
{
max=len;
}
}

if(a[i]==0)
{
diff++;
}
else
{
diff--;
}

if(!h.ContainKey(diff)
{
h.Add(diff, i);
}
}

return max;
}``````

Comment hidden because of low score. Click to expand.
0
of 2 vote

``````/*the function returns the end index of the longest sub-sequence
and start index is passed as reference variable*/
int findMaxSubSeq(int a[],int i,int &start)
{
int end;
static int count={0,0},token,len=(sizeof(a)/sizeof(a);

if(i==len))
{
token=((count<count)?count:count);
return 0;
}

count[a[i]]++;
end=fun(a,i+1,start);

if(end==0)
{
if(!count || !count)
{
start=i;
if(token>0)
end=i+(2*token)-1;
else
end=0;  //for strings containing only 1's or only 0's
}
else if(count==count)
{
token=-1;  //so that the condition 'if(token>0)' above is not satisfied
count--; //so that this condition is not satisfied again
return i;
}
else
count[a[i]]--;
}
return end;
}

void main()
{
int a[]={1,1,0,1,0,1,1},start=0;
end=findMaxSubSeq(a,0,start);
if(start>=end)
cout<<"No such sub-sequence";
else
for(int i=start;i<=end;i++)
cout<<a[i];
}``````

Time Complexity-O(n)

Comment hidden because of low score. Click to expand.
0
of 0 votes

dude, need o(n) space

Comment hidden because of low score. Click to expand.
0
of 0 vote

I know this thread is old, but I think this question is interesting and very tricky. Can we modify the elements in the array? I mean we can achieve the required complexity and give the start & end index if we can modify the original array, but probably not the original sub-sequence. does this count? :p Not sure if the following process can make the interviewer happy.

The idea is, we start a loop from the zero index(let's say i = 0) and find the first pair of adjacent 1 & 0, change them to -1, and then we check the left and right side of the pair if left or right has not reached the boundaries. There are two possibilities which make the sub-sequence starts from the pair a longer one:
1. array[left] ^ array[right] = 1 (if left > -1 and right < length of the array)
2. array[right] ^ array[right + 1] = 1 (if right + 1 < length of the array)

if neither of the condition can be reached, then we set the current index to right (i = right), and repeat the process until i reaches the boundary. The time complexity should be O(n)

after the loop, every possible pair should have been set to -1. And to get the start and end indexes of the required sub-sequence, we starts another loop to get the max length of continuous -1, that's another O(n). So overall, we have O(n) + O(n) = O(n), and the function requires left & right & length(this variable is used to calculate the max length of the sub-sequence) which is a constant, so the space complexity is O(1). The only problem is that we need a copy of the original array to give the detailed sub-sequence or we can only tell the interviewer where the sub-sequence is. But that's the only solution I can think of which can have a close complexity to the requirement. Looking forward to a perfect solution to this question. The following function is the implementation, it doesn't handle some edge cases like an array that has only one element. It is not perfect and has not been fully tested, but it has passed the following test cases:
{1,1,0,0,0,0,0,0,0,0,0,1,1,1}(14 elements in total, the answer is 6)
{1,1,0,0,0,1}(6 elements in total, the answer is 6)
{1,1,0,0,0,1,0,0}(8 elements in total, the answer is 8)
{0,1,1,1,1,1,1,1,1,0,1,0,0,0}(14 elements in total, the answer is 8)
{1,0,1,0,0,0,1}(7 elements in total, the answer is 4)

``````//examples:
//101010=>##1010=>####10=>######
//11000000000111=>1##000000000111=>1##00000000111=>1##0000000##11=>1##000000####1=>1##00000######
//110001=>1##001=>####01=>######
//11000100 =>1##00100=>####0100=>######00
int fun(int* binaries, int len)
{
int left = -1, right = -1;

for(int i = 0; i < len; ++i)
{
if (binaries[i] ^ binaries[i+1] == 1)
{
binaries[i] = -1;
binaries[i+1] = -1;
if (i > 0)
{
left = i - 1;
}
if (i < len)
{
right = i + 2;
}

while(left > -1 || right < len)
{
if (left > -1 && right < len && binaries[left] ^ binaries[right] == 1)
{
binaries[left] = -1;
binaries[right] = -1;
--left;
++right;
}
else if (right < len - 1 && (binaries[right] ^ binaries[right + 1] == 1))
{
binaries[right] = -1;
binaries[right + 1] = -1;
right += 2;
}
else
{
break;
}
}

i = right;
}
}

left = -1, right = -1;
int templen = 0;
for (int i = 0;i < len ;++i)
{
if (left == -1 && binaries[i] == -1)
{
left = i;
}
if (binaries[i] == -1)
{
right = i;
if (right - left > templen)
{
templen = right - left + 1;
}
}
if (i > 0 && binaries[i] != -1 && binaries[i-1] == -1)
{
left = -1;
}
}

return templen;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

After reviewing my implementation, I found that I can get rid of the 2nd loop by introducing another two variables instead. Stupid me!

``````int fun(int* binaries, int len)
{
int left = -1, right = -1;
int start = -1, end = -1;
for(int i = 0; i < len; ++i)
{
if (binaries[i] ^ binaries[i+1] == 1)
{
binaries[i] = -1;
binaries[i+1] = -1;
if (i > 0)
{
left = i - 1;
}
if (i < len)
{
right = i + 2;
}

while(left > -1 || right < len)
{
if (left > -1 && right < len && binaries[left] ^ binaries[right] == 1)
{
binaries[left] = -1;
binaries[right] = -1;
--left;
++right;
}
else if (right < len - 1 && (binaries[right] ^ binaries[right + 1] == 1))
{
binaries[right] = -1;
binaries[right + 1] = -1;
right += 2;
}
else
{
break;
}
}

i = right;

if (right >= len)
{
right = len - 1;
}
else
{
--right;
}
if (left < 0)
{
left = 0;
}
else
{
++left;
}
if ((right - left + 1) > (end - start + 1))
{
start = left;
end = right;
}

}
}

return (end != -1) ? (end - start + 1) : 0;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Sorry, the test result of test case {1,1,0,0,0,1,0,0} should be 6

Comment hidden because of low score. Click to expand.
0
of 0 vote

TC O(N); SC O(1)

``````public int getMaxLen(int[] arr ){

if( arr == null || arr.length == 0 ){
return 0;
}

int max = 0, sum = 0, len = arr.length;
int sign = 1;

for( int i=0; i<len; i++ ){
sign = (arr[i] == 1)?1:-1;
arr[i] = sign * (len+1);
sum += sign;

if( sum > 0 ){
sign = (arr[sum-1]>=0)?1:-1;
int pos1 = arr[sum-1]*sign;
if( pos1 == len+1 ){
arr[sum-1] = sign * i;
}else{
int tmp = i - pos1 ;
max = (tmp>max)?tmp:max;
}
}else if( sum == 0 ){
int tmp = i+1;
max = (tmp>max)?tmp:max;
}
}

sum = 0;
for( int i=0; i<len; i++ ){
sign = (arr[i] >= 0)?1:-1;
arr[i] =  len+1 ;

sum += sign;
if( sum < 0 ){
if( arr[-sum-1] == len + 1 ){
arr[-sum-1] = i;
}else{
int tmp = i - arr[-sum-1]  ;
max = (tmp>max)?tmp:max;
}
}
}
return max;
}``````

Comment hidden because of low score. Click to expand.
0
of 0 votes

This idea uses the space of the origin array.
The idea is to store the sum of all elements in the specific pos of the array.
Whenever the sum is met again, check it with the first time the sum was met and update the max.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public int maxSubArray(int[] array) {
int max = 0;
if(array.length<2)
return max;
for(int i=0; i<array.length; i++) {
if(array[i]==0)
array[i] = -1;
}
int[] temp = new int[array.length];
temp = array;
for(int i=1; i<array.length; i++) {
temp[i] = temp[i-1] + array[i];
}
for(int i:temp) {
if(i==0)
max = i+1;
}
HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
for(int i=0; i<array.length; i++) {
if(!hm.containsKey(temp[i])) {
hm.put(temp[i], i);
}else {
int pot = i - hm.get(temp[i]);
if(pot>max)
max = pot;
}
}
return max;
}``````

idea from: geekforgeeks

Comment hidden because of low score. Click to expand.
0
of 0 vote

Following solution runs in O(n+m) where m < n.

``````public class SubSequence {

public String get(String data){
if (data == null || data.length() <=1)
return null;

int start = -1, end = -1;
int tempStart= -1, tempEnd = data.length();
// assume that first char is interested one
char interested = data.charAt(0);
// store position of 1s
Stack<Integer> stack = new Stack<>();

for(int index = 0; index < data.length(); index++){
if (data.charAt(index)== interested){
stack.push(index);
if (tempStart == -1)
tempStart = index;
}else{
if (tempStart == -1)
continue;
if (stack.isEmpty()){
if ((index - tempStart) > (end - start)){
start = tempStart;
end = index;
}
tempStart = -1;
}else
// pop the matching 1
stack.pop();
}
}

// if the input itself is longest sequence, it should come here
if (stack.isEmpty() && tempStart != -1){
if ((tempEnd - tempStart) > (end - start)){
start = tempStart;
end = tempEnd;
}
}

// if input has more 1s, stack is not empty
while(!stack.isEmpty()){
tempStart = stack.pop();
if ((tempEnd - tempStart) > (end - start)){
start = tempStart + 1;
end = tempEnd;
}
tempEnd = tempStart;
}

return data.substring(start, end);
}

public static void main(String[] args) {
SubSequence seq = new SubSequence();
System.out.println(seq.get("111001110011100011100"));
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

It can be done in O(n) time and O(1) space using two pointers.

1. Count # of 0's, #Z, and 1's, #O.

2. Initially "start" pointer points to position 0, "end" points to n-1. This is current window.

3. If #Z > #O,
3.a) if any of the pointers point to 0, move the pointer and reduce #Z.
3.b) If none of the pointers point to 0, skip 1's from the end where there are fewer 1's to skip to get to a 0. Once you get to zero 3.a applies. Update counters accordingly.

4. Similar logic applies to #Z < #O.

Basically the idea is that for the max window there is a #Z = #O, we try to reach that number from the possible max.

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````public class FindLargestUniformWindow {

// false = 0, true = 1
static int findLargestUniformWindow(Boolean a[]){
int n = a.length;
if(n<=1){
return 0;
}

//int numZerosMinusNumOnes[] = new int[n];
int numZerosMinusNumOnesCurr = 0;
Map<Integer,Integer> valVsLowestIndexWhereOccured = new HashMap<Integer,Integer>();
valVsLowestIndexWhereOccured.put(0, -1);
int maxWindowLength = 0;

for(int i = 0; i < n; i++){
//numZerosMinusNumOnes[i] = numZerosMinusNumOnesCurr;
boolean val = a[i];
if(!val){
numZerosMinusNumOnesCurr++;
} else {
numZerosMinusNumOnesCurr--;
}

if(!valVsLowestIndexWhereOccured.containsKey(numZerosMinusNumOnesCurr)){
valVsLowestIndexWhereOccured.put(numZerosMinusNumOnesCurr, i);
} else {
int windowLengthCur = i - valVsLowestIndexWhereOccured.get(numZerosMinusNumOnesCurr);
if(windowLengthCur > maxWindowLength){
maxWindowLength = windowLengthCur;
}
}
//System.out.println(i + "\t" + numZerosMinusNumOnesCurr + "\t" + valVsLowestIndexWhereOccured.get(numZerosMinusNumOnesCurr));
}

return maxWindowLength;
}

public static void main(String[] args){

Boolean[] testcase = {false, false, true,true, false, true, false, false, false, false, true};
int result = 6;

System.out.println(Arrays.toString(testcase));

int m = findLargestUniformWindow(testcase);

System.out.println(m + "\t" + result);
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````def hasSameNumberOnesAndZeroes(aString):
return aString.count('1') == aString.count('0')

def largestSubsequenceWithSameNumberOnesAndZeroes(start, end, aString):
if hasSameNumberOnesAndZeroes(aString[start:end+1]):
return end - start, start, end, aString[start:end+1]
return max( [largestSubsequenceWithSameNumberOnesAndZeroes(start, end-1,
aString),
largestSubsequenceWithSameNumberOnesAndZeroes(start+1, end,
aString)], key=lambda x: x)

def runTest(myString):
print "Longest substring of %s with an equal number of 1's and 0's: %s" % (myString, largestSubsequenceWithSameNumberOnesAndZeroes(0, len(myString), myString))

def main():
myString1 = '1101000'
myString2 = '10101010'
runTest(myString1)
runTest(myString2)

if __name__ == '__main__':
main()``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````S='10101010'
S=list(S)
different=[]
Hash={}
def longest(x):
max1=0
for i in range(0,len(x)):
different.append(0)
if x=='1':
different=1
else:
different=0
for i in range(1,len(x)):
if x[i]=='1':
different[i]=different[i-1]+1
else:
different[i]=different[i-1]-1
for i in range(0,len(x)):
if different[i] in Hash:
judge=i-Hash[different[i]]+1
max1=max(max1,judge)
else:
Hash[different[i]]=i
return max1``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

- Write the 0/1 String in your board.
- Now your target is to erase some 0 and one such that we have equal number of zero and one left in the board
- The remaining number in the board is the "Sequence". Note we are not altering the order and We are not suppose to return a substring
- Now question is what to erase and what not ?
- Let we have X number of ONE and Y number of Zero.?
- If X == Y , Cool ! Equal number of Zero one Found! Ans is Full number
- IF X < Y : Less One ! erase (Y-X) Number of Zero anywhere.. Cool: Ans is 2*X
- If Y > X: Less Zero! Erase (X-Y) Number of One from the board! Ans is 2*Y

Complexity : O(N)
The code is as below:

``````#define MIN(a,b) ((a < b)?a:b)
int MaximalSubSequenceOfEqualNumberOFZeroOne(int *a, int n){
int countOne=0,countZero=0;
for(int i=0;i    if(a[i]==1) countOne++;
}
countZero = n-countOne;
return 2 * MIN(countZero,countOne);
}

int main(){
int a[]={1,0,1,0,1,0,1,0,0,1,0,0,0};
printf("Ans:%d",MaximalSubSequenceOfEqualNumberOFZeroOne(a,sizeof(a)/sizeof(a)));
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

Python3

from collections import deque

inp = [1,1,0,1,0,0,0]

d = deque(inp)
tot0 = d.count(0)
tot1 = d.count(1)

while tot0 != tot1:
if tot0 > tot1:
if d == 0:
d.popleft()
elif d[len(d)-1] == 0:
d.pop()
else:
d.popleft()
else:
if d == 1:
d.popleft()
elif d[len(d)-1] == 1:
d.pop()
else:
d.popleft()
tot0 = d.count(0)
tot1 = d.count(1)

print(list(d))

This was the simplest answer I could come up with.

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