Yahoo Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1) create a temp array of same size as input array.
2) Now assume each zero as -1, so for every index i in temp array, store the count of ones and zeroes till that index in original array. (count of ones + (-1*count of zeroes))
3) find two farthest index which has same value. That would be the answer.

Why so, say at index i and j we have same values. --> S[i] == S[j] --> S[i] + count of ones - count of zeroes =S[i](since S[i] == S[j])
--> count of ones = count of zeroes.

Time complexity = O(n), Space complexity = O(n)

- m3th0d.itbhu August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- sam August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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 August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@sam  Using O(n) space you can definitely find duplicates in an array in O(n) time complexity.

- m3th0d.itbhu August 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@m3th0d Your algorithms seem problematic. Take the following example:
Array 1: 1 0 0 1 1 0
Temp1: 1 0 -1 0 1 0
Array 2: 0 0 0 0 1 1
Temp2: -1 -2 -3 -4 -3 -2

Obviously temp1 and temp2 have nothing in common at each index. But m=1 and n=5.

- coderfe December 23, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

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);
 }
}

- Sudhir October 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

#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;
	
}

- jag3048 August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

acunt -good naming))

- glebstepanov1992 August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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;
}

- tushar August 09, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

same length, read the question plz

- charlie January 06, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- Ashay Raut August 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
		
	}

}

- tester August 30, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- rohit September 03, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
-> 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);

}

}}

- supershal September 07, 2013 | 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