Subj : Re: Arranging the keys problem
To   : comp.programming
From : August Karlstrom
Date : Fri Sep 30 2005 03:08 am

Sc0rpi0 wrote:
> 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.

Each key probably refer to a distinct record, so we need to copy them to 
a new table. Hence the running time and the space requirement is O(n) 
with this approach. Anyway it meets the requirements :-)


August

.