[prog] An interview question

[Michael Bentley]

On Aug 3, 2007, at 7:37 PM, priya venkateshan wrote:

> I attended a job interview of Oracle recently, and I was asked one  
> question
> whose answer I'm not sure of.
> You are given a set of numbers. You have to arrange them such that the
> result from concatenating all the numbers is largest.
> Like for e.g you have 114, 81, 8, you are supposed to give the  
> output as
> 881114. You are not allowed to change the order of digits in the  
> original
> numbers given.
> Initially, i thought of sorting on the basis of most significant  
> digit, [it
> would be 1 for 114, 8 for 81 and 8], but the problem arises when  
> the most
> significant digits are the same. It would be cumbersome to keep  
> sorting on
> the basis of the next most significant digit, so instead of storing  
> it as
> ints, i decided to store the numbers as character strings.
> A dictionary-type of sort doesnt work here as the number strings  
> are of
> different lengths, so to make them all the same length, i proposed the
> following method
> if you have 114, 81 and 8,
> you make them all of uniform length which is maximum length in the
> collection +1
> and to pad up the remaining, i suggested repeating the number.
> so you would have 1141, 8181, 8888.
> Now when you sort it alphabetically or numerically, you'll have  
> 8888, 8181,
> 1141.
>
> Could anyone tell me why this will not work, and give cases where  
> it might
> not?

I don't really understand how your approach works.  Can you post some  
code?  In the meantime, here's a stab at a possible solution:

---[cut]---
#!/usr/bin/env python

nums = [114, 81, 88]
answer = 0

def all_permutations(lst):
     if len(lst) <=1:
         yield lst
     else:
         for perm in all_permutations(lst[1:]):
             for i in range(len(perm)+1):
                 yield perm[:i] + lst[0:1] + perm[i:]

for candidate in all_permutations(nums):
     n = int(''.join(str(x) for x in candidate))
     if n > answer:
         answer = n

print answer
---[cut]---

hope this helps,
Michael

---
(do (or (do (not '(there is no try))) ()))