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.
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.
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 count of the number of zeroes and traverse the array from left.
- If the number is not 0, skip.
- If it’s 0, keep increasing count until array[n-count] is not 0. Then set current number to array[n-count].
- 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
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.
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.
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..