Groupon Interview Question SDE1s
Country: United States
Cheng Q.'s approach is correct. Here is an implementation for this idea.
I use the array pos, where pos[i] = the left most position where count_1 - count_0 = i
Time complexity: O(N)
Space complexity: additional O(N)
#include <iostream>
#include <algorithm>
#include <cstring>
const int MAX_N = 100;
const int INF = 0x3F3F3F3F;
using namespace std;
int solve(int a[MAX_N], int n) {
int b[2*MAX_N + 1];
int *pos = b + MAX_N; // pos points to the middle of b so that we can use negative indices for accessing pos elements
for (int i = -n; i <= n; ++i)
pos[i] = INF;
int result = 0;
for (int i = 0, count = 0; i < n; ++i) {
count += a[i] ? 1 : -1;
result = max(i - pos[count], result);
pos[count] = min(i, pos[count]);
}
return result;
}
int main() {
int a[MAX_N] = {1,1,1,1,1,0,0,0,0,0,0,0,1};
//int a[MAX_N] = {0,0,1,0,1,0,1,0,1};
cout << solve(a, 13) << endl;
return 0;
}
O(N) solution in Python
'''
Created on Aug 14, 2013
@author: maheedhar
'''
def largestsetofonesandzeroes(arr):
count_ones = count_zeroes = 0
for item in arr:
if item == 1:
count_ones += 1
else:
count_zeroes += 1
i = 0
j = len(arr) - 1
while i < j:
diff = count_ones - count_zeroes
if diff == 0:
break
elif diff > 0:
if arr[i] == 1:
i += 1
count_ones -= 1
elif arr[j] == 1:
j -= 1
count_ones -= 1
else:#Both ends have zero
i += 1
count_zeroes -= 1
elif arr[i] == 0:
i += 1
count_zeroes -= 1
elif arr[j] == 0:
j -= 1
count_zeroes -= 1
else:#Both ends have Ones
j -= 1
count_ones -= 1
return j - i + 1, arr[i:j + 1]
print largestsetofonesandzeroes([0, 0, 1, 0, 1, 0, 1, 0])
I have tested the below code with the input arrays commented in the code.
static void Main(string[] args)
{
int x = 0;
int y = 0;
//int[] a = { 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//int[] a = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
//int[] a = { 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1};
//int[] a = {0, 0,1, 0, 1, 0, 1, 0, 1};
//int[] a = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1};
int[] a = {1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0};
int count_of_0 = 0;
int count_of_1 = 0;
int n = 0;
int i = 0;
int j = 0;
n = a.Length;
for (x = 0; x < n; x++)
{
for (y = x; y < n; y++)
{
if (a[y] == 0)
{
(count_of_0)++;
}
if (a[y] == 1)
{
(count_of_1)++;
}
if (count_of_0 == count_of_1)
{
if (y - x > j - i)
{
i = x;
j = y;
}
}
}
count_of_0 = 0;
count_of_1 = 0;
}
Console.WriteLine("The maximum length of the sub-array with equal number of 0's and 1's is {0} and the Sub-Array starts at {1} and ends at {2}", j - i + 1, i, j);
for (int k = i; k <= j; k++)
{
Console.WriteLine(a[k]);
}
}
It can be solved by using suffix arrays, by building all subarrays individually and looping over them to see if their length and sum of their values are equal to half(like length is 8 and sum is 4 as given in problem) and if it true ,storing the subarray length in max count variable.Keep updating this variable as you get bigger subarray satisfying the condition.
Guys .. I tried for the testcase - 101111111010
Output should be 4, but i dont think any of the programs give output.. This problem is bigger than it seems
This problem isn't very simple. The naive method is testing all the combination. The time complexity of that is O(n^2). Mukesh has gave us this answer. I think this question should be used dynamic programming method. We can list some special testcases:
00101010100: 8 two times the less number
00000100000: 2 two times the less number
10111111010: 4 two times (the rightest subarray)
10111010110: 4 two times (the middle subarray)
The problem of all the solutions is how to decide when the subarray start and end with the same number which is also the smaller count of 1's and 0's.
#include<stdio.h>
main(){
int ar[10],n,j;
printf("Enter number of elements:");
scanf("%d",&n);
for(j=0;j<n;j++){
printf("Enter a[%d]--->",j);
scanf("%d",&ar[j]);
}
/*printf("Enterd elements are:");
for(j=0;j<n;j++){
printf("%d--->",ar[j]);
}
}*/
int a,b,c=0,i,x,y;
for (i=0;i<n;i++){
//printf("i=%d\n",i);
int m=n;
while(m){
//printf("m=%d\n",m);
a=0;b=0;
for (j=i;j<m;j++){
//printf("j=%d\n",j);
if (ar[j]==1){
a=a+1;
//printf("a=%d\n",a);
}
else{
b=b+1;
//printf("b=%d\n",b);
}
}
if(a==b && (a+b)>=c){
c=a+b;
x=i;
y=m;
//printf("c=%d\n",c);
}
m--;
}
}
if(c>0){
printf("The large substring That contain equal number of 1's and 0's is:");
while(x<y){
printf("%d",ar[x]);
x++;
}
printf("\n");
}
else
printf("There is no large substring That contain equal number of 1's and 0's is\n");
}
O(n+k)
package careercup;
import java.util.BitSet;
/**
* Largest subarray with equal number of 0's and 1's.
*
*/
public class P4570783653298176 {
public static int subArrayLength(int[] input) {
int zeroes = 0;
int ones = 0;
int min = 0;
BitSet bitSet = new BitSet(input.length);
// Use BitSet to mark a change.
// Sample: 01011110000
// BitSet: -1-1---1111
for (int i = 0; i < input.length; i++) {
if (input[i] == 0)
zeroes++;
else
ones++;
int t = Math.min(zeroes, ones);
if (min != t) {
bitSet.set(i);
min = t;
}
}
int location = -1;
int count = 0; // Keeps track of current best value in a sequence
int best = 0; // Keeps track of best value until now
for (int i = 0; i < input.length;) {
if (location == -1 || Math.abs(bitSet.nextSetBit(i + 1) - location) <= 2) {
// Increment count whenever a change is seen in the ith or i+1th position
count++;
} else {
if (best < count)
best = count;
count = 1;
}
// No need to traverse the unset bits
location = bitSet.nextSetBit(i + 1);
i = bitSet.nextSetBit(i + 1);
// After the last bitset, break
if (i == -1)
break;
}
// best is just the number of changes, so 2*best is the answer
return 2 * best;
}
public static void main(String[] args) {
int[] input = { 0, 0, 1, 0, 1, 0, 1, 0, 1 };
System.out.println(P4570783653298176.subArrayLength(input));
}
}
#include<stdio.h>
#define n 12
int main()
{
int a[12]={1,0,1,1,1,1,1,1,1,0,1,0};
int i,j,c[2]={0,0},count=0,maxcount=0;
int low,high;
for(i=0;i<n;i++)
{ c[0]=0;c[1]=0;count=0;
for(j=i;j<n;j++)
{
if(a[j]==0) c[0]++;
else c[1]++;
if(c[0]==c[1])
{
count+=2;
if(count>maxcount)
{
low=i;
high=j;
maxcount=count;
}
}
}
}
printf("Maximum subarray is %d \t %d:\n",low,high);
for(i=low;i<=high;i++)
printf("%d\t",a[i]);
return 0;
}
cristian.botau is correct
Solution with start and end is not giving correct solution with
Further improvement in Mukseh's first code can be done by adding check for
if (i > n - result)
break;
Complete code will be as
int result = 0;
for (int i = 0; i < (n - 1); i++)
{
if (i > n - result)
break;
int[] count = new int[2] { 0, 0 };
for (int j = i; j < n; j++)
{
count[a[j]]++;
if ((count[0] == count[1]) && (count[0] > result / 2))
result = 2 * count[0];
}
}
main point in this problem is:
1) sub array of equal number of 0 and 1. So the length of sub array is even. So, we discard any sub array of odd length.
2) if sub array have equal number of 0 and 1 then sum of all element is must be equal to LengthOfArray/2 .. because length is even and have equal number of 1 and 0.
If we split this problem is this 2 part and only checking subarray of even size having sum equal to ArraySize/2 ...
main point in this problem is:
1) sub array of equal number of 0 and 1. So the length of sub array is even. So, we discard any sub array of odd length.
2) if sub array have equal number of 0 and 1 then sum of all element is must be equal to LengthOfArray/2 .. because length is even and have equal number of 1 and 0.
If we split this problem is this 2 part and only checking subarray of even size having sum equal to ArraySize/2 ...
This is how I could have done it.
let array:[Int] = [0,0,0,1,1,2,2,2,2,2,2,2,3,4,5,0,1,1,0,0]
func subArray(array:[Int]) -> Int {
let n = array.count
var countZeros = 0
var countOnes = 0
for (var i = 0; i < n; i++) {
if array[i] == 0 {
countZeros++
} else if array[i] == 1 {
countOnes++
}
}
return 2 * min(countZeros, countOnes)
}
subArray(array)
Here is O(n*n) solution.
int maxSequenceCount( int a[], int n )
{
int result = 0;
for( int i = 0; i < ( n - 1 ); i++ )
{
int count[2] = {0};
for( int j = i; j < n; j++ )
{
count[ a[j] ]++;
if( ( count[0] == count[1] ) && ( count[0] > result/2 ) )
result = 2 * count[0];
}
}
return result;
}
Here comes O(n) solution.
int maxSequenceCount( int a[], int n )
{
int count[2] = {0};
for( int i = 0; i < n; i++ )
{
count[ a[i] ]++;
}
int start = 0;
int end = n - 1;
while( ( start < end ) && ( count[0] != count[1] ) )
{
int more = ( count[0] < count[1] ) ? 1 : 0;
if( a[start] == more )
{
start ++;
count[more]--;
continue;
}
if( a[end] == more )
{
end --;
count[more]--;
continue;
}
count[ a[start] ]--;
start++;
}
return ( count[0] == count[1] ) ? 2 * count[0] : 0;
}
define B[n] as (num_of_0 - num_of_1) in A[0...n]
- Cheng Q. August 14, 2013then we want max(i - j) where B[i] == B[j]
it's an O(n) problem.