This is an Amazon interview question for software developer engineer from careercup. Here is the original thread,
"
Given an array of 0s and 1s, and k, Find the longest continuous streak of 1s after flipping k 0s to 1s.
E.x array is {1,1,0,0,1,1,1,0,1,1}
k = 1 (which means we can flip ‘k’ one 0 to 1)
Answer: 6 (if we flip 0 at index 7, we get the longest continuous streak of 1s having length 6)
2. Algorithm
Assume that there is N zeros in the given array and allow K flips, then there is C(N, K) which denotes the ways of to flip zeros - select K from N options. This is a factorial computation complexity which is something we should definitely avoid.
As the task to to find the longest streak of ones after K flips, therefore this is a optimization problem. Let's see if we can narrow down the cases to speed up the search process. Here is my case: only need to flip zeros continuously to maximize the lengths of ones. Here is my argument.
Given an array: 11100001110011110101, where N = 8
Given flips: K = 4
If flips the zeros not in continuous way: 11100001110011110101
The 4 zeros in read are to be flipped. And between there are 2 zeros existing in blue. The longest streak will be the max(5, 9) in this case. This is never as good as flipping the zeros in the continuous way, (11100001110011110101 or 11100001110011110101), because we always can flip the blue zeros and get longer result together with it as 10 and 11, which both are longer than 5 and 9.
I wish I could use better formulated math to explain it in a more general description and arguing. In above simple argument there is only need to check the cases that zeros are flipped continuously. Therefore this will reduced the search space from C(N, K) to (N - K) -- from factorial to linear.
3. C++ Implementation
// ********************************************************************************
// Implementation
// ********************************************************************************
#include <vector>
#include <queue>
size_t FindLongestContinuousStreakAfterKFlips(const std::vector<char>& arr, size_t kFlips)
{
if (arr.empty()) {
return 0;
}
size_t result = 0;
std::queue<size_t> idxOfZero;
size_t startIndex = 0;
size_t loc = 0;
bool allOnes = true;
for (auto it = arr.begin(); it != arr.end(); ++it, ++loc) {
if (*it == 0) {
allOnes = false;
if (idxOfZero.size() < kFlips) {
idxOfZero.push(loc);
}
else {
size_t tempResult = loc - startIndex;
if (tempResult > result) {
result = tempResult;
}
if (idxOfZero.empty()) {
startIndex = loc + 1;
}
else {
startIndex = idxOfZero.front() + 1;
idxOfZero.pop();
idxOfZero.push(loc);
}
}
}
}
if (allOnes ) {
return arr.size();
}
if (!idxOfZero.empty() && idxOfZero.size() == kFlips) {
// hitting the end of arr
size_t tempResult = arr.size() - startIndex;
if (tempResult > result) {
result = tempResult;
}
}
if (result == 0 && !idxOfZero.empty()) {
return arr.size();
}
return result;
}
// ********************************************************************************
// 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);
}
}
No comments:
Post a Comment