Re: Arranging the keys problem
- From: Sc0rpi0 <sc0rpi0@xxxxxxxxxxxxxx>
- Date: Thu, 29 Sep 2005 23:08:43 +0200
Willem:
> ) There are n keys of different 3 colors say white ,red and blue only.Now
> ) we have to arrange keys such that red keys come before white ones and
> ) white ones come before blue keys eg RWWBBB where the keys are placed in
> ) any random order.Give me a linear time algorithm to solve this problem
> ) ( O(n)).
>
> Quicksort. You may need a slight tweak to make it linear time.
OMG ;) and you wonder why that interviewer did not liked your algs. ;) ?
Just "sorting by counting". If we have definied set of extacly know
elements, there is: R,W,B. so even if given in totally random order
just one pass counting how many was W,R and B. Then write that many
to the table. RRRRRRWWWBBBBBBBBBBBBBBB - sorted.
--
Sc0rpi0
I hated going to weddings.
All the grandmas would poke me saying "You're next".
They stopped that when I started doing it to them at funerals.
.
- Follow-Ups:
- Re: Arranging the keys problem
- From: Willem
- Re: Arranging the keys problem
- References:
- Re: Arranging the keys problem
- From: Willem
- Re: Arranging the keys problem
- Prev by Date: Re: Arranging the keys problem
- Next by Date: Re: Reverse words in a string (Another Interview question)
- Previous by thread: Re: Arranging the keys problem
- Next by thread: Re: Arranging the keys problem
- Index(es):
Relevant Pages
|
