- the first item is a number
- the second item is one of three colors (red, blue, or yellow).
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).
 
|
|
 
|
Sort on second key when, first key in a set is sorted
Assume that we are given as input n pairs of items, where
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).
For example: (1,blue), (3,red), (4,blue), (6,yellow), (9,red) should become (3,red), (9,red), (1,blue), (4,blue), (6,yellow).
Subscribe to:
Post Comments (Atom)
1 comment:
Solution :
1.> Iterate over the set.
2.> Store each element in a key-ordered look up table.
a.> the key being a function of the color
b.> the key order is such that red < blue < yellow
c.> the value is a list of the set's elements
3.> If the value for a set element is already present, simply append the set element to the value list and continue
4.> After all elements have been iterated over, simply iterate over the ordered key set and print the value list
Step 2b, could be a doubly linked list implementation, restricting the complexity to O(n)
Overall time complexity would also be O(n)
Post a Comment