## Tribal Fusion Interview Question Software Engineer / Developers

- 0of 0 votes
Given an array of n elements. The array can have duplicates.

Now sort the array based on frequency of distinct number in array.

eg: a= [3,4,2,5,3,3,4,2,1,5}

output = {3, 4,2,5,1} coz, 3 occurs thrice, 4,2,5 occurs twice, so they are retained in order of there occurrence in original array, and at last 1, as it appears least number of time.

**Country:**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 on January 29, 2012 Edit | Flag Reply