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:
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
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; }
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.
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); } } } }
Let us know your approach in comments section. Happy Coding 🙂