screen-shot-2016-11-04-at-8-29-05-pm

Uber Interview Questions – Move Zeroes

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:

  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, keep increasing count until array[n-count] is not 0. Then set current number to array[n-count].
  4. After the traversal, set all last count numbers to 0.

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

Share on Facebook7Tweet about this on TwitterShare on LinkedIn0Share on Reddit0

15 thoughts on “Uber Interview Questions – Move Zeroes

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

  2. 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;
    }

  3. 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]

    1. 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]

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

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

  6. 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–;
    }
    }

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

  8. 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}

  9. 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++;
    }
    }
    }

Leave a Reply

Your email address will not be published. Required fields are marked *