“Write a function that given a list of non negative integers, arranges them such that they form the largest possible number. For example, given [50, 2, 1, 9], the largest formed number is 95021.”
This one comes from an excellent blog by Mr. Valdarrama and his apparently controversial post from a couple years ago.
Readers of the blog apparently came up with a few close-but-not-quite solutions, but all of them involve building a custom comparator for sorting the input array and then joining the array into a numerical string. Discerning what goes into the guts of the comparator is certainly a challenge, which is why I've never asked this particular question in an interview, but it's worth seeing how this problem can be solved I think, given a few different inputs.
First let's consider the initial input, [50, 2, 1, 9]
Looking at that sample we might think that doing a straight numerical comparison by iterating through each digit in the comparator's left and right arguments might work, and for this input it certainly does.
Here's a solution with numerical comparison by padding numbers with fewer digits with the previous digit (so 5 v 56 becomes 55 v 56).
That solution fails for a test input like [420, 42, 423] which should generate 42423420, but instead comes up with 42342420.
The answer it turns out is much simpler to write but more nuanced. Rather than comparing numbers directly to each other, if we compare the difference between the parsed strings made by combining the numbers lexically and determining which combination is larger we can create a simple rule for our comparator to test that works for all cases.
Check it out.
This is almost exactly the same as the standard comparator for integers except we're simply testing combinations of strings to see which pair makes the larger number, then bubbling the winner to the front of the array each step. At the end, we'll always end up with the largest possible number! Also we could reverse the order of the parseInt clauses to find the smallest possible number, which is pretty cool!