In a given string of 0s and 1s , if you flip n number of 0s to 1...

>In a given string of 0s and 1s , if you flip n number of 0s to 1, what would be the longest contiguous string of 1s possible. e.g {0 0 1 0 1 1 0 1 0 0} when n = 2 the answer would be {4,7} and attained by flipping bit number 4 and 7 from 0 to 1
>example input
10 2
0 0 1 0 1 1 0 1 0 0
>example output
4 7

The above programming test was given to me by my younger brother who's in univ studying CSE, and graduating next year. I could not solve this problem in the allotted time (30 minutes). This has made my impostor syndrome stronger than ever. Its not even like I dont know how to program. I have been programming since i was 14 years old. I have programmed in batch script, shell script, Basic, C, Visual Basic, C++, Java, Python, x86 assembly, AVR assembly, 8085 assembly, ARM assembly. I have worked with various platforms, x86_64 machines, android, ARM microcontrollers, AVR microcontrollers, etc etc.
I am not even that dumb, when I was 14, I without any formal knowledge discovered a way to convert binary numbers to decimal, and implemented it in VB6 to make 'encryption tool'. When I was 17 I was making full adders in minecraft without any formal training.
I even did decently well in college.
But I HAVE NO IDEA WHY I PANICKED DURING THE TEST, EVEN THOUGH I KNEW EXACTLY HOW TO SOLVE THIS PROBLEM IN MY HEAD BUT WHY WHY

Attached: 0088 - nokSoT1.jpg (614x588, 122K)

isn't this just like a greedy solution? on each iteration, pick the position (or positions) that have the longest contiguous string, and follow from them, until you can't add anymore ones.

Yes its exactly like that
It took me ~40 minutes to implement it though, that's the problem.
Working with high level software really rots your brain

Attached: mio_cry.gif (600x450, 140K)

just go trough each iteration and check the longest string in each one, if you find a longer one in the next iteration update it. doesn't really sound difficult

>rots your brain
I hear a lot of people at woke say this, that they are losing old skills.. but the truth is they are focusing on different skills. There's a ton you know that your little brother doesn't, and tech is so big today that two people can specialize in different parts of it and not totally understand what the other is doing.

Your brother is in college, which is the peak time of trivia studying, problems like these. You are solving real problems presumably, and if you did have to solve this specifically no one would give a damn if you could finish in 30 minutes or a couple hours.

Attached: pg9gv2KYv41r7gjb3_540.png (500x373, 213K)

work* :(

Yes my friend, I was able to finish writing the solution, but not in the allocated time, I exceeded the time by 10 minutes by my incompetence.
From the moment I finished reading the problem statement, I knew exactly how I was going to solve this problem but it took me unexpectedly long

I guess that's true but I just want to remain a superset of whatever I leaned in the past past and am learning now.
I wish I had better memory

i mean, you would need to have some experience with implementing search algos to get a solution working fast. and 40 minutes legit isn't bad, imo, if you didn't know what to do.

Performance anxiety. Whenever I have to skate in front of someone I like/respect/IwantToSeeThemLikeMe, I just automatically fuck up. I bet it's just because you felt like this was your chance to prove yourself and you just overloaded.

This is badly phrased. You should ask for an algorithm explicitly. That being said; the solution is pretty simple. You take the index of every 0 bit in your bitstring, and sort these indices by the number of 1s adjacent in descending order. Then you flip the bits at the first n sorted indices. If you end up with more than one sequence of 1s then you put the indices of all but the shorted sequences back into your sorted list and start again.

t. webshite developer

I don't think so.

23 2;
101111110100011101110111


Clearly the correct solution is to make the second group contiguous, with eleven 1's. Greedy selection goes for the first group, ending up with ten 1's.

what is the purpose of this exercise? what would it ever be useful for?

>what is the purpose of this exercise?
testing your problem solving skills

>what would it ever be useful for?
this exercise is very simple and if you can't even do this you're not prepared for more complex tasks that will come the the job.

Security will walk you out now.

And I think a simple solution is to scan through each position, and keeping the count of the longest string starting from that position containing at most n 0's, then pick the maximum.

What if n is greater than the number of zeros in the string?

is it possible faster than n^2?

Find the shortest string of repeated 0s that can be changed to 1 and completely "bridge the gap", change them all to 1.

Subtract the number of changes you made. Repeat until out of changes.

Then determine the longest run of 1s

Shit, misread what your supposed to output. Instead just keep track of each position you flip as you flip them instead of determining the longest run

module Contiguous where

import Data.List (maximumBy)
import Data.Ord (comparing)

longest :: Int -> String -> Int
longest _ [] = 0
longest n ('1':xs) = 1 + longest n xs
longest 0 ('0':xs) = 0
longest n ('0':xs) = 1 + longest (n - 1) xs
longest n xs = error $ "error: " ++ show n ++ " " ++ show xs

suffixes :: String -> [(String, Int)]
suffixes xs = takeWhile (not . null . fst) $ (\n -> (drop n xs, n)) [0..]

pickLongest :: Int -> String -> (String, Int)
pickLongest n = maximumBy (comparing (longest n . fst)) . suffixes

findZeroPositions :: Int -> (String, Int) -> [Int]
findZeroPositions n (xs, n0) = fmap ((+ n0) . snd) . take n . filter ((== '0') . fst) $ zip xs [0..]

flippedZeros :: Int -> String -> [Int]
flippedZeros n = findZeroPositions n . pickLongest n


> flippedZeros 2 "101111110100011101110111"
[16,20]

function f(bs, n) {
// Consider all ranges bs[left:right]
let left = 0;
let right = 0;
let num_zeros = 0; // numbers of zeros in current range
let max = 0; // longest range found so far
let max_left = 0; // left value for longest range found so far

const len = bs.length;

while (right !== len) {
// Try increasing right
if (bs[right] === '1') {
right += 1;
} else if (num_zeros < n) {
right += 1;
num_zeros += 1;
} else {
// Increase left
if (bs[left] === '0') {
num_zeros -= 1;
}
left += 1;
}

if (left > right) {
right = left;
num_zeros = 0;
}

if (right - left > max) {
max = right - left;
max_left = left;
}
}

let indices = []; // indices of zeros to flip
for (let i = max_left; i !== len && indices.len !== n; i += 1) {
if (bs[i] === '0') {
indices.push(i);
}
}
return indices;
}

(Using K for the number of allowed flips, K=2 in OP example, to avoid confusion with N as the length of the input string.)

You can store the position of the last K zeroes seen in a ring buffer, and then iterate over the input string with a state machine. Each zero seen generates a possible solution that you check against the best maximum so far.

This solution is O(N) time, but O(K) space. I have a feeling a more space-efficient solution would be possible.

Ooh, nice. I knew something like this had to be possible, but I couldn't quite see it.

Damn, should have been indices.length, not indices.len in the last for loop.