Amazon Interview Question
Country: United States
Interview Type: Phone Interview
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.
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.
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)
if (wR - wL > bestWindowWidth){
bestWindowWidth = wR - wL;
bestWR = wR;
bestWL = wL;
};
instead of bestWR=WR, WR-1 should be assingned.
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;
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)
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;
}
}
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;
}
}
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;
}
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)
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).
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()
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))
}
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;
}
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);
}
}
#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;
}
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:
- ninhnnsoc October 22, 2014