Subj : Re: Arranging the keys problem
To   : comp.programming
From : Sc0rpi0
Date : Fri Sep 30 2005 12:08 am

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.

.