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.

1.  Solution without library functions
2.  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 )

1. Create a map to store the frequency of each element  (<key,value> as <element, frequency> )
2. Insert an element  with frequency = 1 , if the map doesn’t  contain that element.
3. Increment the frequency of element, if map already contains that element.
4. 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 🙂

You Might Also Like

Zoho Interview Experience | 2021

Zoho Question | Sum of Binary-Decimal Number