Amazon Interview Question
Software Engineer / DevelopersCountry: India
The solution is not O(n).
Only the array formation part is O(n).
Number formation part is O(n^2)
Hi Exact name would be count sort.
It does put keys into buckets , however since the bucket can have only single element and we only store the count encountered.
@popoff As I mentioned in the answer above, the nested for loop part is actually O(n). The nested loop iterates as much as the number of digits. Note that having a nested loop does not always mean that we have O(n^2) execution time. This problem is a perfect example for this.
Just use counting sort ( O(n) ). Then rearrange the number starting with the biggest one.
Note that the nested for loop below make a total of n iterations only. So the resulting code is O(n).
- hakanserce January 02, 2013