## Amazon Interview Question

• 10

Country: United States
Interview Type: Phone Interview

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

I would use SLIDING WINDOW for this problem. (Just realized that I have used it at least 3 times at careercup!)

Lets use a window covering from index wL to index wR. Let the number of zeros inside the window be nZero. We try to maintain the window with at most m zeros inside.

The main steps are:
- While nZero is no more than m: expand the window to the right (wR++) and update the count nZero;
- While nZero exceeds m, shrink the window from left (wL++), update nZero;
- Update the widest window along the way. The positions of must-flip zeros are inside the best window.

This solution assumes we can use m or less number of flips.
Time complexity = O(n), space = O(1).

Pseudo-code:

``````wL = 0; wR = 0;
nZero = 0;
bestWindowWidth = -1;

while(wR < A.length()){
//expand to the right, update '0' count:
if (nZero <= m){
wR++;
if (A[wR] == '0') nZero++;
};

//shrink from left, update '0' count:
if (nZero > m){
if (A[wL] == '0') nZero--;
wL++;
};

//update best window:
if (wR - wL > bestWindowWidth){
bestWindowWidth = wR - wL;
bestWR = wR;
bestWL = wL;
};
};``````

Output:

``// Must-flip zeros are inside the best window``

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

ninhnnsoc. Nice solution

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

I really like this solutions, and the explanation of of the asymptotic analysis. Excellent work, and thanks for introducing me to a new concept that I had not previously considered.

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

This is basically the same as my solution, except that you rescan for the first zero when shrinking the left side whereas I store that information in a deque. I like the simplicity of your solution.

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

+1.

Very nice solution!

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

nice. +1

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

if (wR - wL > bestWindowWidth) could be evaluated to true when nZero == m +1. i.e. 11101101

so this if should be replaced with if (nZeo< = m && wR - wL > bestWindowWidth)

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

Comment hidden because of low score. Click to expand.
0

This won't work for a simple case like [0, 1, 1, 1] and m = 0

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

if (wR - wL > bestWindowWidth){
bestWindowWidth = wR - wL;
bestWR = wR;
bestWL = wL;
};
instead of bestWR=WR, WR-1 should be assingned.

Comment hidden because of low score. Click to expand.
0

Nice solution! But there is one bug in this program. When first element is '0' in that case update the count to 1;

``````if(A == 0)
count = 1;``````

Comment hidden because of low score. Click to expand.
0

Very nice solution but this gives O(n^2) in worst case. Consider m = 1 and array = 1 1 1 1 1 1 1 1 0 0

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

Ruby Solution to the above problem

``````def flipZero( arr = [], m )
left  = 0
right = 0
max   = -1
zeroc = 0
lefti = 0
righti = 0
start_zero_loc = 0
while right < arr.length
#puts "right #{right} :: zeroc #{zeroc}  :: left #{left} :: max #{max} :: start_zero_loc #{start_zero_loc}"
if zeroc <= m
right += 1
if arr[ right ] == 0 then
zeroc += 1
if zeroc == 1 then
start_zero_loc = right
end
end
else
if arr[ right ] == 0 then
zeroc -= 1
if zeroc == 1 then
start_zero_loc = right
end
left   = start_zero_loc
end
left += 1
end

if ( right - left ) > max
max    = ( right - left )
lefti  = left
righti = right
end
end
p [max, lefti, righti]
end

flipZero([1, 1, 0, 1, 1, 0, 0, 1, 1, 1], 2)``````

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

Nice Work, seems similar to sliding window, but any ways it works

Comment hidden because of low score. Click to expand.
0

yeah, Nicely explained but faced few difficulties while implementing it.

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

public class FindPos {
public static List<Integer> findPositions(int[] arr, int m) {
if (arr == null || arr.length == 0 || m == 0) {
return Collections.emptyList();
}
int l = 0;
int r = findInitInterval(arr, m);

int bestL = 0;
int bestR = r;
while (r < arr.length) {
l = findNextZero(arr, l) + 1;
r = findNextZero(arr, r + 1);
if ((r - l) > (bestR - bestL)) {
bestL = l;
bestR = r;
}
}

return findZeros(arr, bestL, bestR);
}

private static int findInitInterval(int[] arr, int m) {
int remained = m;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 0) {
remained--;
if (remained < 0) {
return i;
}
}
}

return arr.length;
}

private static int findNextZero(int[] arr, int l) {
for (int i = l; i < arr.length; i++) {
if (arr[i] == 0) {
return i;
}
}
return arr.length;
}

private static List<Integer> findZeros(int[] arr, int l, int r) {
List<Integer> found = new ArrayList<Integer>();
for (int i = l; i < r; i++) {
if (arr[i] == 0) {
}
}
return found;
}
}

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

``````public class FlipZero {

public static void main(String[] args) {

//System.out.println(countMax("10011101111"));
System.out.println(getFlipIndex("10111101101011101"));
}

static int getFlipIndex(String inp) {

int len = inp.length();
int max = 0;
int index = 0;
for(int i=0;i<len;i++) {

if(inp.charAt(i) == '0'){

int localMax = countMax(inp.substring(0, i)+"1"+inp.substring(i,len));
if(localMax > max) {

max = localMax;
index = i;
}
}
}

return index+1;
}
static int countMax(String inp) {

if(inp==null || inp.isEmpty())
return -1;

int len =  inp.length();
int count = 0;
for(int i=0;i<len;i++) {

if(inp.charAt(i)=='1') {

int localCount = 1;
for(int j=i+1;j<len;j++) {

if(inp.charAt(j)=='1')
localCount++;
else
break;

}

if(localCount>count)
count = localCount;
}
}

return count;
}

}``````

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

This is similar to the max subarray problem and can be solved in O(n) time using something similar to Kadane's algorithm. The main idea is maintaining a sliding window that contains a continuous sequence of 1's as we iterate over the array. We extend the right side of the window if we encounter a 1 or the number of flips is less than m; otherwise we shrink the left side to one position to the right of the first zero. The last part forces us to maintain a list of the positions of the zeros. Thus O(m) space. Here a solution in Java.

``````int[] maximumContinuousOnes(int a[], int m) {
ArrayList<Integer> maxFlipIndices = innerMaximumContinuousOnes(a, m);
int result[] = new int[maxFlipIndices.size()];
for (int i = 0; i < maxFlipIndices.size(); ++i) {
result[i] = maxFlipIndices.get(i);
}
return result;
}

ArrayList<Integer> innerMaximumContinuousOnes(int a[], int m) {
int maxLength = 0;
int maxBegin = 0;
int maxEnd = 0;
int begin = 0;
ArrayDeque<Integer> flipIndices = new ArrayDeque<Integer>();

for (int i = 0; i < a.length; ++i) {
if (a[i] == 0) {
if (flipIndices.size() < m) {
}
else  {
int length = i - begin;
if (length > maxLength) {
maxLength = length;
maxBegin = begin;
maxEnd = i;
}
begin = flipIndices.removeLast() + 1;
}
}
}

int length = a.length - begin;
if (length > maxLength) {
maxBegin = begin;
maxEnd = a.length;
}

ArrayList<Integer> maxFlipIndices = new ArrayList<Integer>();
for (int i = maxBegin; i < maxEnd; ++i) {
if (a[i] == 0) {
}
}
return maxFlipIndices;
}``````

Comment hidden because of low score. Click to expand.
0

I appreciate your code. It is better than first code since the array is not double scanned. You are using the type 'arraydeque' for a dynamic queue. For me I would use a circle queue (static int array)

Comment hidden because of low score. Click to expand.
0

Yes I avoid the extra scan, but the net result is still O(n) time. If the input has a high 1 to 0 ratio, my code will be faster, but perhaps not otherwise because of overhead of the deque operations. The worse case for my solution is an input of all zeros which will use O(n) space.

Unless I misunderstand, ArrayDeque is a circular queue like you describe and all the operations I've used are O(1).

Comment hidden because of low score. Click to expand.
0

Oops, never mind about the worse case O(n) space. That was a early morning brain fart.

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

``````def zeroflipper(s, maxflip):
ones =  * maxflip
pos = [-1] * maxflip
maxpos = [-1] * maxflip
flip,length,maxlen = 0,0,0

for i in range(len(s)):
if s[i] == '1':
ones[maxflip-1] += 1
length +=1
else:
if flip < maxflip:
flip += 1
length = sum(ones) + flip
del ones
ones.append(0)
del pos
pos.append(i)

if length > maxlen:
maxlen = length
maxpos = pos[:]

return maxlen, maxpos

def main():
s = '1101100111'
maxflip = 2

print(zeroflipper(s,maxflip))

if __name__ == '__main__':
main()``````

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

``````package main
import "fmt"

func sum(s []int) (sum int) {
sum = 0
for _,v := range s {
sum += v
}
return
}

func shift(s []int) {
for i:=0; i<len(s)-1; i++ {
s[i] = s[i+1]
}
s[len(s)-1] = 0
}

func zeroflipper(s []int, maxflip int) ( int, []int ) {
ones := make([]int, maxflip)
pos := make([]int, maxflip)
maxpos := make([]int, maxflip)
flip, length, maxlen := 0,0,0

for i,v := range s {
if v == 1 {
ones[maxflip -1 ]++
length++
} else {
if flip < maxflip {
flip++
}
length = sum(ones) + flip
shift(ones)
shift(pos)
pos[len(pos)-1] = i
}

if length > maxlen {
maxlen = length
for i,v := range pos {
maxpos[i] = v
}
}
}
return maxlen, maxpos
}

func main(){
s := []int{1,1,0,1,1,0,0,1,1,1}
maxflip := 2

fmt.Println(zeroflipper(s,maxflip))
}``````

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

I know it is not as good as the sliding window approach and works at O(n^2). Yet another way of solution.

``````int main() {
vector<int> vec = {1, 1, 0, 1, 0, 1, 0, 0, 1, 1};
int m = 2;
int max_now = 0, max_all=0;
vector<int> changes, changes_all;
for(int i = 0; i < vec.size(); ++i) {
int tmp_m = m;
max_now = 0;
changes.clear();
for(int j=i; j < vec.size(); ++j) {
if(vec[j] == 0) {
tmp_m --;
if(tmp_m < 0) {
if(max_now > max_all) {
max_all = max_now;
swap(changes, changes_all);
}
break;
} else {
changes.push_back(j);
}
}
max_now++;
}
if(max_now > max_all) {
max_all = max_now;
swap(changes, changes_all);
}
}

for(auto i:changes_all) {
cout << i << " ";
}
cout << endl << max_all << endl;

return 0;
}``````

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

``````class FlipZero {

public static void findFlipMax(int[] array, int maxFlip) {

int sum = 0;
int maxSum = 0;

for (int i = 0; i < array.length; ++i) {
if (array[i] == 1) {
++sum;
}
if (array[i] == 0) {
if (maxFlip > 0) {
--maxFlip;
++sum;
} else {
if (maxSum < sum) {
maxSum = sum;
}
int last = queue.remove();
sum = i-last;
}
}
}
if (maxSum < sum) {
maxSum = sum;
}

System.out.println("maxSum = " + maxSum);
if (maxList != null)
System.out.println("flip indexes = " + Arrays.toString(maxList.toArray()));

}

public static void main(String [] args) {
findFlipMax(new int[]{1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1}, 2);
}
}``````

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

``````#include <stdio.h>
#include <limits.h>
///
/// this problem can be solved with a sliding window.
///
/// essentially. we want to find the maximum we can do for
/// every possible starting index.
///
/// as the algorithm illustrates, everytime we recompute maxlen
/// that can be achieved with a starting index, we incur O(1) cost.
/// as we simply need to slide out the last starting index, and if
/// we free a fill. we can use that fill to go further.
///
/// NOTE. e - end index here will always advance, as when we free
/// up fills on the left side (start index). there is no way we could
/// do worse. i.e. go backward.
//
/// when we run out of fill, i.e. can not advance further.
/// we need to move the start to try to free up some fills.
///
/// NOTE. we can not move the end further as we do not have fills.
/// and moving end backwards will simply gives us a subpoptimal
/// solution.
///
int maxbit_length(char* a, int size, int m) {
int maxlen = INT_MIN;
char fill[size];
for(int i=0;i<size;++i)
fill[i] = 0;

int s,e=0;
for(s=0;s<size;++s) {
while(1) {
/// try to fill it.
if (!a[e]) {
if (m>0 && e<size) {
fill[e] = a[e] = 1;
++e;
--m;
} else {
// run out of fills. update the max len;
maxlen = maxlen < (e-s) ? (e-s) : maxlen;
break;
}
} else {
++e;
}
}
/// advance s. and see whether we can reclaim a fill.
if (fill[s]) {
fill[s] = a[s] = 0;
++m;
}
}
return maxlen;
}

int main() {
char a[] = {1,1,0,1,1,0,0,1,1,1};
int m = 2;
printf("%d\n", maxbit_length(a, sizeof(a)/sizeof(a), m));
return 0;
}``````

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

``````if (nZero <= m){
wR++;
if (A[wR] == '0') nZero++;
};``````

should we not check first the condition if (A[wR] == '0') nZero++ and then increment wR ..
A[0,1,1,1]
m=0
output according to your code is : wl=0,wr=3
whereas it should be wl=1 , wr = 3 .
Correct me if i am missing something .. Thanks

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

Does it work on 00110011101

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

In the very first solution , in case of 0 flips and for array 0,1,1,1 , the program gives wrong output but if we make a very small change , this problem can be sorted

if(nzero<=flips)
{
if(a[wr]==0)
nzero++;

wr++;

}

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

I have a question - Suppose number of flips allowed is 2, can the flips be separate rather than contiguous? For example, input = {1,1,0,1,1,0,1,1,1,0,0,1} and number of flips allowed is 2, so will the solution be 1,1,1,1,1,1,1,1,1 or 1,1,1,1,1,1

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.

### 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.