Amazon Interview Question for Software Engineer / Developers






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.

- Anonymous July 04, 2010 | Flag Reply
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?

- Anonymous July 04, 2010 | Flag
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).

- geekyjaks December 15, 2013 | Flag
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[0])));
}

- dutta.dipankar08 June 10, 2015 | Flag
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?

- The Red Baron August 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Stupidest answer :)

- Anonymous December 16, 2012 | Flag
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.

- sppl February 22, 2014 | Flag
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.!!

- sigkill June 08, 2014 | Flag
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.

- SomeGuy July 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

cant understand. seems good.

- aaron liang September 18, 2012 | Flag
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[2] GetLongestSubSequence(bool[] sequence)
{
   if (sequence.length < 2) return new int[]{-1,-1};
   int startIndex = 1;
   int stopAt = 0;
   bool firstChar = sequence[0];
   Queue<int[2]> possibleSubSequences = new Queue<int[2]>();
   
   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[0]-1 != lastEndIndex)
       { 
           startIndex = ps[0];
       }
       endIndex = ps[1];
     }

      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.

- Anonymous July 02, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Uses Ω(n) space up to log factors.

- Anonymous July 03, 2010 | Flag
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.

- Anonymous July 03, 2010 | Flag
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.

- SomeGuy July 03, 2010 | Flag
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!

- SomeGuy July 03, 2010 | Flag
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.

- SomeGuy July 03, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Good effort SomeGuy

- Anonymous July 04, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- AnotherGuy July 04, 2010 | Flag
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.

- S July 03, 2010 | Flag Reply
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

- Anonymous July 04, 2010 | Flag
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.

- Anonymous July 04, 2010 | Flag
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.

- Anonymous July 04, 2010 | Flag
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"...

- S July 04, 2010 | Flag
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).

- RAKESH July 05, 2010 | Flag
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.)

- Anonymous July 05, 2010 | Flag
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.

- RAKESH July 06, 2010 | Flag
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

- buried.shopno July 10, 2010 | Flag
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

:(

- Anonymous July 03, 2010 | Flag Reply
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);
	}

- dood July 05, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Finds the maximum prefix.

- Anonymous July 05, 2010 | Flag
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.

- dood July 05, 2010 | Flag
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}

- Ravi July 06, 2010 | Flag
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);
	}
}

- Anonymous July 05, 2010 | Flag Reply
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.

- Anonymous July 08, 2010 | Flag Reply
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();
}

- n1t3sh July 08, 2010 | Flag Reply
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

- Anonymous July 09, 2010 | Flag
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?

- ryndrvs July 12, 2010 | Flag Reply
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.

- Anonymous July 14, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- GateChang July 19, 2010 | Flag
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

- tryer July 18, 2010 | Flag Reply
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[2] to a[11] = 1-1+1-1+1-1+1-1-1+1 =0

- Anonymous July 20, 2010 | Flag Reply
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.

- zoubincn May 18, 2013 | Flag
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 :-)

- Amit Priyadarshi July 21, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can u please elabaorate your idea ?

- ravikant July 24, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@Amit
Your solution will not work for 0010100

- GFLB August 13, 2010 | Flag
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?

- The Red Baron August 26, 2010 | Flag Reply
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.

- ftfish August 26, 2010 | Flag
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.

- Ram August 26, 2010 | Flag Reply
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 ?

- oshin August 26, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ani September 22, 2010 | Flag
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[0];
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 .

- saumils1987 August 26, 2010 | Flag Reply
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)

- Anonymous August 26, 2010 | Flag Reply
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.

- counter example August 26, 2010 | Flag
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

- nitin August 26, 2010 | Flag Reply
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.

- Anonymous August 26, 2010 | Flag Reply
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

- Steve August 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Question asks for subsequence.

Answer for your example will be 1001

- Mahesh August 26, 2010 | Flag
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.

- Xi Zhang August 26, 2010 | Flag Reply
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?

- jimmyzzxhlh August 26, 2010 | Flag
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

- @above August 26, 2010 | Flag Reply
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--;

- MaYanK August 26, 2010 | Flag Reply
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;
}

- burmeselady August 27, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Rocco August 28, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

*understanding

- Rocco August 28, 2010 | Flag
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...

- harit222 August 30, 2010 | Flag
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)

- Prince August 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- varun.mulki April 18, 2012 | Flag
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)

- Prince August 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

for 10001, it doesn't work.

- zoubincn May 18, 2013 | Flag
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");

}

- karan August 29, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- karan August 29, 2010 | Flag Reply
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;
}
}

}

- Rahul Kumar August 31, 2010 | Flag Reply
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

- Rahul Kumar August 31, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

abe sale compile kiya tha kya ...

- netappreject September 02, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

abe sale compile kiya tha kya ...

- netappreject September 02, 2010 | Flag
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"

- mike September 18, 2010 | Flag
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;

- san September 05, 2010 | Flag Reply
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.

- Gol September 10, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

how about using a stack
algorithm

push a[0],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..

- c# September 12, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- mike September 18, 2010 | Flag
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);
	}
}

- Anonymous September 23, 2010 | Flag
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

- GP January 05, 2011 | Flag
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

- career.baghel September 11, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Jigs September 29, 2010 | Flag Reply
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.

- fang October 06, 2010 | Flag Reply
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

- sandeep November 25, 2010 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

It works great :)

- Lokesh January 09, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 123 January 10, 2011 | Flag
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

- Karthik January 23, 2011 | Flag
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;

- Anonymous February 20, 2011 | Flag Reply
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

- Anonymous February 20, 2011 | Flag Reply
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;
}

- jiangok2006 July 19, 2012 | Flag Reply
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[2]={0,0},token,len=(sizeof(a)/sizeof(a[0]);
   
   if(i==len))
   {  
     token=((count[0]<count[1])?count[0]:count[1]);
     return 0;
   }

   count[a[i]]++;
   end=fun(a,i+1,start);
   
   if(end==0)
   {
    if(!count[0] || !count[1])
    {
      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[0]==count[1])
    {
      token=-1;  //so that the condition 'if(token>0)' above is not satisfied    
      count[0]--; //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)

- coderBon August 18, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

dude, need o(n) space

- aaron liang September 18, 2012 | Flag
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;
}

- GuestViewer April 06, 2013 | Flag Reply
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;
}

- GuestViewer April 06, 2013 | Flag
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

- GuestViewer April 06, 2013 | Flag Reply
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;
}

- jinshuxianty June 28, 2013 | Flag Reply
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.

- jinshuxianty June 28, 2013 | Flag
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[0] = array[0];
		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

- sz2376@columbia.edu November 20, 2013 | Flag Reply
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"));
  }
}

- geekyjaks December 15, 2013 | Flag Reply
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.

- lasthope January 16, 2014 | Flag Reply
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);
	   }
}

- just_do_it July 26, 2014 | Flag Reply
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[0])

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)[3])

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

if __name__ == '__main__':
    main()

- Alex Cannon February 08, 2015 | Flag Reply
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[0]=='1':
        different[0]=1
    else:
        different[0]=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

- Wei February 10, 2015 | Flag Reply
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[0])));
}

- dutta.dipankar08 June 10, 2015 | Flag Reply
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] == 0:
d.popleft()
elif d[len(d)-1] == 0:
d.pop()
else:
d.popleft()
else:
if d[0] == 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.

- jkatzwhitew December 14, 2018 | 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