Tribal Fusion Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: Phone Interview
This solution will only work when numbers in array in this range of 0 to n-1. This is not specified in question.
It can be done with the concept of counting sort.
Pseudo code:-
a= [3,4,2,5,3,3,4,2,1,5}
int n=a.length();
int B[]=new int[max(a)]; //initialise with zero
for i<- 0 to n-1
do{
B[a[i]]++;
}
int start=0;
while(B!=null) // this whole loop will late o(m^2) time if m is large this method is not good
{ find max in B // in O(m) time m is the maximum element value
Let i th index is max
for(int j=start;j<B[i];j++)
{
a[j]=i;
}
We can use the hashing and link list combination here.
First create a hash table and values will be the frequency of no.
eg: a= [3,4,2,5,3,3,4,2,1,5}
hash table of size 5 (biggest no)
let say it is h[5].
h[1] = 0, h[2]=2, h[3]=3, h[4]=2, h[5]=2.
Now iterate the hash table ans use insertion sort using linked list.
It can be done by performing Counting Sort twice.
For the first time the frequency of each number is counted in another array.
For the second time, we perform counting on the frequencies with same value.
Space complexity = O(4n). Time Complexity = O(5n). So basically both space and time complexities are of the order n.
- cooldaa January 29, 2012