Deshaw Inc Interview Question
Software Engineer / DevelopersIt resembles to concept of bucket sort as commented about assign a value to each color say red = 0.1 blue = 0.2 etc
let a[] be the array of marbles scattered (0.1,0.2,0.1,0.4,0.2....)
for(int i=0; i<n; i++)
insert a[i] into b[n*a[i]]
where n is total number of colors
insert in to b using a linklist
refer CLRS pg 174 Bucketsort
that does it in O(n) with space complexity n+ (total no of marbles)/n
Assign a value for marbles of each color.Sort them O(nlogn).
- dream December 28, 2009If the no of colors are 2 or 3 then we can do it in O(n)