Amazon Interview Question SDE-2s
Country: United States
Interview Type: In-Person
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);
}
}
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);
}
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;
}
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);
}
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
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);
}
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);
}
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);
}
//
// 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;
}
{
#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;
}
}
#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;
}
//
// 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;
}
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;
}
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;
}
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));
}
}
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;
}
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;
}
}
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;
}
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;
}
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;
}
//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;
}
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;
}
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;
}
{
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));
}
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));
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;
}
}
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;
}
}
}
}
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.
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;
}
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);
}
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;
}
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);
}
}
//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;
}
}
#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;
}
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;
}
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);
}
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()
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);
}}
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);
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);
}
}
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
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
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));
}
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;
}
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));
}
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
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;
}
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;
}
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;
}
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
- emiaj.123 February 14, 2016public 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); }