7
\$\begingroup\$

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 > 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
\$\endgroup\$
5
  • \$\begingroup\$ So the task basically was to decompose the numbers into digits and then rearrange those digits to form the largest possible value that could be represented by these digits? \$\endgroup\$
    – AlexV
    Jul 3, 2019 at 8:43
  • \$\begingroup\$ yeah... as I understood it \$\endgroup\$ Jul 3, 2019 at 8:56
  • 3
    \$\begingroup\$ You're probably not allowed to decompose the numbers into digits. Why would they specify not digits, but numbers otherwise? \$\endgroup\$ Jul 3, 2019 at 19:44
  • \$\begingroup\$ see geeksforgeeks.org/… \$\endgroup\$ Jul 3, 2019 at 20:00
  • \$\begingroup\$ Firstly, you could use a list instead of a dictionary for work_dict if I'm not mistaken \$\endgroup\$ Jul 5, 2019 at 12:24

6 Answers 6

7
\$\begingroup\$

First of all, whenever you see this ... this is a big no-no:

'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]

it could be replaced by a simple

''.join(str(i) * work_dict[i] for i in reversed(range(10)))

Of course, the initialization of the work_dict is similar. And in fact, you don't need to initialize it if you take care to use dict.get instead of dict[]:

work_dict[number] = work_dict[number] + 1
# is equivalent to
work_dict[number] = work_dict.get(number, 0) + 1  # default to 0 if not in dict

Ps., whenever you are counting something, consider using collections.Counter.


Warning: The rest of this answer tries to address the problem that OP say they are solving in the comments to the question. However, it is not certain that the understanding of the problem by the OP is correct. From here on, we assume that you are allowed to shuffle all the input digits, whereas the original problem probably only allows shuffling around the numbers.


If you want to have it as compact and "functional" as possible, it would be much easier to just sort the entire input and output it:

def maximum_number(lst):
    return int(''.join(sorted(''.join(str(x) for x in lst), reverse=True)))

However, note that this doesn't work on the empty list (which might be okay, depending on the specification of the function).

It should also be mentioned that

  1. it is harder to write than the "manual loop" variant, which can be important in an interview
  2. it might be harder to read and thus to debug, but I believe that this is up to the eye of the beholder to determine

For complexity, this is O(n log n) whereas the optimal algorithm has running time O(n). We again see the trade-off between running time and readability.

Here is an O(n) algorithm using Counter:

from collections import Counter
def maximum_number(lst):
    counter = Counter()
    for elt in lst:
        counter += Counter(str(elt))
    return int("".join(str(i) * counter[str(i)] for i in range(9, -1, -1)))
\$\endgroup\$
7
  • \$\begingroup\$ This is very compact indeed. But is it in any way more performant than my code? I mean, both will find it in a magnitude of the sorting algorithm, which is on average O(n*log(n)), correct? You do get some optimization, from treating the num as a string though, so you save the deconstruction. \$\endgroup\$ Jul 3, 2019 at 10:24
  • 1
    \$\begingroup\$ sorted also accepts reverse=True as argument, so you could get rid of the outer reversed. \$\endgroup\$
    – AlexV
    Jul 3, 2019 at 10:27
  • 1
    \$\begingroup\$ @DavidRefaeli Updated in answer. Added an O(n) algorithm using Counter instead of the manual dict approach. \$\endgroup\$
    – Pål GD
    Jul 3, 2019 at 10:51
  • 1
    \$\begingroup\$ No need to use .get(...) for the counter as per the doc, missing elements have a count of 0. You can also see this in the counter implementation that was already contained in my answer. \$\endgroup\$
    – AlexV
    Jul 3, 2019 at 11:00
  • 1
    \$\begingroup\$ @EricDuminil I added a note before the section where I start sorting and counting. \$\endgroup\$
    – Pål GD
    Jul 4, 2019 at 13:05
7
\$\begingroup\$

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.

\$\endgroup\$
7
  • \$\begingroup\$ Consider initializing (if necessary) the dict using dict comprehension { str(x) : x for x in range(10)}. \$\endgroup\$
    – Pål GD
    Jul 3, 2019 at 9:10
  • \$\begingroup\$ @EricDuminil: I specifically ask the OP for this aspect, and he affirmed it. So technically at the time of writing the answer was valid. \$\endgroup\$
    – AlexV
    Jul 3, 2019 at 20:25
  • 1
    \$\begingroup\$ @EricDuminil: I also included my take on that "alternative" (maybe correct) interpretation. \$\endgroup\$
    – AlexV
    Jul 3, 2019 at 20:39
  • 1
    \$\begingroup\$ Perfect. I haven't seen an example for which cmp= is needed in a long time. Too bad it's been removed. \$\endgroup\$ Jul 3, 2019 at 20:46
  • 1
    \$\begingroup\$ Already in base 10?? Huh? The OP has binary integers, not strings. Your own solution uses str(number) so you're already actively / explicitly converting from number to ASCII decimal string. Maybe what you meant to say is that Python has an efficient int->string function built-in which happens to use base 10 :P. \$\endgroup\$ Jul 4, 2019 at 5:05
7
\$\begingroup\$

The question reads :

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. (Emphasis mine)

In a comment it was stated :

The task basically was to decompose the numbers into digits and then rearrange those digits to form the largest possible value that could be represented by these digits

Those two statements are very different and I'd tend to believe you either misunderstood the interview question or you didn't explain it properly. The example you gave, 22110 isn't constructed by the digits [2,2,1,1,0], but by the numbers [2,21,10]. This fits much more with how you worded your question.

With your code, getting an input of [20,210,32] would yield the result 3222100, but the actual answer should be 3221020 because of [32,210,20].

At least, this is all assuming that the requirements that you put in your questions are specifically the one you received in the interview, meaning you misunderstood the question.

\$\endgroup\$
7
  • \$\begingroup\$ 3222100 is the correct max number, at least I think, as I don't have the question in front of me anymore - but there were enough examples from which I understood this. I emphasized the not digits to stress that you need to break the number into digits. \$\endgroup\$ Jul 3, 2019 at 17:33
  • 4
    \$\begingroup\$ @DavidRefaeli It's hard to tell from the statement you gave in your question and it really feels like it's wrong. Are you sure didn't just see it this way? Because as I wrote, for the example you gave both explanations work. \$\endgroup\$
    – IEatBagels
    Jul 3, 2019 at 17:38
  • 1
    \$\begingroup\$ You're 100% correct. The question is completely boring otherwise. See geeksforgeeks.org/… \$\endgroup\$ Jul 3, 2019 at 19:56
  • \$\begingroup\$ well, now I can't be sure... but could be. Who knows... \$\endgroup\$ Jul 3, 2019 at 20:39
  • 1
    \$\begingroup\$ @EricDuminil oh god.. Ahah. It looks good now? \$\endgroup\$
    – IEatBagels
    Jul 4, 2019 at 18:18
3
\$\begingroup\$

As mentioned by @IEatBagels, it seems that you didn't understand the question. You're not allowed to split numbers into digits. You're only allowed to reorder whole numbers in order to get the maximum joined number. The output for [0, 12] should be 120, not 210!

Others answers are proud to be O(n) or O(n log n), but well, they're probably wrong.

So I'm proud to present this O(n!) solution:

from itertools import permutations

def joined_number(numbers):
    return int(''.join(str(number) for number in numbers))

max(permutations([20,210,32]), key= joined_number)
# (32, 210, 20)

max(permutations([1, 19, 93, 44, 2885, 83, 379, 3928]), key= joined_number)
# (93, 83, 44, 3928, 379, 2885, 19, 1)

The performance is horrible and it will fail for lists longer than ~10 elements, but at least you can play with it in order to understand what the real question was.

You can then try to look for the sort which could give you the correct answer.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ Downvoter: constructive criticism is welcome. \$\endgroup\$ Jul 3, 2019 at 20:47
  • 3
    \$\begingroup\$ @PeterCordes: If I understood your proposal correctly, the most straightforward implementation would be using sorted(numbers, key=str, reverse=True). However, this does yield the wrong result for inputs like [9, 2, 5, 51] -> [9, 51, 5, 2] where it should be [9, 5, 51, 2] instead. \$\endgroup\$
    – AlexV
    Jul 4, 2019 at 5:54
  • 1
    \$\begingroup\$ @AlexV: Ah, well spotted. You're right, it's not as simple as I thought. And it's not just leading digit then shortest, either. Because 59 should sort ahead of 5, but 51 should sort behind 5. But grouping by leading digit lets you cut down the brute-force search space by an order of magnitude until we think of something better than trying every possibility. \$\endgroup\$ Jul 4, 2019 at 5:56
  • 2
    \$\begingroup\$ @PeterCordes: The simplest counter-example I could find is [0, 1, 10]. The problem is solved with "sorting by comparator" (see geeksforgeeks.org/… and AlexV's answer, which are basically the same) but it would be interesting to see if there's any simple "sort by key" solution. \$\endgroup\$ Jul 4, 2019 at 6:11
  • 1
    \$\begingroup\$ @EricDuminil: oh cool, until seeing the solution, it wasn't clear to me there was a transitive or whatever it's called property here that would allow a comparison sort, where a < b and b < c implies a < c \$\endgroup\$ Jul 4, 2019 at 6:15
2
\$\begingroup\$

EDIT: After talking to Baldrickk in the comments, I've realized that my sort by key method doesn't work for this problem. For instance, the below approach would sort [50,505040] as 50504050 instead of 50505040. I'm leaving the answer up for those who are interested.


This is my attempt at solving the problem assuming that the OP did indeed misinterpret the question and that the numbers can't be split up into digits. Going off of AlexV's answer I've come up with a simple sort by key solution (rather than sort by cmp). I would have posted this as a comment but I lack the reputation.

The first step is to realize that since the first digit is the most significant, the second digit the second most significant and so on, we can simply do an alphabetical sort.

def maximum_number(lst):
  return int("".join((str(n) for n in sorted(lst, key=str, reverse=True))))

So this will work for most cases.

But as AlexV pointed out in a comment, this neglects that, for instance, 5 should be sorted ahead of 51 (since 551>515), 1 ahead of 10, etc.

The key element to take note of here is that a number n that begins with a digit d should be sorted ahead of a number nk if k < d, but behind nk if k > d. If k = d, the order is arbitrary. This can be adjusted for by appending the first digit of every number onto itself, yielding the following solution.

def sorting_key(num):
  num_str = str(num)
  return num_str + num_str[0]

def maximum_number(lst):
  return int("".join((str(n) for n in sorted(lst, key=sorting_key, reverse=True))))

This passes all examples I've seen posted in other answers.


Thanks to Baldrickk for pointing out that the first revision of this answer would fail at [50,501]

\$\endgroup\$
16
  • \$\begingroup\$ maximum_number([50,501])? \$\endgroup\$
    – Baldrickk
    Jul 4, 2019 at 10:02
  • 1
    \$\begingroup\$ 2*str(num) appears to be a better sorting key - I haven't checked to see it it is optimal \$\endgroup\$
    – Baldrickk
    Jul 4, 2019 at 10:08
  • \$\begingroup\$ @Baldrickk Thanks for pointing that out. You can account for that by using the first digit, rather than the last. I've edited the answer occordingly. \$\endgroup\$ Jul 4, 2019 at 10:12
  • 1
    \$\begingroup\$ @Baldrickk That method fails on [50501,50] (5050150 instead of 5050501). \$\endgroup\$ Jul 4, 2019 at 15:20
  • 2
    \$\begingroup\$ Sigh... The whole code in Ruby would be numbers.sort{|a,b| [b, a].join <=> [a, b].join } because sorting by comparator hasn't been removed. Python is a great language with many good design decisions but this one doesn't feel right. \$\endgroup\$ Jul 4, 2019 at 18:57
-1
\$\begingroup\$

Here's what I came up with. It runs in O(n) because of the for each loop, and seems to be a nice readable option to me.

numberList = [1, 19, 93, 44, 2885, 83, 379, 3928]

def largestNumber(value):
    string = ''
    for number in value:
        string = string + str(number)
    result = ''.join(sorted(string, reverse=True))
    return(int(result))


print(largestNumber(numberList))


Output: 99998888754433332211

Your solution works in the same time complexity, so they are both on the same page in that regard, but stringing the values together and using python's built in sorting function saves some space and complexity.

\$\endgroup\$
7
  • \$\begingroup\$ The answer should be 93834439283792885191. \$\endgroup\$ Jul 3, 2019 at 20:25
  • \$\begingroup\$ Doesn't sorted(string, reverse=True) use an O(digits log digits)` sorting algorithm? Or does Python use CountingSort for sorting the characters of an ASCII or UTF-8 strings to get O(char) complexity? \$\endgroup\$ Jul 4, 2019 at 5:09
  • 1
    \$\begingroup\$ @PeterCordes There's not much difference between O(n.log n) and O(n) anyway, but I'm pretty sure the complexity will be O(n. log n) here. \$\endgroup\$ Jul 4, 2019 at 9:24
  • \$\begingroup\$ @PeterCordes, I know the time complexity of the sort is O(n log n) because Python uses Timsort, but the overall time complexity should still be O(n) since the for each loop iterates over every item of the input numberList, right? \$\endgroup\$ Jul 8, 2019 at 19:52
  • \$\begingroup\$ N * log(N) grows more quickly than N, by an extra factor of log(N). So it dominates the for-loop's time. You have O(N + N*log(N) ) which simplifies to O( N*log(N) ) \$\endgroup\$ Jul 8, 2019 at 20:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.