Amazon Interview Question for SDE-2s


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

public static int longestSequence(int [] array, int k){
    	int maxLength = 0;
    	int start = 0;
    	int runningLength = 0;
    	int tmpK = k;
    	
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == 1){
    			runningLength++;
    		}
    		else if(tmpK > 0 && tmpK < k){
    			tmpK--;
    			runningLength++;
    		}
    		else if(tmpK == k){
    			tmpK--;
    			runningLength++;
    			start = i;
    		}
    		else{ //tmpK == 0
    			tmpK = k;
    			maxLength = Math.max(maxLength, runningLength);
    			runningLength = 0;
    			int tmp = i;
    			i = start;
    			start = tmp;
    		}
    	}
    	
    	return Math.max(maxLength, runningLength);
    }

- emiaj.123 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

This could be solved by Two Pointers in O(n) time.

vector<int> a = { 1, 1, 0, 0, 1, 1, 1, 0, 1 ,1 };
        // k is the number of bits that can be flipped
	int k = 1;

	int len = 0;
	for (int fast = 0, slow = 0; fast < a.size(); ++fast) {                
		if (a[fast] == 0) --k;
		for (; k < 0; ++slow) {
			if (a[slow] == 0) ++k;
		}
				
		len = max(len, fast - slow + 1);
	}

- clark.li86 February 19, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

C++ Solution:

Note:
1) If we know that 's' has a maximum of 64 elements, we can replace the vector with a uint64 variable
2) solution assumes that the given k is the maximum number of flips allowed, so if k = 2, the number of possible flips could be 0, 1 or 2.

std::vector<size_t> zerosToFlip(const std::vector<bool>& s, const uint64_t k)
{
    std::vector<size_t> currIdxList; // list of the current flipped elements
    std::vector<size_t> finalIdxList; // final list of the flipped elements
    
    uint64_t maxNumOnes = 0; // maximum number of consecutive ones
    uint64_t numOnes = 0; // current number of consecutive ones
    uint64_t availableFlips = k; // remaining number of flips
    
    // for each element in the sequence
    for (size_t i = 0; i < s.size(); ++i)
    {
        // get the current element
        const bool currEl = s[i];
        
        if (currEl == 1)
        {
            // increase the number of consecutive ones
            ++numOnes;
        }
        else
        {
            // the current element is zero
            
            if (availableFlips > 0)
            {
                // we still have flips,
                // flip the zero and append the index to the list
                currIdxList.push_back(i);
                --availableFlips;
                ++numOnes;
            }
            else
            {
                // no more flips available
                
                if (numOnes >= maxNumOnes)
                {
                    // the sequence of flips produce
                    // a longer sequence of consecutive 1 w.r.t
                    // the previous sequence of flips
                    
                    // save the new max number of consecutive ones
                    maxNumOnes = numOnes;
                    
                    // save the list of indexes as the final one
                    // at the moment this is the best sequence of flips we have found
                    finalIdxList = currIdxList;
                }
                
                // let's start a new possible sequence of flips
                // we flip the current zero and update the counters
                currIdxList.clear();
                currIdxList.push_back((i));

                numOnes = 1;
                availableFlips = k - 1;
            }
        }
    }
    
    if (numOnes >= maxNumOnes)
    {
        // Let's check if the last sequence is the longest one
        finalIdxList = currIdxList;
    }
    return finalIdxList;
}

- Angelo February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

private static void findLongestSequence(int [] array, int k) {
		// TODO Auto-generated method stub
		int maxLength = 0, tempLength = 0, currentIndex = 0, tempFlips = k;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 1 && tempFlips >= 0) {
				tempLength++;
				if (i == (array.length - 1) && maxLength < tempLength) {
					maxLength = tempLength;
				}
			} else {
				if (tempFlips == 0) {
					currentIndex++;
					
					tempFlips = k;
					if (maxLength < tempLength) {
						maxLength = tempLength;
					}
					tempLength = 0;
					tempFlips = k;
					i = currentIndex;
				} else {
					tempFlips--;
					tempLength++;
				}
			}
		}
		System.out.println("LongestSequenceLength = " + maxLength);
	}
}

- gaganpalsingh9 February 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int longestSequence(int [] array, int k){
    	int maxLength = 0;
    	int start = 0;
    	int runningLength = 0;
    	int tmpK = k;
    	
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == 1){
    			runningLength++;
    		}
    		else if(tmpK > 0 && tmpK < k){
    			tmpK--;
    			runningLength++;
    		}
    		else if(tmpK == k){
    			tmpK--;
    			runningLength++;
    			start = i;
    		}
    		else{ //tmpK == 0
    			tmpK = k;
    			maxLength = Math.max(maxLength, runningLength);
    			runningLength = 0;
    			int tmp = i;
    			i = start;
    			start = tmp;
    		}
    	}
    	
    	return Math.max(maxLength, runningLength);

}

- emiaj.123 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

int tmp = i;
i = start;
start = tmp;

This gonna be a problematic if you have a 0 at array[0]. loop will go on to a infinit loop

- HPY February 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not really, since the variable "i" will start the next iteration at "start+1" (since the "i++" part of the for loop gets executed after every iteration).

I will concede that there is a tiny error when k == 0, which prevents the runningLength variable from being reset to 0. Here is the fixed version:

public static int longestSequence(int [] array, int k){
    	int maxLength = 0;
    	int start = 0;
    	int runningLength = 0;
    	int tmpK = k;
    	
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == 1){
    			runningLength++;
    		}
    		else if(tmpK > 0 && tmpK < k){
    			tmpK--;
    			runningLength++;
    		}
    		else if(tmpK == k && k > 0){
    			tmpK--;
    			runningLength++;
    			start = i;
    		}
    		else{ //tmpK == 0
    			tmpK = k;
    			maxLength = Math.max(maxLength, runningLength);
    			runningLength = 0;
    			int tmp = i;
    			i = start;
    			start = tmp;
    		}
    	}
    	
    	return Math.max(maxLength, runningLength);

}

- emiaj.123 February 15, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int longestSequence(int [] array, int k){
    	int maxLength = 0;
    	int start = 0;
    	int runningLength = 0;
    	int tmpK = k;
    	
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == 1){
    			runningLength++;
    		}
    		else if(tmpK > 0 && tmpK < k){
    			tmpK--;
    			runningLength++;
    		}
    		else if(tmpK == k){
    			tmpK--;
    			runningLength++;
    			start = i;
    		}
    		else{ //tmpK == 0
    			tmpK = k;
    			maxLength = Math.max(maxLength, runningLength);
    			runningLength = 0;
    			int tmp = i;
    			i = start;
    			start = tmp;
    		}
    	}
    	
    	return Math.max(maxLength, runningLength);
    }

- emiaj.123 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int longestSequence(int [] array, int k){
    	int maxLength = 0;
    	int start = 0;
    	int runningLength = 0;
    	int tmpK = k;
    	
    	for(int i = 0; i < array.length; i++){
    		if(array[i] == 1){
    			runningLength++;
    		}
    		else if(tmpK > 0 && tmpK < k){
    			tmpK--;
    			runningLength++;
    		}
    		else if(tmpK == k){
    			tmpK--;
    			runningLength++;
    			start = i;
    		}
    		else{ //tmpK == 0
    			tmpK = k;
    			maxLength = Math.max(maxLength, runningLength);
    			runningLength = 0;
    			int tmp = i;
    			i = start;
    			start = tmp;
    		}
    	}
    	
    	return Math.max(maxLength, runningLength);
    }

- emiaj.123 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// main.cpp
// Amazon
//
// Created by Kiruba Ebenezer Ramanathan on 14/02/16.
// Copyright © 2016 Kiruba Ebenezer Ramanathan. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
// insert code here...
int max_Count= 0,cur_Count = 0;
int n,array[100],flag = 0;
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&array[i]);
}
for (int i = 0; i < n; i++) {

if (array[i] == 1) {
cur_Count++;
}
if ( cur_Count > max_Count ) {
max_Count = cur_Count;
if (max_Count > 1) {
flag = i;
}
}
if (array[i] == 0) {
cur_Count = 0;
}

}
array[flag+1] = 1;
for (int i = 0 ; i < n; i++) {
printf("%d ",array[i]);
}
return 0;
}

- Kiruba Ebenezer February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{

#include <iostream>

int main(int argc, const char * argv[]) {
// insert code here...
int max_Count= 0,cur_Count = 0;
int n,array[100],flag = 0;
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&array[i]);
}
for (int i = 0; i < n; i++) {

if (array[i] == 1) {
cur_Count++;
}
if ( cur_Count > max_Count ) {
max_Count = cur_Count;
if (max_Count > 1) {
flag = i;
}
}
if (array[i] == 0) {
cur_Count = 0;
}

}
array[flag+1] = 1;
for (int i = 0 ; i < n; i++) {
printf("%d ",array[i]);
}
return 0;
}

}

- Kiruba Ebenezer February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>

int main(int argc, const char * argv[]) {
// insert code here...
int max_Count= 0,cur_Count = 0;
int n,array[100],flag = 0;
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&array[i]);
}
for (int i = 0; i < n; i++) {

if (array[i] == 1) {
cur_Count++;
}
if ( cur_Count > max_Count ) {
max_Count = cur_Count;
if (max_Count > 1) {
flag = i;
}
}
if (array[i] == 0) {
cur_Count = 0;
}

}
array[flag+1] = 1;
for (int i = 0 ; i < n; i++) {
printf("%d ",array[i]);
}
return 0;
}

- Kiruba Ebenezer February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//
// main.cpp
// Amazon
//
// Created by Kiruba Ebenezer Ramanathan on 14/02/16.
// Copyright © 2016 Kiruba Ebenezer Ramanathan. All rights reserved.
//

#include <iostream>

int main(int argc, const char * argv[]) {
// insert code here...
int max_Count= 0,cur_Count = 0;
int n,array[100],flag = 0;
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d",&array[i]);
}
for (int i = 0; i < n; i++) {

if (array[i] == 1) {
cur_Count++;
}
if ( cur_Count > max_Count ) {
max_Count = cur_Count;
if (max_Count > 1) {
flag = i;
}
}
if (array[i] == 0) {
cur_Count = 0;
}

}
array[flag+1] = 1;
for (int i = 0 ; i < n; i++) {
printf("%d ",array[i]);
}
return 0;
}

- kirubstkp February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int longest_one_streak(int* array, int size, int k){

    int back = 0;
    int zeros = 0;
    int ones = 0;
    int max = 0;
    for (int front = 0; front < size; front++) {
        if (0 == array[front])
            zeros++;
        else
            ones++;

        if (zeros == k){
            if (zeros + ones > max)
                max = zeros + ones;
        }

        if (zeros > k){
            while (back < front && 1 == array[back]) {
                back++;
                ones --;
            }
            if (back < front && 0 == array[back]) {
                back++;
                zeros--;
            }

        }
    }
    return max;
}

- Alex February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find k times the max longestSequence when one 0 is replaced with 1.
Time complexity is O(kn).

int longestContinuousSequence(boolean[] bits, int k) {
	    	int zeros = 0;
	    	int ones = 0;
	    	for (boolean bit : bits) {
	    		if (!bit)
	    			zeros++;    		
	    		else 
	    			ones++;
	    	}	    
	    	if (ones == 0)
	    		return Math.min(k, bits.length);
	    	if (zeros == 0)
	    		return bits.length;
	    	int max = Integer.MIN_VALUE;
	    	int maxIndex = - 1;	    	
	    	while (zeros > 0 && k > 0) {
	    		int prefix = 0;
	    		int suffix = 0;	    		
	    		for (int index = 0; index < bits.length; index++) {
	    			if (!bits[index]) {	    				
	    				if (suffix == 0) {
	    					suffix = 1;	 	    					
	    				}
	    				else {	
	    					if (max < suffix + prefix) {
	    						max = suffix + prefix;
	    						maxIndex = index - suffix;
	    					}
	    					prefix = suffix - 1;
	    					suffix = 1;
	    				}	    				
	    			}
	    			else {
	    				if (suffix == 0 )
	    					prefix++;
	    				else
	    					suffix++;
	    			}
	    		}	
	    		if (max < suffix + prefix) {
					max = suffix + prefix;
					maxIndex = bits.length - suffix;
	    		}
	    		bits[maxIndex] = true;
	    		k--;
	    		zeros -= 1;
	    	}
	    	return max;
	    	
	    }

- EPavlova February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class ContinousStreak {
	
	public static int cont(int[] a,int ind){
		a[ind]=1;
		int oneCnt=0;
		int maxOneCnt=0;
		for(int i=0;i<a.length;i++){
			if(a[i]==1)
				oneCnt++;
			else
				oneCnt=0;	
			if(oneCnt>maxOneCnt)
				maxOneCnt = oneCnt;
		}
		return maxOneCnt;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a = {1,1,0,0,1,1,1,0,1,1};
		System.out.println(cont(a,7));
	}

}

- Sudheer February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int longestStreak(int[] arr, int k) {
int pp = -1;
int p = -1;
int prevCount = 0;
int maxCount = 0;
int c;
for (c = 0; c < arr.length; c++) {
if (arr[c] == 0) {
if (prevCount == k) {
if (c - pp - 1 > maxCount) {
maxCount = c - pp - 1;
}
pp = p;
prevCount = 0;
}
p = c;
prevCount++;
}
}

if (c - pp - 1 > maxCount) {
if (prevCount == k) {
maxCount = c - pp - 1;
}
}

return maxCount;
}

- Praveen February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class FindLongestBinaryStreakWithk {
	public static void main(String[] args) {
		int arr[] =
		{ 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0 };
		int k = 1;
		System.out.println(longestStreak(arr, k));
	}

	private static int longestStreak(int[] arr, int k) {
		int pp = -1;
		int p = -1;
		int prevCount = 0;
		int maxCount = 0;
		int c;
		for (c = 0; c < arr.length; c++) {
			if (arr[c] == 0) {
				if (prevCount == k) {
					if (c - pp - 1 > maxCount) {
						maxCount = c - pp - 1;
					}
					pp = p;
					prevCount = 0;
				}
				p = c;
				prevCount++;
			}
		}

		if (c - pp - 1 > maxCount) {
			if (prevCount == k) {
				maxCount = c - pp - 1;
			}
		}

		return maxCount;
	}

}

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

private static int longestStreak(int[] arr, int k) {
		int pp = -1;
		int p = -1;
		int prevCount = 0;
		int maxCount = 0;
		int c;
		for (c = 0; c < arr.length; c++) {
			if (arr[c] == 0) {
				if (prevCount == k) {
					if (c - pp - 1 > maxCount) {
						maxCount = c - pp - 1;
					}
					pp = p;
					prevCount = 0;
				}
				p = c;
				prevCount++;
			}
		}

		if (c - pp - 1 > maxCount) {
			if (prevCount == k) {
				maxCount = c - pp - 1;
			}
		}

		return maxCount;

}

- Praveen February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int longestStreak(int[] arr, int k) {
int pp = -1;
int p = -1;
int prevCount = 0;
int maxCount = 0;
int c;
for (c = 0; c < arr.length; c++) {
if (arr[c] == 0) {
if (prevCount == k) {
if (c - pp - 1 > maxCount) {
maxCount = c - pp - 1;
}
pp = p;
prevCount = 0;
}
p = c;
prevCount++;
}
}

if (c - pp - 1 > maxCount) {
if (prevCount == k) {
maxCount = c - pp - 1;
}
}

return maxCount;
}

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

blah

- blah February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int longestStreak(int[] arr, int k) {
int pp = -1;
int p = -1;
int prevCount = 0;
int maxCount = 0;
int c;
for (c = 0; c < arr.length; c++) {
if (arr[c] == 0) {
if (prevCount == k) {
if (c - pp - 1 > maxCount) {
maxCount = c - pp - 1;
}
pp = p;
prevCount = 0;
}
p = c;
prevCount++;
}
}

if (c - pp - 1 > maxCount) {
if (prevCount == k) {
maxCount = c - pp - 1;
}
}

return maxCount;
}

- praveengarg07 February 14, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//Worst case: O(N) time, O(N) space
public int maxOnes(int[] arr,int k)throws NullPointerException
{
	if(arr==null)
	{
		throw new NullPointerException();
	}
	if(arr.length<k)
	{
		return 0;
	}
	int i=0;
	int maxLen=Integer.MIN_VALUE();
	int zeros=0;
	int[] results=new int[arr.length];
	results[0]=1;
	int s=0;
	for(int j=1;j<results.length;j++)
	{
		results[j]=1+results[j-1];
		if(arr[j]==0)
		{
			zeros++;
		}
		while(zeros>k)
		{
			if(arr[i]==0)
			{
				zeros--;
			}
			i++
			s=results[i-1];
		}
		maxLen=Math.max(maxLen,results[j]-s);
		j++;
	}
	return maxLen;
}

- divm01986 February 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int MaxConsecutive(int[] values, int k)
{
    int numOnes = 0;
    int max = int.MinValue;
    int tmpK = k;

    int begin = 0;
    int end = 0;
    while(begin < values.Length)
    {
        Debug.Assert(values[begin] == 0 || values[begin] == 1);

        if (values[begin] == 0)
        {
            //Release the last kth 0 converted to 1
            if (tmpK == 0)
            {
                // Skip the ones
                while (values[end] == 1)
                {
                    end++;
                    numOnes--;
                }

                numOnes--;
                end++;
            }
            else
                tmpK--;
        }

        numOnes++;
        begin++;
        max = Math.Max(numOnes, max);
    }

    return max;
}

- hnatsu February 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int flip1sTo0s(int[] arr, int k){
        int maxScore = 0;
        int temp = 0;
        int tempK = k;
        for(int i=0; i<arr.length;i++){
            if(arr[i] == 1){
                temp++;
            }
            if(arr[i]==0){
                if(tempK>0){
                    tempK--;
                    temp++;
                }else{
                    tempK=k;
                    temp=0;
                    continue;
                }
            }
            maxScore = Math.max(maxScore, temp);
        }
        return maxScore;
    }

- ricardo.mogg February 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{

int []input = new int[]{1,1,0,0,1,1,1,0,1,1};
//int []input = new int[]{1,0,0,1,1,1,0,0,1};
int runningLength=0;
int maxLength =0;
int k=1;
for(int i=0;i<input.length;i++){
if(input[i] == 1){
runningLength++;
}
else {
if(k>0){
runningLength++;
k--;
}
else{
if(maxLength <runningLength){
maxLength = runningLength;

}
runningLength=0;
k=1;
}
}
}
System.out.println("Max "+Math.max(runningLength,maxLength));


}

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

int []input = new int[]{1,1,0,0,1,1,1,0,1,1};
//int []input = new int[]{1,0,0,1,1,1,0,0,1};
int runningLength=0;
int maxLength =0;
int k=1;
for(int i=0;i<input.length;i++){
if(input[i] == 1){
runningLength++;
}
else {
if(k>0){
runningLength++;
k--;
}
else{
if(maxLength <runningLength){
maxLength = runningLength;

}
runningLength=0;
k=1;
}
}
}
System.out.println("Max "+Math.max(runningLength,maxLength));

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

Recursion + Kadane's + Backtracking

public class ContinuesOnesByFlipping {

	public static class Result { int max; public Result(int m) {max = m;}}
	
	public static void main(String[] args) {
		int[] array = new int[] {1,0,1,0,1,1,0,0,0,1,0,1,1,1,0,1};
		int k = 3;
		
		System.out.println("Result = "+ maxOnes(array, k));
	}
	
	public static int maxOnes(int[] array, int k) {
		Result r = new Result(0);
		maxOnes(array, k, 0, r);
		return r.max;
	}
	
	public static void maxOnes(int[] array, int k, int start, Result r) {
		if (k == 0) {
			r.max = Math.max(maxOnesKadane(array), r.max);
		}
		for (int i = start; i < array.length; i++) {
			if (array[i] == 0 && k > 0) {
				array[i] = 1;
				maxOnes(array, k - 1, i + 1, r);
				array[i] = 0;
			}
		}
	}
	
	public static int maxOnesKadane(int[] array) {
		int maxSoFar = 0;
		int maxEndingHere = 0;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 1) {
				maxEndingHere += 1;
			} else if (array[i] == 0) {
				maxEndingHere = 0;
			}
			if (maxEndingHere > maxSoFar) {
				maxSoFar = maxEndingHere;
			}
		}
		return maxSoFar;
	}
}

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

int longest_streak(bool a[],int k)
{
    int size = sizeof(a)/sizeof(bool);
    vector<int> countOfOneZero;
    int count = 0;
    
    for(int i = 0; i< size; )
    {
        while(a[i++]) count++;// this is count of consecutive 1
        countOfOneZero.push_back(count);
        count = 0;

        while(!a[i++]) count++;//this is count of consecutive 0
        countOfOneZero.push_back(count);
        count = 0;
    }
    if(a[i-1]) countOfOneZero.push_back(0);// if the given array ends with 1, then count of //trailing 0 is 0
//at the end of this loop countOfOneZero contains count of consecutive 1 followed by //count of consecutive 0 .... and even indexes give count of 1 and odd index gives count //of zero
   int currentStreak(0), maxStreak(0),availableFlipCount(k);
   for(vector<int>::iterator it = countOfOneZero.begin(); (it+1) != countOfOneZero.end(); it+=2)
   {
       currentStreak = 0;
       availableFlipCount = k;
 
       for(vector<int>::iterator it2 = it; (it2+1) != countOfOneZero.end(); it2+=2)
       {
           currentStreak+=*it2;
           if(availableFlipCount > *(it2+1))
           {
               currentStreak+=*(it2+1);
               availableFlipCount -= *(it2+1);
               if(!availableFlipCount)
               {
                   if((it2+1) != countOfOneZero.end())
                   {
                       currentStreak+=*(it2+2);
                       if(currentStreak > maxStreak) maxStreak = currentStreak;
                       it2 = countOfOneZero.end() -1;
                   }
               }
           }
           else
           {
               currentStreak+=availableFlipCount;
               availableFlipCount = 0;
               if(currentStreak > maxStreak) maxStreak = currentStreak;
                it2 = countOfOneZero.end() -1;

           }
       }    
   }
   
}

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

public int longestStreak(int[] a, int k){
        int maxLength = 0;
        int endPos = 0;
        Stack<Integer> zeroStack = new Stack<>();
        int j = 0;
        for(int i=0, start=0;i<a.length;i++ ){
            if(a[i] ==0 && j==k){
                int currentStreakLength = i-start;

                if(currentStreakLength >maxLength){
                    maxLength = currentStreakLength;
                    endPos = i-1;
                }
                start = zeroStack.pop();
                zeroStack.push(a[i]);
            }else if(a[i] ==0 && j<k){
                zeroStack.push(i);j++;
            }

        }

        if(j<k){
            endPos = a.length-1;
            maxLength = a.length;
        }
        System.out.println("Longest streak (with '"+ k+"' zero's) of length "+maxLength+" found at position: "+endPos);
        return maxLength;
    }

This will find the longest streak with K zeros in O(n) time and o(k) space.

- prijain February 16, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Minor correction -

public int longestStreak(int[] a, int k){
        int maxLength = 0;
        int endPos = 0;
        Stack<Integer> zeroStack = new Stack<>();
        int j = 0;
        for(int i=0, start=0;i<a.length;i++ ){
            if(a[i] ==0 && j==k){
                int currentStreakLength = i-start;

                if(currentStreakLength >maxLength){
                    maxLength = currentStreakLength;
                    endPos = i-1;
                }
                start = zeroStack.pop();
                zeroStack.push(i);
            }else if(a[i] ==0 && j<k){
                zeroStack.push(i);j++;
            }

        }

        if(j<k){
            endPos = a.length-1;
            maxLength = a.length;
        }
        System.out.println("Longest streak (with '"+ k+"' zero's) of length "+maxLength+" found at position: "+endPos);
        return maxLength;
    }

- pJain February 16, 2016 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

int longest_sequence(bool* arr, int size, int k)
{
   int ones = 0, zeros = 0, seq_one = 0, max_seq = 0;
   int k_temp = k;
   int i, flip = 0;
   for (i = 0; i < size; ++i)
   {
      if (arr[i] == 1)
         ones++;
      else
         zeros++;
   }
   if (k >= size) //if k is greater than or equal to  array size
      return size;
   else if (zeros < k) //if no_of_zero is less than k and k is less than array size
      return size;
   else if (ones == 0)
      return k;

  
   //k is less than array size and zeros is greater than k
   for (i = 0; i < size; ++i)
   {
      if (1 == arr[i])
         seq_one++;
      else
      {
         if (k_temp > 0 && k_temp <= k)
         {
            if (k_temp == k)
            {
               flip = i; //starting index of flip
            }
            k_temp--;
            seq_one++;
         }
         else //if (k_temp == 0)
         {
            if (max_seq < seq_one)
               max_seq = seq_one;
            seq_one = 0;
            k_temp = k;
            i = flip;
            flip = 0;
         }
      }
   }
   return (max_seq > seq_one? max_seq : seq_one);

}

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

private int[] arr = {1,1,0,0,1,1,0,1,1,1};
	private int k = 2;
	private int max = 0;
	
	public void find() {
		int cnt = 0,k_=k,i_=-1;
		for (int i = 0; i < arr.length;) {
			if(arr[i] == 1) {
				++cnt;
				++i;
			} else if(arr[i] == 0 && k_-- > 0) {
				if(i_== -1) {
					i_ = i + 1;
				}
				++cnt;
				++i;
			} else {
				max = max > cnt ? max : cnt;
				k_ = k;
				i = i_;
				i_ = -1;
				cnt = 0;
			}
		}
		max = max > cnt ? max : cnt;
	}

- Asif Garhi February 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How much time do you get for such a question? It took me almost 4 hours to come to the most efficient solution I could come up with. I know that is very poor timing. What should I do to improve?

- Asif Garhi February 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Just need to flip K continuous zeros in the array. Assume there are N zero in total. Then there are N-K cases. Here is the detail: cpluspluslearning-petert.blogspot.co.uk/2016/02/find-longest-continuous-streak-of-one.html

Test

#include <cassert>
void Test()
{
    {
        const std::vector<char> arr;
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 100) == 0);
    }
    {
        const std::vector<char> arr = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 0);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 1);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 2);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 3);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 4);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 5);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 6);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 7);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 8) == 8);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 9) == 9);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 10);
    }
    {
        const std::vector<char> arr = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 8) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 9) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 10) == 10);
    }
    {
        const std::vector<char> arr = { 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1 };
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 4);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 14);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 17);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 19);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 19);
    }
    {
        const std::vector<char> arr = { 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1};
        assert(FindLongestContinuousStreakAfterKFlips(arr, 0) == 3);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 1) == 6);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 2) == 8);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 3) == 10);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 4) == 12);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 5) == 14);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 6) == 16);
        assert(FindLongestContinuousStreakAfterKFlips(arr, 7) == 16);
    }
}

- peter tang February 17, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

//C#
static int anupsLongestStreak(int[] arr, int k)
        {
            int streak = 0;

            var seq = new List<sequenceOfOnes>();

            int startIndex = 0;
            int endindex = 0;
            for (int i = 0; i < arr.Length; i++)
            {
                if (arr[i] == 0 && i == 0)
                {

                }
                else if (arr[i] == 0 && i != 0)
                {
                    endindex = i - 1;
                    if (startIndex != endindex)
                    {
                        if (startIndex == 0)
                        {
                            seq.Add(new sequenceOfOnes(startIndex, endindex));
                        }
                        else
                        { seq.Add(new sequenceOfOnes(startIndex + 1, endindex)); }

                        startIndex = endindex + 1;
                    }
                    else { startIndex += 1; }

                }
                else if (i == (arr.Length - 1))
                {
                    endindex = i;
                    seq.Add(new sequenceOfOnes(startIndex + 1, endindex));
                }

            }

            int maxSequence = 0;
            int index = 0;
            for (int i = 0; i < seq.Count-1; i++)
            {
                if (seq[i + 1].startIndex - seq[i].endIndex == k + 1)
                {
                    if (maxSequence < seq[i + 1].size + seq[i].size)
                    {
                        maxSequence = seq[i + 1].size + seq[i].size+k;
                        index = seq[i].endIndex + 1;
                    }
                }

            }

            return maxSequence;
        }

  class sequenceOfOnes
    {
        public int startIndex { get; set; }
        //int startIndex=0;
        public int endIndex{ get; set; }
        public int size  { get; set; }

        public sequenceOfOnes(int _startIndex, int _endIndex)
        {
            startIndex = _startIndex;
            endIndex = _endIndex;
            size = endIndex - startIndex + 1;
        }
    }

- anup@hificoding.com February 18, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#include <iostream>
#include <climits>

int main() {

     int N ,K;
    cin >> N;
    cin >> K;
    int input[N];

    for (int i = 0; i < N; i++) {
        cin >> input[i];
   }
    
    int arrayCount[N];
    int kCount[N];
    
    for (int i = 0; i < N; i++) {
    
        if (input[i] == 1) {
            arrayCount[i] = 1;
			kCount[i] = K;
            for (int j = i-1; j >= 0; j--) {
                if (kCount[j] >= 0) {
                    arrayCount[j] ++;
                }
                else // this item cannot be connected to the current sequence.
                    break;
            }
        } else if (input[i] == 0) {
            arrayCount[i] = 1;
            kCount[i] = K-1;
            for (int j = i -1; j >=0; j--) {
                if (kCount[j] > 0) {
                    arrayCount[j]++;
                }
                kCount[j]--;
            }
            
        }
    
    }
   int max = INT_MIN;
	for (int i =0 ; i < N;i++)
       {
		if (max < arrayCount[i])
        {

			max = arrayCount[i];
        }
   } 
std::cout << max << std::endl;
    
    return 0;
}

- Kenny February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public int getlogestchain(int[]input,int k){
		List<int[]> zerosPairs = new ArrayList<>();
		int[] zerosPostion= new int[input.length];		
		int tempindex=0,flip=k,nodeindex=0;
		int longestLength=0;
		for(int i=0;i<input.length;i++){
			if(input[i]==0){				
			    zerosPostion[tempindex]=i;
			    if(flip==1){
			    	int[] Node=new int[2];
			    	Node[0]=zerosPostion[nodeindex];
			    	Node[1]=zerosPostion[nodeindex+k-1];						
					zerosPairs.add(Node);					
					flip++;
					nodeindex++;
				}
			    flip--;
			    tempindex++;						
			}
		}		
		int zerosindex=0,tempLength;
		int[] currentNode=new int[2],nextNode=new int[2],previousNode=new int[2]; 
		for(Iterator<int[]> it= zerosPairs.iterator();it.hasNext();){		
			if(zerosindex==0){
				currentNode=it.next();
				nextNode = it.next();				
				tempLength=nextNode[1];
				zerosindex++;
			}
			else{
				previousNode=currentNode;
				currentNode=nextNode;
				nextNode=it.next();
				tempLength=nextNode[1]-previousNode[0]-1;
				if(tempLength>longestLength)
					longestLength=tempLength;
				zerosindex++;
				if(zerosindex==zerosPairs.size()-1){
					previousNode=currentNode;
					currentNode=nextNode;
					tempLength=input.length-previousNode[0]-1;
					zerosindex++;
				}
			}
			if(tempLength>longestLength)
				longestLength=tempLength;
		}
		return longestLength;
	}

- pratap February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When we find that we can't go further we should go back to after the first 0 we found, instead of checking from the next item, this can improve the time complexity

private static void findLongestSequence(int[] array, int k) {
		int maxLength = 0;
		int currentLength = 0;
		int currentIndex = 0;
		int availableFlips = k;
		int first0 = -1;
		for (int i = 0; i < array.length; i++) {
			if (array[i] == 1 && availableFlips >= 0) {
				currentLength++;
			} else {
				if (availableFlips == 0) {
					if (first0 != -1) {
						currentIndex = first0;
						first0 = -1;
					} else {
						currentIndex++;
					}
					availableFlips = k;
					currentLength = 0;
					availableFlips = k;
					i = currentIndex;
				} else {
					if (first0 == -1) {
						first0 = i;
					}
					availableFlips--;
					currentLength++;
				}
			}
		}
		if (maxLength < currentLength) {
			maxLength = currentLength;
		}
		System.out.println("Longest Sequence Length = " + maxLength);
	}

	public static void main(String[] args) {
		int[] arr = new int[] { 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1 };
		int k = 4;
		findLongestSequence(arr, k);
	}

- Ivan February 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

O(N) solution in python (also O(N) space). The idea is to count the number of 0s, and save the position and count for each beginning of a 1s block in a queue. We deque a start position when the difference between its count and the current count is k:

from collections import deque

def kFlip(ar, k):
  max_len = 0
  zero_count = 0
  q=deque()
  prev_val=0
  first_one=None
  for pos, val in enumerate(ar):
    if val==1:
      if prev_val==0:
        q.append((pos, zero_count))
        if first_one==None:
          first_one=pos
    else:
      zero_count+=1
      if len(q)>0 and zero_count-q[0][1]>k:
        cur_len = pos-q[0][0]
        if cur_len>max_len:
          max_len=cur_len
        q.popleft()
    prev_val=val

  if len(q)>0:
    zeroes_left=k-(zero_count-q[0][1])
    start_pos=q[0][0]
    while zeroes_left>0 and start_pos>0:
      start_pos-=1
      if ar[start_pos]==0:
        zeroes_left-=1
    cur_len = len(ar)-start_pos
    if cur_len>max_len:
      max_len=cur_len

  return max_len

def main():
  ar=[1,0,0,1,1,1,0,1,1]
  k=2
  print(ar, k)
  print(kFlip(ar,k))

if __name__ == "__main__":
  main()

- gen-x-s February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I have tested the code on a couple of inputs. If anyone found some error pls do let me know.

{
private static void FindMaxLength(int[] arr, int numberOfFlipsAllowed) {
int temp = 0, maxCount = 0, prev = 0;
int k = numberOfFlipsAllowed;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
if (k > 0) {
temp = temp + 1;
k--;
} else if (temp > maxCount) {
maxCount = temp;
temp = prev + 1;
prev = 0;
}
} else if (arr[i] == 1) {
temp++;
prev++;
}
}
System.out.println("Max Count = " + maxCount);
}}

- anky February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static void FindMaxLength(int[] arr, int numberOfFlipsAllowed) {
        int temp = 0, maxCount = 0, prev = 0;
        int k = numberOfFlipsAllowed;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == 0) {
                if (k > 0) {
                    temp = temp + 1;
                    k--;
                } else if (temp > maxCount) {
                    maxCount = temp;
                    temp = prev + 1;
                    prev = 0;
                }
            } else if (arr[i] == 1) {
                temp++;
                prev++;
            }
        }
        System.out.println("Max Count = " + maxCount);

- anky February 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class AmazonQ1 {

	public static void main(String[] args) 
	{
		int array[] = {1,1,0,0,1,1,1,0,0,1,1};
		int totalNumberOfFlips = 2;
		int tempFlips = totalNumberOfFlips;
		int tempNumberOfOnes=0;
		int maxNumberOfOnes = tempNumberOfOnes;
		for (int index = 0; index < array.length; index++) 
		{
			if (array[index] == 0)
			{
				if (tempFlips > 0)
				{
					tempFlips--;
					maxNumberOfOnes++;
					tempNumberOfOnes++;
				}
				else
				{
					tempNumberOfOnes=0;	
					tempFlips = totalNumberOfFlips;
				}
			}
			else
			{
				tempNumberOfOnes++;
				if (maxNumberOfOnes < tempNumberOfOnes)
				{
					maxNumberOfOnes = tempNumberOfOnes;	
				}
			}
		}
		System.out.println("Counter is : " + maxNumberOfOnes);
	}
}

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

Strange!! Nobody is talking about the algorithm.

- Sujon February 24, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

arr = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
k = 3
tmpK = 0
total_so_far = 0
max_so_far = 0

tmpK = k

for c in arr:
	if c == 0:
		if tmpK >= 1:
			tmpK -= 1
			total_so_far += 1
		else:
			total_so_far = 0
			tmpK = k
	elif c == 1:
		total_so_far += 1
	if max_so_far < total_so_far:
		max_so_far = total_so_far

print max_so_far

- Saikat February 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

arr = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
k = 3
tmpK = 0
total_so_far = 0
max_so_far = 0

tmpK = k

for c in arr:
if c == 0:
if tmpK >= 1:
tmpK -= 1
total_so_far += 1
else:
total_so_far = 0
tmpK = k
elif c == 1:
total_so_far += 1
if max_so_far < total_so_far:
max_so_far = total_so_far

print max_so_far

- Saikat February 25, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Java Code:

public class PP {

	public Dim findLongestStreak (int[] nums, int k) {
		Dim d = new Dim();
		int i = 0;
		int n = k;
		int start = 0;
		int count = 0;
		while(i < nums.length){
			
			if(nums[i] == 0){
				if(n > 0){
					n--;
					count++;
				} else {
					checkAndSetLength(d, start, count);
					if(i == nums.length-1){
						break;
					}
					start = start+1;
					i = start;
					count = 0;
					n = k;
					continue;
				}
			}else{
				if(i == nums.length-1){
					count++;
					checkAndSetLength(d, start, count);
					break;
				}
				count++;
			}
			i++;
		}
		return d;
	}
	private void checkAndSetLength(Dim d, int start, int count){
		if(d.maxLength < count){
			d.index = start;
			d.maxLength = count;
		}
	}
}

class Dim{
	public int index = 0;
	public int maxLength = 0;
	public boolean equals(Object d) {
		Dim d1 = (Dim) d;
		return d1.maxLength == maxLength && d1.index == index;
	}
}

Unittest:

@Test
	public void testFindLongestStreak() {
		Dim d = new Dim();
		d.maxLength = 7;
		d.index = 4;
		assertEquals(d, new PP().findLongestStreak(new int[]{1,1,0,0,1,1,1,1,0,1,1}, 1));
		d.maxLength = 8;
		d.index = 0;
		assertEquals(d, new PP().findLongestStreak(new int[]{1,1,0,0,1,1,1,1,0,1,1}, 2));
	}

- ss March 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How about this

#include <stdio.h>

int arr[] = { 1, 1, 0, 0, 1, 1, 1, 0, 1, 1 };
int k = 1;

int fun(int arr[], int i, int size, int k){
	if (size == i) return 0;
	if (k < 0) return -1;	
	if (arr[i] == 1)
		return (1 + fun(arr, i + 1, size, k));
	if (arr[i] == 0)
		return (1 + fun(arr, i + 1, size, k - 1));
}
int main(){
	int size = sizeof(arr) / sizeof(arr[0]);
	int sum = 0;
	for (int i = 0; i < size; i++)
	{
		int count = fun(arr, i, size, k);
		if(sum < count)	sum = count;
	}
	printf("%d", sum);
	return 0;
}

- praveen pandit March 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

void longestSequence(int[] arr) {
		int sum = 0;
		int position = 0;

		int flip = -1;
		int start = 0;
		int end = arr.length;

		int i = 1;
		int size = arr.length;

		do {
			if (arr[i - 1] != 0) {
				i++;
				continue;
			}

			if (flip == -1) {
				flip = i;
			} else {
				end = i;
				int tmp = end - start;
				if (tmp > sum) {
					sum = tmp;
					position = flip;
				}

				start = flip;
				flip = end;
				end = size;
			}

			i++;
		} while (i <= size);

		int cnt = end - start;
		if (sum < cnt) {
			sum = cnt;
			position = flip;
		}

		System.out.println("Total sum is " + sum + " by flipping position " + (position - 1));
	}

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

Came up with this O(N) solution that uses O(N) memory, but pretty simple.

a = [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1]
k = 2

zeroes = filter(lambda x: a[x] == 0, range(len(a)))
left = 0
mx = 0
cur = 0
for i in range(len(a)):
    if a[i] == 1:
        cur += 1
    else:
        if k > 0:
            k -= 1
            cur += 1
            if k == 0:
                left += 1
        else:
            cur = i - zeroes[left - 1]
            left += 1
    mx = max(mx, cur)
print mx

- art.averin May 04, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int calculate_subarr( int *arr, int n, int k) {
deque<int> loc;
int i=0, one_count=0;
int max_count = 0;
while(i<n && loc.size() < k) {
if(arr[i] == 0)
loc.push_back(i);
}

for(int i=0; i<n; i++) {
if(arr[i] == 1)
one_count++;
}

while(loc.size() == k) {
int min = loc[0];
for(int i=min-1; i>0;i--) {
if(arr[i] == 1)
min--;
else
break;
}

int max = loc.back();
for(int i=max+1; i<n;i++) {
if(arr[i] == 1)
max++;
else
break;
}

int curr_max_count = max - min + 1;
if( curr_max_count > one_count )
curr_max_count = one_count;
if( curr_max_count > max_count )
max_count = curr_max_count;
loc.pop_front();
int maxc = max + 1;
while(maxc < n) {
if(arr[maxc] == 0) {
loc.push_back(maxc);
break;
}
maxc++;
}
}
return max_count;
}

- kbkunalb May 12, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private static int Flip(int[] numbers, int k){

        int length = numbers.length;
        int currentMax = 0;
        int startIndex = 0;
        int index = 0;

        while(index < length){
            index = startIndex;
            int zeros = k;
            int count = 0;

            while(zeros >= 0 && index<length){
                if(numbers[index++] == 0 ){
                    if(zeros == 0) break;
                    if(zeros == k) startIndex = index;
                    zeros--;
                }
                count++;
            }
            currentMax = Math.max(count, currentMax);
        }
        return currentMax;
    }

- incarose November 11, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findLongestPatternAfterFlip(Integer[] arr) {
		int startIndex=0;
		int currIndex=0;
		int changedIndex=-1;
		int cnt=0;
		int tmpCnt=0;
		while(currIndex!=arr.length&&startIndex!=arr.length) {
			if(arr[currIndex]==1) {
				tmpCnt++;
				currIndex++;
			}else {
				if(changedIndex>0) {
					cnt = Math.max(tmpCnt, cnt);
					tmpCnt=0;
					currIndex = ++startIndex;
					changedIndex=-1;
				}else {
					changedIndex=currIndex;
					tmpCnt++;
					currIndex++;
				}
			}
		}
		return cnt;
	}

- engeloded November 28, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

I am not sure but this piece of code seems to work

arr = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1]
k = 3
tmpK = 0
total_so_far = 0
max_so_far = 0

tmpK = k

for c in arr:
	if c == 0:
		if tmpK >= 1:
			tmpK -= 1
			total_so_far += 1
		else:
			total_so_far = 0
			tmpK = k
	elif c == 1:
		total_so_far += 1
	if max_so_far < total_so_far:
		max_so_far = total_so_far

print max_so_far

- Saikat February 25, 2016 | 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