Screenshot 2017-01-19 11.36.44

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

This week, I’m going to discuss the question – arrange given numbers to form the biggest number possible. Like our previous posts about Uber interview questions, I’m focusing more about the analysis process than the final solution.

The idea is not to give our readers the answer/code immediately. Instead, I’d 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 candidate’s coding skills and has been asked by many companies including Uber, Facebook recently.

Second, we’ll 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, you’ll 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. That’s why I’d 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:

  1. Transform a number to a list of digits (number_to_digits)
  2. Sort the digits in descending order (biggest_number)
  3. Transform a list of digits back to the number (digits_to_number)

Let’s first take a look at the code and I’ll 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, it’s number 0. Though you don’t 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 it’s 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, don’t worry about the exact syntax. For instance, it’s completely okay to just write sort(digits, Reverse=True) when you can’t remember the syntax.

 

Get Next Greater Number

Let’s 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.

Let’s 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, it’s 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 it’s 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..

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 Facebook4Tweet about this on TwitterShare on LinkedIn1Share on Reddit0

7 thoughts on “Uber Interview Questions – Arrange Given Numbers To Form The Biggest Number Possible

  1. The analysis should have mentioned the negative input case as well, is it allowed or not.
    As it seems, it is not.
    If negative inputs are possible, the problem is a bit more interesting.

  2. Do interviews allow the use of library functions like sort() or str()?

    def find_largest_num2(n):
    nums = [x for x in str(n)]
    return “”.join(reversed(sorted(nums)))

  3. I got the same question when interviewed at Opera. What makes I did not pass was how to become log (n) in space and worst case complexity.

    1. F*#27n&c8k1i; awesome issues here. I’m very satisfied to look your article. Thank you so much and i’m having a look forward to contact you. Will you please drop me a e-mail?

  4. Let me propose better solution for original “The Biggest Number Possible”. You can significantly optimise sorting because of the two conditions:

    1. Elements have fixed length: 1
    2. Elements fall within very narrow and guaranteed range: [0 .. 9]

    So you can avoid using general purpose sort which is O (nlogn) on average and radix sort inspired search.

    1. Create an array of length 10 and prepopulate it with zeroes ( O(n) ).
    2. Using this array count the digits ( O(n) ).
    3. Go from most to least significant digits and output the digits according to count ( O(n) ).

    Input: 4283865
    Digit-counting array: [ 0, 0, 1, 1, 1, 1, 0, 0, 2, 0 ]

  5. You can optimise the implementation by sorting the array in ascending order in biggest_number function, you don’t need to reverse the digits in digits_to_numbers function as reversing does add some overhead.

Leave a Reply

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