Uber Interview Questions - Move Zeroes

Uber Interview Questions - Move Zeroes As weve 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 didnt 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, well discuss a Uber interview question move zeroes. This question is usually asked in phone screens or as the first question in on-site interviews. Its for sure that youll 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 doesnt matter. Lets 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 Id like to discuss this problem is that it seems so simple at first glance, but youll be surprised at how many people didnt 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 cant 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 its 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, its 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, weve 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 dont really need to finish every single number. When we already reach the last count numbers, theres 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 its left = right or left right. (If you use left = right, youll have trouble with input like [1, 2]) Personally, Id like to keep code concise. So I wont add if array[left] == 0 before the swapping. In fact, this method modifies the array in-place. Therefore, theres 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 its 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..