Zoho Interview Question 2022 | Sorting

Zoho Interview Question 2022:
This is Zoho Interview Question 2022. Write a program to sort the given array according to frequency of elements.
Examples:
Sample 1
Input:
[2 , 3, 2 , 4, 5 , 12 , 2 , 3, 3 , 3 , 12 ]
Output
[3 , 3, 3 , 3, 2 , 2, 2 , 1 2, 1 2 , 4 , 5 ]
Sample 2 :
Input:
[0, 2, 1 , -1, 1 , 2 , 0, 4, -1 , 4 ]
Output
[-1 , -1 , 0, 0, 1 , 1, 2, 2, 4, 4 ]
In Zoho usually inbuilt/library functions like map, list etc are not allowed. So we are going see two approaches.
- Solution without library functions
- Solution using Map
Zoho Interview Question 2022 Approach:
Sample 1 Frequency list:
3 – > 4
2 -> 3
12 -> 2
4 -> 1
5 -> 1
Here you can see that element 3 have the highest frequency so all the 3 is placed in the beginning of the result. Elements are placed in the decreasing order of their frequency.
Sample 2 Frequency List:
-1 -> 2
0 -> 2
1 -> 2
2 -> 2
4 -> 2
In Sample 2, all the elements have same frequency. In that case we compare the element values. Elements with least value comes first. Ex: -1 comes first because it is the least of all the elements.
Logic ( without library functions)
To maintain the frequency of each element we are going to use count array which stores the frequency of the elements in input array. For each occurrence of an element increment the count in all the locations of that particular element
For example:
[smartslider3 slider=”4″]
Now use this count array and sort based on the frequency. While swapping swap both input array and count array. Note: For Simplicity we have used bubble sort. You can use quick sort or inbuilt functions like Arrays.sort() for better performance.
Program
[code lang=”java”]
int [] sortByFrequency(int[] arr)
{
int n = arr.length;
int count[] = new int[n];
//For each element, increment the count in all the occurrence of that particular element
for(int i = 0; i<n; i++)
{
for(int j = 0; j<n; j++)
{
if(arr[j] == arr[i])
count[j]++;
}
}
// Bubble sort
for(int i=0; i<n-1; i++)
{
for(int j=0; j<n-1-i; j++)
{
//Check the frequency
if(count[j] < count[j+1])
{
swap(j,j+1,arr);
swap(j,j+1,count);
}
//When frequency is same, check the value of element
else if(count[j] == count[j+1] && arr[j] > arr[j+1])
{
swap(j,j+1,arr);
swap(j,j+1,count);
}
}
}
return arr;
}
[/code]
Logic ( Using Map )
- Create a map to store the frequency of each element (<key,value> as <element, frequency> )
- Insert an element with frequency = 1 , if the map doesn’t contain that element.
- Increment the frequency of element, if map already contains that element.
- Sort the array based on the frequency map.
[code lang=”java”]
int [] sortByFrequency(int[] arr)
{
int n = arr.length;
Map<Integer,Integer> freqMap = new HashMap<>();
for(int i = 0; i<n; i++)
{
freqMap.put(arr[i],freqMap.getOrDefault(arr[i],0)+1);
}
// Bubble sort
for(int i=0; i<n-1; i++)
{
for(int j=0; j<n-1-i; j++)
{
if(freqMap.get(arr[j]) < freqMap.get(arr[j+1]))
{
swap(j,j+1,arr);
}
else if(freqMap.get(arr[j]) == freqMap.get(arr[j+1]) && arr[j] > arr[j+1])
{
swap(j,j+1,arr);
}
}
}
}
[/code]
Let us know your approach in comments section. Happy Coding 🙂