Find max number you can create from an array of numbers Was asked this in an interview yesterday:

You are given an array of numbers (not digits, but numbers: e.g. 9, 23, 184, 102, etc.) - you need to construct the largest number from it. For example: you get 21, 2, 10 - the largest number is 22110. 

This is my solution, I wonder if you can improve this?

def maximum_number(a):
    work_dict = {
        0: 0,
        1: 0,
        2: 0,
        3: 0,
        4: 0,
        5: 0,
        6: 0,
        7: 0,
        8: 0,
        9: 0
    }

    for ai in a:
        # if ai is a single digit number, just add it
        if ai in work_dict:
            work_dict[ai] += 1
            continue

        # otherwise, decompose it to it's digits
        while ai &gt; 0:
            number = ai % 10
            work_dict[number] = work_dict[number] + 1
            ai = int(ai/10)

    max_num = int('9'*work_dict[9] + '8'*work_dict[8] + '7'*work_dict[7] + '6'*work_dict[6] +
                    '5'*work_dict[5] + '4'*work_dict[4] + '3'*work_dict[3] + '2'*work_dict[2] +
                    '1'* work_dict[1] + '0'*work_dict[0])

    return max_num
Your code

Your code as such seems to be functional, but not really elegant or concise. 

First, the variable names don't speak for themselves. Nobody would be hurt if the function input was named numbers instead of a and number instead of ai. work_dict is also  not a particularly good name since it's very generic. How about digit_histogram?

Handling single digit numbers separately seems unnecessary. The algorithm you implemented can handle them without special treatment.

When constructing max_num, there is a lot of repeated code. You could simplify this using a list comprehension and join (more on that soon).

How I would have tackled this

Since we have the luxury that combination of these numbers should be maximized in base 10, we can get their digits simply by looking at their str representation (which coincidentally happens to be in base 10 ;-) )1.

If you include the other recommendations from above you end up with:

def maximum_number_str(arr):
    digit_histogram = {
        "0": 0, "1": 0, "2": 0, "3": 0, "4": 0,
        "5": 0, "6": 0, "7": 0, "8": 0, "9": 0
    }
    # or: digit_histogram = {str(i): 0 for i in range(10)}

    for number in arr:
        for digit in str(number):
            digit_histogram[digit] += 1

    max_num = "".join(str(i)*digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)


Depending on how familiar you are with Python and if other modules are allowed, you could come up with a solution using collections.Counter, or at least skip the dict initialization all-together if you use .get(...) instead of [...] when accessing the dictionary as presented by Pål GD in is answer.

Just for reference, this is how it could look like using a Counter:

from collections import Counter

def maximum_number_counter(arr):
    digit_histogram = Counter()

    for number in arr:
        digit_histogram.update(str(number))

    max_num = "".join(
        str(i) * digit_histogram[str(i)] for i in reversed(range(10)))

    return int(max_num)




Edit: The other way to think about that task

There seems to be a vivid discussion here if you understood the task correctly. If you follow the arguments that speak against your and my former interpretation, this actually leads to another interesting problem.

I came up with the solution below, though I highly doubt that I could have come up with this in an interview situation.

from functools import cmp_to_key


def maximize_joint_number(number1, number2):
    joined12 = int(str(number1)+str(number2))
    joined21 = int(str(number2)+str(number1))
    return joined21 - joined12


def maximum_number(numbers):
    """
    Generate the largest possible number that can be generated rearanging the
    *numbers*, not the digits of the input sequence
    """
    return int("".join(str(i) for i in sorted(numbers, key=cmp_to_key(maximize_joint_number))))


The idea to this is actually from this blog post that was given in a comment by Eric Duminil. The cmp_to_key trickery is needed because the cmp keyword was removed from sort in Python 3. You could also use cmp_to_key as a decorator, which makes it a little bit nicer:

from functools import cmp_to_key

@cmp_to_key
def maximize_joint_number(number1, number2):
    ...

def maximum_number(numbers):
    return int("".join(str(i) for i in sorted(numbers, key=maximize_joint_number)))


A quick test seems to fulfill all the presented example outputs:


if __name__ == "__main__":
    assert maximum_number([0, 12]) == 120
    assert maximum_number([2, 21, 10]) == 22110
    assert maximum_number([9, 2, 5, 51]) == 95512
    assert maximum_number([20, 210, 32]) == 3221020
    assert maximum_number([1, 19, 93, 44, 2885, 83, 379, 3928]) == 93834439283792885191


The second and third test case break implementations that would try to use something like sorted(numbers, key=str, reverse=True) (lexicographical sort) directly.



1 Thanks to Peter Cordes for pointing out the inaccurate wording here in earlier revisions.