Uber Interview Questions - Arrange Given Numbers To Form The Biggest Number Possible

Uber Interview Questions - Arrange Given Numbers To Form The Biggest Number Possible This week, Im going to discuss the question arrange given numbers to form the biggest number possible. Like our previous posts about Uber interview questions, Im focusing more about the analysis process than the final solution. The idea is not to give our readers the answer/code immediately. Instead, Id like to guide you through the whole analysis process. At the end, I hope you can be equipped everything you need to solve similar questions. Here we go. Arrange Given Numbers To Form The Biggest Number Possible Write a function that takes a number as input and outputs the biggest number with the same set of digits. For example, suppose the input is 423865, then the biggest number with these digits is 865432. Two reasons I chose this question. First, this Uber interview question is a great problem to test candidates coding skills and has been asked by many companies including Uber, Facebook recently. Second, well also discuss an extension of this question, which makes the problem more interesting. Analysis I think most people should be able to come up with the right approach without difficulty. However, when it comes to code, youll be surprised about how many people fail to do that. In order to get the biggest number by rearranging the digits, all we need is to order all digits in descending order. For example, if the input is 62832, we just need to sort them and output 86322. As I mentioned above, few people can get the code right. Thats why Id like to focus more on the coding part. As a practice, please try to finish the code within 15min before reading rest of the post. Code To start with, we need 3 basic methods here: Transform a number to a list of digits (number_to_digits) Sort the digits in descending order (biggest_number) Transform a list of digits back to the number (digits_to_number) Lets first take a look at the code and Ill highlight few points after that. The code should be as simple as it is. A few points are worth to mention here: Instead of having a huge single method that does everything, we put two util methods separately. This is a good style to follow for both interview and real projects. Also, it makes it easier to code as the logic is clearer. We should always validate input and in this case, its number 0. Though you dont see any explicit validation here, I started the code by checking if the number is 0. However, it turned out to be unnecessary as the two util methods have handled that automatically. But its important to keep this in mind. Most of the time in an interview, you are not required to implement the sort by yourself (unless the question is about sorting). So feel free to use the system library. Also, dont worry about the exact syntax. For instance, its completely okay to just write sort(digits, Reverse=True) when you cant remember the syntax. Get Next Greater Number Lets change the question a little bit. How can you get the next greater number with the same set of digits? For example, suppose the input is 423862, then the biggest number with these digits is 426238. Think about it before reading following sections. One of the best ways to think is to try with examples. If all digits are in descending order, the number is already the largest one. So in essence, we should look for digits in the “wrong” order. Lets use the same example 423862. If we start from the right, digit 3 is in the “wrong” position because all digits after it 862 are in descending order. So to get the next greater number, all we need is to swap 3 with a bigger digit 6 and re-order the rest digits. So we can summarize the algorithm as follows: Go through each digit from right to left Find the first digit that is not in descending order. In the example, its 3. For all digits after the current digit (862), find the smallest one that is also greater than the current digit, which is 6. Swap it with the current digit. So the current number is 426832. The last step is to sort all digits after the current digit (6) in ascending order, so we get 426238. Summary Takeaways for question arrange given numbers to form the biggest number possible: Starting with some real examples is a great way to get ideas. Sometimes, you just need to summarize all your manual steps and that becomes the final algorithm. Have the right idea is far from half done! As you can see, getting to the right code to these two questions is not trivial. For the 2nd question, although there are just 10 lines of code (excluding comments), you should be very cautious about boundary checking to make it right. Separate util methods from the main function can keep your code much cleaner and actually its easier for you to implement. By the way, if you want to have more guidance from experienced interviewers, you can check Gainlo that allows you to have mock interviews with engineers from Google, Facebook, Uber etc..