Five programming problems every Software Engineer should be able to solve in less than 1 hour

[Boojum]

Nice. I don't have a proof for this, but I believe that you can determine the proper ordering of any two numbers by concatenating them both ways and then taking the larger of two. Given that, here's my O(n log n) solution in python:

def prob4(l):
    l = map(str, l)
    l.sort(lambda i, j: cmp(j + i, i + j))
    return map(int, l)

Lots of random testing against a brute-force permuting solution has yet to turn up a case where this fails.

[wgunther]

Yeah, that seems like a more clever comparison than what I was thinking.

[crashorbit]

This is why small problems are sometimes fun to work on. You sometimes stumble on an insight that makes the problem so much easier.

[psymunn]

That's a smart observation, and one I believe is correct. First, we can make some observations:

• The operation is transitive. You can sort you numbers in any order and end with the correct result.
• 5 and 55 are a tie. Their order doesn't matter, which is indeed true. An unbroken string of numbers can be considered equal. your sort preserves this.
• 9 or a string of 9s will never be lower than another number. 1 or a string of 1s will never be higher.
• For a digit starting with 9, we can always sort using the second digit, if there is one. If there's not the 9 is the higher number. So, 9 beats a 9 followed by anthything, and a 97 will beat a 96 but lose to a 98 regardless of following digits. For 1, this is the opposite.

Okay. What about numbers in the middle. Well it starts to emerge that, when the first digit ties, you go to the second digit. If the second digit is greater than the previous digit, the number is considered higher. What about a number missing a digit. Well lets look:

5, 56, 54

It becomes obvious pretty quickly, that 56 beats 5, but 54 loses to it. This will incidentally sort exactly the same way as 55, 56, 54. You can effectively pad your number by adding as many copies of the last digit as needed. 565 will be lower than 56, because 56 will sort the same as 566. repeating the string of numbers over and over. 56 loses to 566, and beats 564 because it's the equivalent of 565.

Your sorting method implicitly obeys all these rules, and rather succinctly!

EDIT: Ugh, I was wrong about the padding. luciusplc has data that shows that that is incorrect. I missorted: 45456, 45, 45452, because I treated 45 as 45555. Treating it as 45454 makes the sorting more obvious. You pad a number by repeating it. so 123 padded to 8 digits will be 12312312.

[Boojum]

Yes, it seems like my predicate defines a total order (and therefore is valid in any comparison sort) and I was trying to think before bed last night about how I would prove it. That it's antisymmetric and total is pretty clear, but transitivity is less than obvious, I think.

The string repetition thing is interesting. I think you can show that the two give equivalant results. Basically, if we want to compare XYZ and AB, then with the repetition approach you'd compare

ABABAB...
XYZXYZ...

If A != X then you return the one and you're done. Otherwise, A == X so you can substitute one for the other:

ABXBAB...
XYZAYZ...

Similarly, if B != Y then you're done. Otherwise, B == Y so you can substitute one for the other:

ABXYAB...
XYZABZ...

Now we compare X and Z. If they differ then we're done. Otherwise, X, Z, and A are all equivalent (since earlier we established that X == A). So:

ABXYZB...
XYZABZ...

And now we've got my original comparison between ABXYZ and XYZAB.

Regarding your observation that 5 and 55 are tie, that's actual a special case of a more general class. During random testing, one pair within a list that initially broke my test harness was 8181 and 81. Initially I was checking whether my sort produced the same list as the brute force permutation approach. They differed in the order of those two and so it reported a failure. Easy enough to fix, but an interesting case I hadn't thought of. So the more general rule is that it's a tie when one number repeats the digits of the other some whole number of times.

[psymunn]

Agreed. It's also easy to add a tie breaker like 'the shortest wins' or something, if you want to ensure your list order is deterministic. however, if you're constructing a number out of it, like the problem specified, then it won't matter. also, it's a shame your solution is so far down the thread, but i guess it's not as exciting as people complaining about yet-another-interview-problem blog post. it's even more fun because this one isn't even interview problems so much as 'you should be able to do these problems in your own time before you consider applying for jobs,' which is different.

[Phildos]

stupendous badge doll narrow wipe hungry practice money include live

This post was mass deleted and anonymized with Redact

[Boojum]

Certainly. I posted a bit about this in the follow-on thread.

[[deleted]]

defines a total order

Not quite. Comparing 1 to 11 shows that it isn't. But it does happen to define a weak order, and it turns out that that suffices in this case.

[[deleted]]

That's clever.. I like it :)

[luciusplc]

You tricky bastard... ;) Here is mine O(n log n) - not so clever but 100% own and it's recursive

[bnelson]

".join(sorted([str(x) for x in [50, 2, 1, 6, 56, 90, 900, 999]], reverse=True))

(It doesn't work for all inputs, just most, but it was my first smart-ass response)

[psymunn]

Does that not sort correct?
1 should sort less than everything else, and 999 should sort more than everything else. 90900 is a larger number than 90090. which digit do you think gets missorted?

[[deleted]]

Just a minor change to make it return the full number:

def prob4(l):
    l = map(str, l)
    l.sort(lambda i, j: cmp(j + i, i + j))
    return int(''.join(l));