As we’ve emphasized many times, most people overestimate the difficulty of Uber/Google/Facebook interview questions and underestimate the importance of bug-free code.

At the end of the day, many people have complained that the questions were simpler than expected, but they didn’t manage to write clean code. Especially when someone is looking over your shoulder, people tend to be nervous.

In our recent posts like this, I really want to discuss more fundamental questions, but get your code correct. This week, we’ll discuss a Uber interview question – move zeroes. This question is usually asked in phone screens or as the first question in on-site interviews. It’s for sure that you’ll write down the solid code and you get no chance if your code is buggy or inefficient.

## Move Zeroes

Modify the array by moving all the zeros to the end (right side). The order of other elements doesn’t matter.

Let’s have an example. For array [1, 2, 0, 3, 0, 1, 2], the program can output [1, 2, 3, 1, 2, 0, 0].

This question move zeroes has been asked by Uber recently (at the time of writing). One reason I’d like to discuss this problem is that it seems so simple at first glance, but you’ll be surprised at how many people didn’t get it right with a time limit.

## Analysis

The most naive approach should be extremely straightforward. By keeping two arrays: one for non-zero numbers and one for all zeroes, we can concatenate them at the end. Since we just need to traverse the array once, this will give us O(N) time complexity. Space complexity is O(N) as we need two additional arrays.

Apparently, time complexity can’t be improved __as we need to traverse the array at least once__. In order to use less space, we should look for modifying the array.

So we can have the following algorithm:

- Keep a counter
of the number of zeroes and traverse the array from left.**count** - If the number is not 0, skip.
- If it’s 0, keep increasing
until array[n-count] is not 0. Then set current number to array[n-count].*count* - After the traversal, set all last
numbers to 0.**count**

In essence, it’s like swapping 0 with numbers on the right. And the similar technique is used in at least the following two problems:

- Quick sort
- Shuffle an array in-place

## Improvements

As you can see, we’ve already got O(N) time complexity and O(1) space complexity. We also know that O(N) time complexity is the lower bound, the only way to further improve the algorithm is to reduce the number of operations, though we still keep O(N) time complexity.

If you think more about the above solution, there are some redundant operations. When we traverse the array, we don’t really need to finish every single number. When we already reach the last ** count **numbers, there’s no need to check zeroes as all of them should be set to 0.

In other words, the iteration should finish when index **i >= count**.

## Code

First of all, instead of using a counter, we simply use the *right *pointer that points to the right end of the array, which works exactly the same in essence. Therefore, when **left ***>= **right, *we can just put everything to 0. This removes redundant operations.* *

A couple of things you should be careful about the code:

- Validating inputs should always be the first thing in your mind.
- Be cautious about whether it’s
**left <= right**or*left < right.*(If you use left <= right, you’ll have trouble with input like [1, 2]) - Personally, I’d like to keep code concise. So I won’t add
**if array[left] == 0**before the swapping. - In fact, this method modifies the array in-place. Therefore, there’s no need to return the array.

## Summary

You can see that for the question move zeroes, the final code is no more than 15 lines and it’s still possible to make it more concise. This is the clean bug-free code that interviewers want.

By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interview with engineers from Google, Facebook, Uber etc..

The post is written by
**
Gainlo** - a platform that allows you to have mock interviews with employees from Google, Amazon etc..

I'd like to learn more

Code is broken!

3. If it’s 0, increase count by 1 and set current number to array[n-count].

I think 3rd step of algorithm is wrong. How could you guarantee that array[n-count] will not be non zero?

Thanks.

the posted code will fail if the last element of the input is 0. for ex: [1, 2, 0, 1, 3, 0] would give [1, 2, 0, 1, 3, 0]

Array can be traversed from left to right using two pointers: i (to read) and j (to write)

// Java code:

void moveZeroes(int[] src) {

int i = 0, j = 0;

do {

if (src[i] != 0) src[j++] = src[i];

} while (++i < src.length);

while(j < i) src[j++] = 0;

}

1. Keep a counter count of the number of zeroes and traverse the array from left.

2. If the number is not 0, skip.

3. If it’s 0, increase count by 1 and set current number to array[n-count].

4. After the traversal, set all last count numbers to 0.

For input [6, 0, 8, 0, 0] the algorithm will work like below :

Lets start traverse array. Array is zero based, so first index is 0.

1. i = 0; array[0] == 6; 6 != 0; count = 0;

Array stay same: [6, 0, 8, 0, 0]

2. i = 1; array[1] == 0; 0 == 0; count = 1;

Set 1st element value to (5-1)th element value. Array will same again [6, 0, 8, 0, 0]

3. i = 2; array[2] == 8; 8 != 0; count = 1;

Array stay same: [6, 0, 8, 0, 0]

4. i = 3; array[3] == 0; 0 == 0; count = 2;

Set 3rd element value to (5-2)th element value. Array will same again [6, 0, 8, 0, 0]

5. i = 4; array[4] == 0; 0 == 0; count = 3;

Set 4rd element value to (5-3)th element value. Array will change to [6, 0, 0, 0, 8]

6. After the traversal, set all last count numbers to 0. So we will set last 3 element to 0. Array will be:

[6, 0, 0, 0, 8]

Sorry

6. After the traversal, set all last count numbers to 0. So we will set last 3 element to 0. Array will be:

[6, 0, 0, 0, 0]

Hey Jake.

Can you please tell me how your code will give correct output for a test case like this ?

1 2 0 3 0 1 0

According to you whenever you find A[left] as zero you swap it with A[right], but what if A[right] is also zero. Then this swapping will be meaningless and as I can see in your code that left pointer will move forward without replacing 0 with a non zero number. As per I think if after swapping also A[left] remains zero then we shouldn’t move left pointer forward until we get a non zero value at A[right].

Correct me if I am wrong some where.

Does your code work with (0,1,2,0,4,3,0)

The condition is the array starts and ends with zero.

This seems to be missing the edge case where the right end is already a zero in the array, swapping it out with the left will bring a zero before the right pointer.

Following should work as well:

static void uber(int[] arr)

{

int i =0;

int j=arr.length-1;

while(j>i)

{

while(j>i&&arr[i]!=0)

{

i++;

}

while(j>i&&arr[j]==0)

{

j–;

}

//swap.

int temp = arr[i];

arr[i]=arr[j];

arr[j]=temp;

i++;

j–;

}

}

Thanks a lot for pointing out the bug in the code. We’ve fixed the bug and updated the code 🙂

def move_zeros (array):

pos = 0

for n in array:

if n == 0:

continue

array[pos] = n

pos = pos + 1

# Fill the rest of the array with 0’s.

while pos < len(array):

array[pos] = 0

pos = pos + 1

One line is enough:

A.sort(reverse=true)

That’s O(nlogn) but who cares: log(1 billion)=9

Code seems buggy still. Given input “[0, 0, 0, 1, 2, 0]”, the output is “[0, 2, 1, 0, 0, 0]”.

Here’s my code:

{code}

def move_zeros(lst):

“””Modify the array by moving all the zeros to the end (right side).

The order of other elements doesn’t matter.”””

if not lst:

return lst

left = 0

right = len(lst) – 1

while True:

while lst[left] != 0 and left = right:

break

while lst[right] == 0 and left = right:

break

lst[left], lst[right] = lst[right], lst[left]

{code}

void moveZerosToRight(int[] ia) {

int c = 0;

for (int i = 0; i < ia.length – c-1; i++) {

if (ia[i] == 0){

while (ia[ia.length – c -1] == 0){

c++;

}

ia[i] = ia[ia.length – c -1];

ia[ia.length – c -1] = 0;

c++;

}

}

}