Amazon Interview Question
Software Engineer / DevelopersSAT: needs to check every possible assignment for satisfaction, hence O(2^n) is the minimum. WHERE'S MY MILLION DOLLARS?
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])));
}
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?
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.
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.
// 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.
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.
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!
Yeah, I see what you're saying now. even that bug fix doesn't work. optimal is 1,10. rats.
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.
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
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"...
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, 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.)
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.
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);
}
Yes, Once you have the index, loop through the array and print numbers upto the index-1.
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);
}
}
#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();
}
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.
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
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
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 :-)
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?
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 ?
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 .
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)
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.
Consider the case: 1000000001, obvious, the longest target is 10 or 01 of length 2 not 4
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.
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--;
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;
}
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)
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)
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;
}
}
}
There are only 2 passes...o(n) time complexity
No additional storage except few state variables.... o(1) space
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;
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.
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..
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);
}
}
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
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;
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
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;
}
/*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)
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;
}
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;
}
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;
}
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
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"));
}
}
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.
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);
}
}
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()
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
- 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])));
}
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.
Longest subsequence -> any i,j where i!=j
- Anonymous July 04, 2010Needs 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.