Amazon Interview Question


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

- ninhnnsoc October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

ninhnnsoc. Nice solution

- mikewhity October 22, 2014 | Flag
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.

- masterjaso October 22, 2014 | Flag
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.

- gudujarlson October 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

+1.

Very nice solution!

- Vicks October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

nice. +1

- MIG October 28, 2014 | Flag
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)

- MIG October 28, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

thanks for your solution

- suwei19870312 November 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 votes

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

- Ahmed October 09, 2015 | Flag
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.

- Sachin October 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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] == 0)
        count = 1;

- Puneet3821 June 12, 2017 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Deepak Chaudhary December 18, 2018 | Flag
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)

- shashank shandilya October 24, 2014 | Flag Reply
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

- rohit October 24, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- shashank shandilya October 24, 2014 | Flag
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) {
found.add(i);
}
}
return found;
}
}

- Anonymous October 22, 2014 | Flag Reply
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;
	}

}

- shukad333 October 22, 2014 | Flag Reply
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) {
					flipIndices.addFirst(i);
				}
				else  {
					int length = i - begin;
					if (length > maxLength) {
						maxLength = length;
						maxBegin = begin;
						maxEnd = i;
					}
					begin = flipIndices.removeLast() + 1;
					flipIndices.addFirst(i);
				}
			}
		}
		
		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) {
				maxFlipIndices.add(i);
			}
		}
		return maxFlipIndices;
	}

- gudujarlson October 22, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Amber-Xin October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- gudujarlson October 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def zeroflipper(s, maxflip):
	ones = [0] * 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[0]
			ones.append(0)
			del pos[0]
			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()

- . October 24, 2014 | Flag Reply
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))
}

- . October 25, 2014 | Flag Reply
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;
}

- - October 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class FlipZero {

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

		Queue<Integer> queue = new LinkedList<Integer>();
		List<Integer> maxList = new LinkedList();

		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;
					queue.add(i);
				} else {
					if (maxSum < sum) {
						maxSum = sum;
						maxList = new LinkedList(queue);
					}
					int last = queue.remove();
					queue.add(i);
					sum = i-last;
				}
			}
		}
		if (maxSum < sum) {
			maxSum = sum;
			maxList = new LinkedList(queue);
		}

		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);
	}
}

- Vladimir October 27, 2014 | Flag Reply
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[0]), m));
    return 0;
}

- trent.tong May 14, 2015 | Flag Reply
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

- shaw.nikhil July 29, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Does it work on 00110011101

- omi June 24, 2017 | Flag Reply
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++;

}

- khannaanurag1 September 11, 2017 | Flag Reply
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
Could you please explain.

- surya.das May 16, 2019 | 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