Yahoo Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
Two comments:
1) It is only for one array and not two.
2) It is not O(n), since you still need to find two farthest index which have same value. You cannot just check the value at starting index with the rest of the array.
For example if array is: 1 1 1 1 1 0 0 1 1 1 1 1.
Temp array: 1 2 3 4 5 4 3 4 5 6 7 8. Actual answer would be : m = 3rd index + 1, n = 7th index. In fact there are multiple answers, I am just searching for values from the starting. So complexity is actually: O(n*n) in worst case.
To make it O(n), one suggested method is to take a hash table and start saving the index of the values from temp array. If the value repeats, find the diff with existing index and if the difference is greater than maxdiff then update it.
@sam Using O(n) space you can definitely find duplicates in an array in O(n) time complexity.
public class MaxSubarrayEqualOnesZeros
{
public static void main(String[] args)
{
int[] arr =
{ 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1,
0, 1, 1, 0, 1, 0, 0, 0 };
printMaxSubarray(arr);
}
private static void printMaxSubarray(int[] arr)
{
Integer[] diffMap = new Integer[arr.length * 2 + 1];
diffMap[arr.length] = -1;
int sum = 0;
int maxLength = 0;
int maxStart = -1;
int maxEnd = -1;
for (int i = 0; i < arr.length; ++i)
{
if (arr[i] == 0)
sum -= 1;
else
sum += 1;
Integer prevIndex = diffMap[arr.length + sum];
if (prevIndex == null)
diffMap[arr.length + sum] = i;
else
{
if (i - prevIndex > maxLength)
{
maxLength = i - prevIndex;
maxStart = prevIndex + 1;
maxEnd = i;
}
}
}
System.out.println("indices (" + maxStart + "," + maxEnd + ")");
System.out.println("length=" + maxLength);
}
}
#include<stdio.h>
#include<conio.h>
int main()
{
int a[]={1,0,1,0,0,1,1,1,0};
int b[]={1,0,1.0,0,1,1,1,0,1,0},m,n;
m=9,n=11;
int x,y,i,j;
int acunt_0=0,acunt_1=0,bcunt_0=0,bcunt_1=0;
for( i=0;i<n;i++)
{
if(b[i]==0)
bcunt_0++;
else
bcunt_1++;
for( j=m-1;j>=0;j--)
{
if(a[j]==0)
{
acunt_0++;
break;
}
else
{
acunt_1++;
break;
}
printf(" bcount value %d\n", acunt_0);
//break;
}
if(acunt_0==bcunt_0 && acunt_1==bcunt_1)
{
x=i,y=j;
printf("fond %d\t fond%d\n",x,y);
break;
}
else
{
m--;
}
}
getch();
return 0;
}
Size of Array is given as equal. but u had taken 'a' and 'b' of unequal size. correct me if i'am wrong.
check this:
#include<stdio.h>
#include<conio.h>
#include<conio.h>
int main()
{
int a[]={1,0,1,0,0,1};
int b[]={0,1,1,1,0,0};
int i,j,max,x,y,z=1;
max=5;
int acount_1=3;
int acount_0=3;
int bcount_1=0;
int bcount_0=0;
for(i=5,j=0;i>=0,j<=5;i--,j++)
{
if(b[j]==0)
bcount_0++;
if(b[j]==1)
bcount_1++;
if(a[i]==0)
acount_0--;
if(a[i]==1)
acount_1--;
if(acount_0==bcount_0 && bcount_1==acount_1)
{
if(z)
{
max=abs(j-i);
z=0;
x=i;
y=j;
}
if(abs(j-i)>max)
{
max=abs(j-i);
x=i;
y=j;
}
}
}
printf("i=%d j=%d max=%d",x,y,max);
getch();
return 0;
}
In single array
Method to find subarray of equal 0's and 1's is :
1. Replace each 0 by -1
2. Take cumulative sum in array say "csum[i]=a[0]+a[1]+..+a[i]
3. Let len1 = the max index 'i' where you have csum[i]=0
4. Take hashmap<int,int> hmap
int len2=MIN_INT;
for(int i=0;i<len_of_array;i++)
{
if(!(hmap.containsKey(csum[i])) // csum[i] acts as key and its not present
{
hmap.put(csum[i],i) ; // put it with index i as value
}
else // key is present already in hashmap
{
int lenTemp = i - hmap.get(csum[i]);
if(len2<lenTemp)
len2=lenTemp
}
}
ans = max(len1,len2)
We can use this method for this question by merging both arrays to one array.
public class puzz2 {
public static int[] count1sInArray(int[] array){
int count = 0;
for(int i=0;i<array.length;i++){
if(array[i]==1)
array[i]=++count;
else
array[i]=--count;
}
return array;
}
public static void printArray(int[] arr){
for(int i=0;i<arr.length;i++, System.out.print(", "))
System.out.print(arr[i]);
System.out.println();
}
public static void main(String[] args) {
int[] array1 = {1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1};
int[] array2 = {0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0};
int[] array1_temp = count1sInArray(array1);
int[] array2_temp = count1sInArray(array2);
printArray(array1_temp);
printArray(array2_temp);
int max = 0;
for(int i=0;i<array1_temp.length-1;i++){
if(array1_temp[i]==array2_temp[i]){
if(i>max)
max = i;
}
}
System.out.println("m : 0 n : "+max);
}
}
public bool equalitycheck(int [] A, int B, ref int n, ref int m)
{
if(A.length && B.length ==0 ) return true;
stack<int> zero = new stack<int>();
stack<int> one = new stack<int>();
int i=0;
if(A.length !=0)
{
while(i<A.length)
{
if(A[i]==0)
zero.push(i++);
if(A[i]==1)
zero.push(i++);
}
}
if(B.length !=0)
{
while(i<B.length)
{
if(A[i]==0)
zero.push(i++);
if(A[i]==1)
zero.push(i++);
}
}
while(zero.count!=one.count)
{
if(zero.count>one.count)
zero.pop();
if(zero.count<one.count)
one.pop();
}
if(zero.count ==0 || one.count ==0)
return false;
m=zero.peek()>one.peek()?zero.peek():one.peek();
while(Z.count!=1 && O.count!=1)
{
O.pop();
z.pop();
}
n=O.peek()>Z.peek()?Z.peek():O.peek();
return true;
}
{{
-> two arrays of length n
-> made up of 0 and 1
-> m-n should be max;
-> equal no of 0 and 1.
-> find m and n in O(n)
-> find equal no of 0 and 1. 0 = -1 and 1 = +1
-> min index of equal 0,1 of a and max index of equal 0,1 wiill give m, n
public class findMaxMN(int a[], int[b]){
int a_min = n+1, b_min = n+1, a_max=-1, b_max=-1;
int a_count = 0 , b_count = 0;
for(int i=0;i< n;i++){
if(a[i] == 1){
a_count++;
}else{
a_count--;
}
if(b[i] == 1){
b_count++;
}else{
b_count--;
}
if(a_count == 0){
a_min = min(a_min, i);
a_max = max(a_max, i);
}
if(b_count == 0){
b_min= min(b_min,i);
b_max= max(b_max, i);
}
}
if( a_min == n+1 || b_min ==n+1){
System.out.println("equal no of 0 and 1 not found");
}
if( a_min == n+1 && b_min != n+1){
m = b_min;
n = b_max;
}
if( b_min == n+1 && a_min != n+1){
m = a_min;
n= a_max;
}
m = min(a_min, b_min);
n = max(a_max, b_max);
}
}}
- m3th0d.itbhu August 11, 2013