VMWare Inc Interview Question


Country: United States
Interview Type: Written Test




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

In most cases when the question is related to sub array the Kadane's algorithm is very useful. The real problem in this question is to find largest contiguous sub array for which difference 'numberOfZeros - numberOfOnes' is the biggest to maximize the sum of ones after flipping zeros.
Here is modified version of Kadane's algorithm to do this job.
It converts 0 to -1 and computes the sum till the sum is <=0 (there is more 0s then 1s).
If the sum is > 0 starts from the beginning.
The major difference compare to ordinary Kadane's algorithm is that we are looking for the biggest negative sum instead of positive.
Code:

public static void flipBits(int[] a) {

	int maxDiff = 0;
	int flipStartIndex = 0;
	int flipEndIndex = 0;
	int onesToFlip = 0;
	int totalNumberOfOnes = 0;

	int currentDiff = 0;
	int currentStart = 0;
	int currentOnesToFlip = 0;

	for (int i = 0; i < a.length; i++) {
	    if (a[i] == 0) {
			currentDiff -= 1;
	    } else {
			currentDiff += 1;
			currentOnesToFlip++;
			totalNumberOfOnes++;
	    }
	    if (currentDiff < maxDiff) {
			maxDiff = currentDiff;
			flipStartIndex = currentStart;
			flipEndIndex = i;
			onesToFlip = currentOnesToFlip;
	    } else if (currentDiff > 0) {
			currentDiff = 0;
			currentStart = i + 1;
			currentOnesToFlip = 0;
	    }
	}
	System.out.println(flipEndIndex - flipStartIndex + 1 - onesToFlip +   totalNumberOfOnes - onesToFlip);
}

Space O(1), Time O(n)

- thelineofcode January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

1, 0, 0, 1, 0, 0, 1,1,1,1, 0,1
Doesn't work for this input.

- Anonymous April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

@Anonymous may I ask why? The function returns 10 which looks like the maximum possible number of 1s after flipping.

- Anonymous April 13, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Please correct me if I am wrong.
This should handle the case of no zeros in the array. In which case, it should return the total number of ones present in the array or even say no zeros found.

public static void flip(int a[])
    {
        int maxdiff=0;
        int fsindex=0;
        int feindex=0;
        int onestoflip=0;
        int totalones=0;
        
        int currentdiff=0;
        int currentstart=0;
        int currentonestoflip=0;
        int zerocount=0;
        for(int i=0;i<a.length;i++)
        {
            if(a[i]==0)
            {
                currentdiff-=1;
                zerocount++;
            }
            else
            {
                currentdiff+=1;
                currentonestoflip++;
                totalones++;
            }
            if(currentdiff<maxdiff)
            {
                maxdiff=currentdiff;
                fsindex=currentstart;
                feindex=i;
                onestoflip=currentonestoflip;
            }
            else if(currentdiff>0)
            {
                currentdiff=0;
                currentstart=i+1;
                currentonestoflip=0;
            }
                
        }
        if(zerocount!=0)
            System.out.println(feindex - fsindex + 1 - onestoflip + totalones - onestoflip);
        else
            System.out.println("No zeros to flip, total number of ones"+totalones);
    }

- wolfengineer May 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hi, We can convert 1 to -1 can calculate maximum sum using kadane algorithm. am i right?

- Saket December 01, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the line
int flipEndIndex = 0;
should be changed to
int flipEndIndex = -1;

to accommodate for the case of all 1s in input

- ccc August 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

the line
int flipEndIndex = 0;
should be changed to
int flipEndIndex = -1;

to accommodate for the case of all 1s in input

- ccc August 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

int maximumNumber(vector<int> vec)
{
int max_so_far = 0;
int current_max = 1;
int index = 0;
int end = 0;
for(int i = 0; i < vec.size(); i++)
{
if(vec[i] == 0)
{
current_max++;
end++;
}
else
current_max--;

if(current_max <0)
{
current_max = 0;
index = i;
}

if (current_max < max_so_far)
max_so_far = current_max;

}
return end - index + 1;

}

- anonymous January 08, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void main(String args[]){
		int arr[] = {1, 0, 0, 1, 0, 0, 1, 0};
		int sum=0,maxsum=0,num=0;
		int startIndex=0,stopIndex=0,prevIndex=0;
		
		for(int i=0;i<arr.length;i++){
			if(arr[i] == 1){
				num = -1;
			}else if(arr[i] == 0){
				num = 1;
			}
			sum = sum + num;
			if(maxsum<sum){
				maxsum = sum;
				prevIndex = startIndex;
				stopIndex = i;
			}else if(sum<0){
				sum = 0;
				startIndex = i+1;
			}
		}
		
		for(int j=prevIndex;j<=stopIndex;j++){
			System.out.print(" "+arr[j]);
		}
	}

- Coder January 03, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here my solution I looking for maximum interval sum

#define maxn 100505
using namespace std;
int n,m,k,x,curn,D[maxn],C[maxn] ;
string cad;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>C[i];
		D[i] = D[i-1] + C[i];
		if(C[i] == 0)
			C[i]=1;
		else C[i]=-1;
	}
	int ini = 1,fin=1;
	int sum = C[1];
	int res = C[1];
	int x=1,y=1;
	while(ini <= n)
	{
		if(sum > res)
		{
			res = sum;
			x = ini;
			y = fin;
		}
		if(sum < 0)
		{
			if(fin <= n){
				fin++;
				sum=C[fin];
			}
			ini = fin;
		}else{
			if(fin<=n){
				fin++;
				sum+=C[fin];
			}else
			{
				sum-=C[ini];
				ini++;
			}
		}
	}
	cout<<D[x-1] + D[n] - D[y] + res + ( (y-x+1) - res) / 2;
	return 0;
}

- vlade087 January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is simple, we will solve it like maximum sub array problem. All you need it is to change 1 to -1 and 0 to 1. So maximum subarray will be the answer . Then you build up array where c[i] is sum from 0 to i. Then you iterate over this array, for each j position answer will be cumul[j] - cumul[k], where k is a position of minimum element from left to i. We need to know this minimum and update it when it changes. Answer - pair of k and j, which have produced maximum difference of cumul[j] - cumul[k].

def cumulative(a):
    output = [a[0]]

    for i in range(1,len(a)):
        output.append(output[i - 1] + a[i])

    return output

def prepare(a):
    b = a
    for i in range(0,len(a)):
        if b[i] == 1:
            b[i] = -1
        else:
            b[i] = 1
    return b

def sub_array(a):
    cumul = cumulative(a)
    a = prepare(a)

    left = 0 #Current left minimum position
    left_global = 0#Global left minimum position
    right = 0# right side of maximal interval
    left_min = 999999#left min value
    global_max = -999999#global max value
    right = 0

    for r in range(0,len(a)):
        #if current sum if bigger then previous
        if cumul[r] - left_min > global_max:
            global_max = cumul[r] - left_min
            right = r
            left_global = left + 1
        #if current element cumulative sum if bigger than prevous minimum
        if cumul[r] < left_min:
            left = r
            left_min = cumul[r]

    return (left_global,right)

- glebstepanov1992 January 04, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;


public class Solution {

public static void main(String[] args) {
try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
System.out.print("Enter array size: ");
int length = Integer.parseInt(br.readLine().trim());

System.out.println("Enter sequence: ");
String[] arrayStr = br.readLine().trim().split(" ");

if(arrayStr.length != length) {
throw new Exception(String.format("Size of N - <%d> and size of Array - <%d> differ.", length, arrayStr.length));
}

int max = 0;
int L = 0;
int Lmax = 0;
int Rmax = 0;
int current = 0;
for(int i = 0; i < length; i++) {
if(arrayStr[i].equals("0")) {
current++;
} else {
current--;
}

if(current <= 0) {
L = i;
} else if(current > max) {
Lmax = L;
Rmax = i;
max = current;
}
}

int[] tmpArray = flip(arrayStr, Lmax, Rmax);

int aces = 0;
for(int k = 0; k < length; k++) {
if(tmpArray[k] == 1) aces++;
}
System.out.println(Lmax + " - " + Rmax);
System.out.println(aces);
} catch(Exception e) {
e.printStackTrace();
}
}

private static int[] flip(String[] array, int L, int R) throws Exception {

int length = array.length;

int[] arrayInt = new int[array.length];
for(int i = 0; i < array.length; i++) {
arrayInt[i] = Integer.parseInt(array[i].trim());
}

if(L > length || L < 0 || R > length || R < 0 || L > R) {
throw new Exception("Constraint: 0 <= L <= R < n");
}

for(int i = L; i <= R; i++) {
arrayInt[i] ^= 1;
}

return arrayInt;
}
}

- Alkis April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.*;


public class Solution {	

	public static void main(String[] args) {
		try(BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
			System.out.print("Enter array size: ");
        	int length = Integer.parseInt(br.readLine().trim());
        	
        	System.out.println("Enter sequence: ");
        	String[] arrayStr = br.readLine().trim().split(" ");
        	
        	if(arrayStr.length != length) {
        		throw new Exception(String.format("Size of N - <%d> and size of Array - <%d> differ.", length, arrayStr.length));
        	}
        	
        	int max = 0;
        	int L = 0;
        	int Lmax = 0;
        	int Rmax = 0;
        	int current = 0;
        	for(int i = 0; i < length; i++) {
        		if(arrayStr[i].equals("0")) {
        			current++;
        		} else {
        			current--;
        		}
        		
        		if(current <= 0) {
        			L = i;
        		} else if(current > max) {
        			Lmax = L;
        			Rmax = i;
        			max = current;
        		}
        	}
        	
			int[] tmpArray = flip(arrayStr, Lmax, Rmax);
			
			int aces = 0;
			for(int k = 0; k < length; k++) {
				if(tmpArray[k] == 1) aces++;
			}
        	System.out.println(Lmax + " - " + Rmax);
        	System.out.println(aces);
		} catch(Exception e) {
			e.printStackTrace();
		}
	}
	
	private static int[] flip(String[] array, int L, int R) throws Exception {
		
		int length = array.length;
		
    	int[] arrayInt = new int[array.length];
    	for(int i = 0; i < array.length; i++) {
    		arrayInt[i] = Integer.parseInt(array[i].trim());
    	}
		
		if(L > length || L < 0 || R > length || R < 0 || L > R) {
			throw new Exception("Constraint: 0 <= L <= R < n");
		}
		
		for(int i = L; i <= R; i++) {
			arrayInt[i] ^= 1; 			
		}
		
		return arrayInt;
	}
}

- Alkis April 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Above code is returning 4 instead of 6 as an output

- sam September 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
def result(arr):
maxcount = 0
ones = 0
count = 0
for i in range(len(arr)):
if (arr[i] == 0):
count += 1
else:
count -= 1
ones += 1

if (count > maxcount):
maxcount = count

if (count < 0):
count = 0
return maxcount + ones
}}

- Sopolenius April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{def result(arr):
maxcount = 0
ones = 0
count = 0
for i in range(len(arr)):
if (arr[i] == 0):
count += 1
else:
count -= 1
ones += 1

if (count > maxcount):
maxcount = count

if (count < 0):
count = 0
return maxcount + ones }}

- Sopolenius April 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int main()
{
int n,i;
int *arr;
int startIndex=-1;
int endIndex = -1;
int countOnes=0;
int sum =0, max=0,subtractSum=0;

scanf("%d",&n);
arr = (int *)malloc(sizeof(int)*n);
for(i=0;i<n;i++) {
scanf("%d",&arr[i]);
}
for(i=0;i<n;i++) {
if(arr[i] == 1 && startIndex == -1) {
countOnes++;
continue;
}
else if((sum - subtractSum) <= 0 && startIndex != -1) {
startIndex = i;
subtractSum =0;
sum = 0;
}
else if(arr[i] == 0) {
if(startIndex == -1) {
startIndex = i;
}
sum++;
}
else if(arr[i] == 1){
subtractSum++;
}
if(sum > max) {
max = sum;
endIndex = i;
}
}
if(endIndex==-1)
endIndex = i;
else if(startIndex != endIndex)
endIndex++;
for(i=endIndex;i<n;i++) {
if(arr[i] == 1) {
countOnes++;
}
}
printf("%d",countOnes+max);
return 0;

- Anonymous September 14, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
    for (int j = N-1; j > i; --j) {
         int k = i;
         while (k < j) {
                 if (!A[k]) {
                             R[i][j]++;
                 }
          }
     }
}

- Suren September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Following is bruit-force cum semi-dynamic solution. R[N-1][N-1] matrix stores the number of 1s for each iteration. The stored R matrix can be used in computation to optimize the solution via dynamic-programming.

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

R[N-1][N-1] = {0};
for (int i = 0; i < N-1; ++i) {
    for (int j = N-1; j > i; --j) {
         int k = i;
         while (k < j) {
                 if (!A[k]) {
                             R[i][j]++;
                 }
          }
     }
}
return max{R[i][j]; where 0 < i < N-1 and 0 < j < N-1}

- Suren September 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Here is the best/optimum solution through dynamic-programming...

Assume Given
N=8
A[0...7] = {1,0,0,1,0,0,1,0}

int Zeros (int A[], int i, int j) {
	int countZeros = 0;
	if (i < j) {
		for (int k = i, k < j; ++k) {
			if (!A[k]) {
				countZeros++;
			}
		}
	}
	return countZeros;
		
}

int R[N-1][N-1] = {-1};

int flip (int A[], int R[][], int i, int j) {
	if (i < j) {
		if (R[i][j] != -1) {
			return R[i][j];
		} else {
			R[i][j] = max{ Zeros(A, i, j),
				       1&A[i] + flip(A, R, i+1, j),
				       flip(A, R, i, j-1) + 1&A[j],
				       1& A[i] + flip(A, R, i+1, j-1) + 1&A[j]
				  };
		}
	} else if (i == j){
		return !A[i];
	} else {
		return 0;
	}
	return R[i][j];
}

int main () {
	printf("Max Number of 1s: ", flip (A, R, 0, N-1));
}

- Suren September 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In above code, replace call to function f() by flip().

- Suren September 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

typedef struct res_s
{
	int i;
	int j;
	int sum;
}res_t;

res_t find_sub_array(int* a, int size)
{
	res_t max = {0};
	res_t maxcur = {0};
	res_t* maxsub = NULL;
	int i;

	maxsub = (res_t*)calloc(sizeof(res_t),size);
	max.i= -1*1000;
	maxcur.i=max.i;

	for(i=0; i<size;++i)
	{
		if(maxcur.sum < 0)
		{
			maxcur.sum =a[i];	
			maxcur.i =i;
			maxcur.j =i;
		}
		else
		{ 
			maxcur.sum+=a[i];
			maxcur.j = i;
		}

		if(maxcur.sum > max.sum)
			max = maxcur;

		maxsub[i] = max;
	}
	return maxsub[size-1];
}

/*
* calc max sum based on start and end indexes found
* flip bits in [s,e] range, before ocunting
*/
int calc_sum(int* a,  int n, int s, int e)
{
	int i,sum = 0;
	int toadd = 0;

	for(i=0; i< n;++i)
	{
		if((i < s) || (i > e))
		{
			toadd = a[i];
		}

		if(i >=s && i <= e)
		{
			if(0 == a[i])
				toadd = 1;
		}
		sum+=toadd;
		toadd = 0;
	}

	return sum;

}
int main()
{
	int o[] = {1,0,0,1,0,0,1,0};
	int b[] = {-1,1,1,-1,1,1,-1,1};
	//int a[] = {-1,-2,3,4,-5,6};

	res_t rest = find_sub_array(b, 8);

	printf("%d,%d=%d\n", rest.i, rest.j, calc_sum(o, 8, rest.i, rest.j));

	return;
}

}

- pv March 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1 #include<iostream>
2 using namespace std;
3
4 int calOnes(int *ptr,int);
5
6 int main()
7 {
8 int a[]={0,1,0,1,0,1,0,1,0,1,0,0,1,1};
9 //int a[]={1,0,1,0,0,0,1,0,0,1,1,1,1,0,0,1,1,1,0,0,0,1};
10 int i=calOnes(a,sizeof(a)/sizeof(a[0]));
11
12 cout<<i<<endl;
13
14 }
15
16 int calOnes(int *ptr,int len)
17 {
18 int max_diff = 0;
19 int i;
20 int diff = 0;
21 int orig_ones =0;
22 int zero2one=0;
23 int one2zero=0;
24 for(i = 0;i < len;i++)
25 {
26
27
28 if(ptr[i] == 0)
29 {
30 if(diff <= 0)
31 {
32 zero2one = 1;
33 max_diff = zero2one;
34 one2zero = 0;
35 diff = 1;
36 continue;
37 }
38 ++zero2one;
39 }
40 else
41 {
42 ++orig_ones;
43 ++one2zero;
44 }
45 diff = zero2one - one2zero;
46 if( diff > max_diff)
47 max_diff = diff;
48
49
50 }
51 // cout<<max_diff<<" "<<orig_ones;
52 return(max_diff+orig_ones);
53
54 }

- anand December 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution(object):
    def maxOne(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None or len(nums) == 0:
            return 0
        max_sum = nums[0]
        dp = [0] * len(nums)
        dp[0] = -1 if nums[0] == 1 else 1
        res = 0
        for i, v in enumerate(nums):
            if i == 0:
                res = res + 1 if v == 1 else 0
                continue
            if v == 0:
                if dp[i-1] > 0:
                    dp[i] = dp[i-1] + 1
                else:
                    dp[i] = 1
            else:
                res = res + 1
                if dp[i-1] - 1 > 0:
                    dp[i] = dp[i-1] - 1
                else:
                    dp[i] = 0

            max_sum = max(max_sum, dp[i])

        return res + max(max_sum, 0)

- Anonymous January 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Solution(object):
    def maxOne(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if nums is None or len(nums) == 0:
            return 0
        max_sum = nums[0]
        dp = [0] * len(nums)
        dp[0] = -1 if nums[0] == 1 else 1
        res = 0
        for i, v in enumerate(nums):
            if i == 0:
                res = res + 1 if v == 1 else 0
                continue
            if v == 0:
                if dp[i-1] > 0:
                    dp[i] = dp[i-1] + 1
                else:
                    dp[i] = 1
            else:
                res = res + 1
                if dp[i-1] - 1 > 0:
                    dp[i] = dp[i-1] - 1
                else:
                    dp[i] = 0

            max_sum = max(max_sum, dp[i])

        return res + max(max_sum, 0)

- adiggo January 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class IntFlip {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num;
int temp1 = 0;
System.out.println("Enter the length of the array");
num = in.nextInt();

int[] Arr = new int[num];
System.out.println("Enter the elements of the array");
for(int i = 0;i<Arr.length;i++)
{
int temp = in.nextInt();
if(temp == 0 || temp == 1)
{
Arr[i] = temp;
}
else
{
System.out.println("Please enter either 0 or 1");
i = i-1;
}
}

int l,r;
System.out.println("Enter the lower limit");
l = in.nextInt();
while(l < 0)
{
System.out.println("Invalid!!Please enter again");
l = in.nextInt();
}

System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
System.out.println("Invalid!!Please try again");
r = in.nextInt();
}

Flip(Arr,l,r);

System.out.println("Array after flipping");

for(int f = 0;f<Arr.length;f++)
{
System.out.println(Arr[f]);
if(Arr[f] ==1)
{
temp1 = temp1 + 1;
}
}

System.out.println("The number of 1s in the array is" +temp1);

/*System.out.println("The array is as follows");

for(int j=0;j<Arr.length;j++)
{
System.out.println(Arr[j]);

}*/

}
public static void Flip(int[] Array, int left, int Right)
{
for(int k = left;k<=Right;k++)
{
if(Array[k] == 0)
{
Array[k] = 1;

}
else if(Array[k] == 1)
{
Array[k] = 0;
}
}
}
}

- Anonymous April 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;
public class IntFlip {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
int num;
int temp1 = 0;
System.out.println("Enter the length of the array");
num = in.nextInt();

int[] Arr = new int[num];
System.out.println("Enter the elements of the array");
for(int i = 0;i<Arr.length;i++)
{
int temp = in.nextInt();
if(temp == 0 || temp == 1)
{
Arr[i] = temp;
}
else
{
System.out.println("Please enter either 0 or 1");
i = i-1;
}
}

int l,r;
System.out.println("Enter the lower limit");
l = in.nextInt();
while(l < 0)
{
System.out.println("Invalid!!Please enter again");
l = in.nextInt();
}

System.out.println("Enter the upper limit");
r = in.nextInt();
while(r > Arr.length-1)
{
System.out.println("Invalid!!Please try again");
r = in.nextInt();
}

Flip(Arr,l,r);

System.out.println("Array after flipping");

for(int f = 0;f<Arr.length;f++)
{
System.out.println(Arr[f]);
if(Arr[f] ==1)
{
temp1 = temp1 + 1;
}
}

System.out.println("The number of 1s in the array is" +temp1);

/*System.out.println("The array is as follows");

for(int j=0;j<Arr.length;j++)
{
System.out.println(Arr[j]);

}*/

}
public static void Flip(int[] Array, int left, int Right)
{
for(int k = left;k<=Right;k++)
{
if(Array[k] == 0)
{
Array[k] = 1;

}
else if(Array[k] == 1)
{
Array[k] = 0;
}
}
}
}

- Sharath Ramesh April 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why everything so complected. should run max one's.. check this solution.

int bitRotate() {
	int L = 1, R = 5;
	int size = 8;
	int arr[8] = { 1, 0, 0, 1, 0, 0, 1, 0 };
	
	int count = 0;
	for (int i = 0; i < 8; i++){
		if (i >= L && i <= R) 
			arr[i] = !arr[i];

		if (arr[i] == 1) count++;
	}
	return count;
}

- Sumedh Shende July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int bitRotate() {
	int L = 1, R = 5;
	int size = 8;
	int arr[8] = { 1, 0, 0, 1, 0, 0, 1, 0 };
	
	int count = 0;
	for (int i = 0; i < 8; i++){
		if (i >= L && i <= R) 
			arr[i] = !arr[i];

		if (arr[i] == 1) count++;
	}
	return count;
}

- Sumedh Shende July 26, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include<stdio.h>
#include<stdbool.h>
int flipbits(bool arr[], int n)
{
	// For the example 0 0 0 1 0 1
	int i,origOnes=0,count=0;
	int value[10000];
	
	for(i=0;i<n;i++)
	{
		if(arr[i]==1)
		{
			origOnes=origOnes+1;
			value[i]=1;
		}
		else if(arr[i]==0)
		{
		    value[i]=-1;
		    
		}
		//It now becomes -1 -1 -1 1 -1 1
		//Now Flip the bits and find maximum contiguous array 
	}
	    
	    for(i=0;i<n;i++)
	    {
	        if(arr[i]==true)
	            count++;
	    }
	    if(count==n)
	    {
	        return count;
	    }
	    
	    
	        
		for(i=0;i<n;i++)
		{
			value[i] = -value[i];
		}
		
		//Now, the array becomes 1 1 1 -1 1 -1
		//Here comes the fun part, Just apply Kandane's algorithm 
		//and find the maximum contiguous sub-array
		int MaxSoFar=-99999, MaxEndingHere=0;
		for(i=0;i<n;i++)
		{
			MaxEndingHere = MaxEndingHere + value[i];
			if(MaxEndingHere>MaxSoFar)
				MaxSoFar = MaxEndingHere;
			if(MaxEndingHere<0)
				MaxEndingHere=0;
		}
		//Now we know maximum contiguous sub-array is from arr[0] to arr[4]
		//I guess we flip everything back to normal? no!
		//We know MaxSoFar right now is 3
		//Number of ones initially was 2
		//To get maximum number of ones, ass the original number of ones to MaxSoFar
		return (origOnes + MaxSoFar);
}
int main()
 {
        int a[10000];
        bool arr[10000];
    	int i,j,m,n,ans;
     	scanf("%d",&m);
     	
    	for(j=0;j<m;j++)
    	{
        	scanf("%d",&n);
        	for(i=0;i<n;i++)
        		scanf("%d",&a[i]);
        	for(i=0;i<n;i++)
        	{
        	    if(a[i]==1)
        	        arr[i]=1;
        	    else if(a[i]==0)
        	        arr[i]=0;
        	}
        	ans=flipbits(arr,n);
            printf("%d\n",ans);  
        }
      
	return 0;

}

- Anish Mahapatra May 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

go through the array, while doing it, perform the following:
1. count the number of 1's in your input
2. keep a custom counter +1 if we see a zero, -1 if we see a one, do not count leading 1's
3. use a separate variable to keep track of the max value of your counter
output= max value of your counter + the number of 1's in your input

- YYFF January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

add the 1's which dont occur in this max value and not all the 1's encountered till now

- User123 January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I use a vector to store the zeros like <position in array, k(kth 0)>
Each time, we only need to check if the continuous two zeros in vector can generate more 1 after flipping. If yes, go ahead. If not, record the max 1 can generate now. And return back to original array and do the same step above.
code is below. O(n)

int mostone(int *c, int len){
		vector < vector < int >> poszero;
		int count = 1;
		for (int i = 0; i < len; i++){
			if (*(c + i) == 0) poszero.push_back({ i, count++ });
		}
		vector<int> cur = poszero[0];
		vector<int> next;
		int change= 0;
		int maxone = 0;
		count = 1;
		int intevl = 0;
		for (int i = 1; i < poszero.size(); i++){
			next = poszero[i];
			//dont include the last zero in this inteval
			int increase = (next[1] - cur[1] + 1 - (next[0] - cur[0] + 1 - (next[1] - cur[1] + 1)))-1;
			if (increase>=0){
				change += increase;
			}
			else{
				maxone = std::max(maxone, change+1); //plus back last one
				change = 0;
			}
			cur = next;
		}
		return len-poszero.size()+std::max(maxone,change+1);
	}

- hahaha January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Doesn't work for { 0,0,0,0,1,1,1,0,0,0,0 }.
Correct ans is 8, whereas output is 7

- thelineofcode January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

dont know what "1's which dont occur in this max value and not all the 1's encountered till now" means, but rest assured, the math works out in the end.

public int ggff(int N, int [] A)
{
	int maxctr=0;
	int ctr=0;
	for (int i=0;i<N;i++)
	{
		if (A[i]==1)
			ctr--;
			else ctr++;
		if (ctr<maxctr)
		maxctr=ctr;
		
	}
	if (max<0) /// handle inputs that looks like 111111111...
	return 0;
	else return maxctr;
}

- YYFF January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

dont know what "1's which dont occur in this max value and not all the 1's encountered till now" means, but rest assured, the math works out in the end.

public int ggff(int N, int [] A)
{
	int maxctr=0;
	int ctr=0;
	for (int i=0;i<N;i++)
	{
		if (A[i]==1)
			ctr--;
			else ctr++;
		if (ctr<maxctr)
		maxctr=ctr;
		
	}
	if (max<0) /// handle inputs that looks like 111111111...
	return 0;
	else return maxctr;
}

- YYFF January 02, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

typos..

public int ggff(int N, int [] A)
{
	int maxctr=0;
	int ctr=0;
	int ones=0;
	for (int i=0;i<N;i++)
	{
		if (A[i]==1)
			{ctr--;
			ones++;
			}
			else ctr++;
		if (ctr<maxctr)
		maxctr=ctr;
		
	}
	if (max<0)
	return N;
	else return maxctr+ones;
}

- YYFF January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 votes

Doesn't work for: {1,1,1,0,0,1,1,1,0,0};

- thelineofcode January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Forgot to disregard leading 1's

- YYFF January 02, 2014 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

1 0 0 1 0 0 1 0
flip17
1 1 1 0 1 1 0 1
max(1):6
0 0 0 0 1 1 1 0 0 0 0
flip010
1 1 1 1 0 0 0 1 1 1 1
max(1):8

#include <iostream>
#include <vector>

int check_begin(const std::vector<int>& vec) {
	int cnt_zero;
	int cnt_one;
	
	int bigger = 0;
	int saved_i;

	for(int i = 0; i < vec.size(); i++) {
		cnt_one = 0;
		cnt_zero = 0;

		for(int j = i; j < vec.size(); j++) {
			if(vec[j] == 0) {
				++cnt_zero;
			} else {
				++cnt_one;
			}
		}

		int delta = cnt_zero - cnt_one;
		if(delta > bigger || bigger == 0) {
			bigger = delta;
			saved_i = i;
		}
	}

	return saved_i;
}

int check_end(const std::vector<int>& vec, int begin) {
	int cnt_zero;
	int cnt_one;
	
	int bigger = 0;
	int saved_i;

	for(int i = vec.size() - 1; i > begin; i--) {
		for(int j = begin; j <= i; j++) {
			cnt_one = 0;
			cnt_zero = 0;
			
			if(vec[j] == 0) {
				++cnt_zero;
			} else {
				++cnt_one;
			}
		}

		int delta = cnt_zero - cnt_one;

		if(delta > bigger || bigger == 0) {
			bigger = delta;
			saved_i = i;
		}
	}

	return saved_i;
}

static void flip(std::vector<int>& vec, int begin, int end) {
	std::cout << "flip" << begin << end << std::endl;
	for(int i = begin; i <= end; i++) {
		if(vec[i] == 0) {
			vec[i] = 1;
		} else {
			vec[i] = 0;
		}
	}
}

static int count_one(const std::vector<int>& vec) {
	int cnt = 0;
	for(auto c: vec) {
		if(c == 1)
			++cnt;
	}

	return cnt;
}

static void print_vec(const std::vector<int>& vec) {
	for(auto c: vec) std::cout << c << " ";
	std::cout << std::endl;
}

int main() {
	std::vector<int> binvec{1, 0, 0, 1, 0, 0, 1, 0};
	std::vector<int> binvec_test{0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0};
	int begin, end;
	
	print_vec(binvec);
	begin = check_begin(binvec);
	end = check_end(binvec, begin);
	flip(binvec, begin, end);
	print_vec(binvec);
	std::cout << "max(1):" << count_one(binvec) << std::endl;
	

	print_vec(binvec_test);
	begin = check_begin(binvec_test);
	end = check_end(binvec_test, begin);
	flip(binvec_test, begin, end);
	print_vec(binvec_test);
	std::cout << "max(1):" << count_one(binvec_test) << std::endl;

	return 0;
}

- Felipe Cerqueira January 02, 2014 | 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