[prog] An interview question

[priya venkateshan]

>>0] keep a tag to remember the length of the char string for each no.
yes... neglected to mention that here.

On 8/4/07, Vid Ayer <svaksha at gmail.com> wrote:
>
> 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
>



-- 
The reward for hardwork is only more hardwork. Everything else comes under
side-effects.
Priya Venkateshan,
III B.Tech, InfoTech,
NITK Suratkal
Blogging at http://thenitknumbskulls.wordpress.com