[prog] An interview question

[Vid Ayer]

On 8/4/07, priya venkateshan <priyaven at gmail.com> 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.
>

0] keep a tag to remember the length of the char string for each no.
[eg. 55555, all numbers in the array should uniformly be padded to 5
digits]

1] plus another tag to discard the padded digits

... that can give you the concatenated numbers with the largest result.

> Could anyone tell me why this will not work, and give cases where it might
> not?

It can work ...

-- 
Vid
http://wiki.ubuntu-women.org/VidAyer