Linux Device Driver C Programming Interview Questions

Hi everyone,

Recently, I took an online assessment for a Linux device drivers position at AMD. The assessment required completing a C programming task within 16 minutes. I felt the pressure to finish within that timeframe.

Now, come to the point:

The question was to Arrange an array based on the frequency of its numbers. Frequency refers to the number of times each number occurs in the array.

For example:
Input: [1, 2, 1, 2, 2, 3]
Output:[3, 1, 1, 2, 2, 2]

Approach for above problem statement

• Check if the Array is Valid:
  First, the program checks if the input array is empty or has zero elements. If it does, the function simply returns nothing (NULL) because there's nothing to sort.

• Identify Unique Numbers and Their Counts:
  The program then goes through each number in the array and keeps track of how many times each number appears. It does this by creating two lists:

  • One list to store the unique numbers found in the array.

  • Another list to store how many times each of these unique numbers appears.

• Sort the Numbers by Frequency:
  Once the program knows how often each number appears, it sorts the numbers based on their frequency. The numbers that appear less frequently come first, and the numbers that appear more often come later.

• Rebuild the Array:
  After sorting, the program rebuilds the original array but with the numbers arranged according to their frequency.

  For example, if the number 2 appeared the most, it would be at the end of the new array.

• Output the Sorted Array:
  Finally, the program prints out the newly arranged array, where the numbers are sorted by how often they appear.

• Clean Up:
  The program also makes sure to free up any memory it used to store temporary lists, which is good practice to avoid memory leaks.

Complete C program with above approach

#include <stdio.h>
#include <stdlib.h>

int *sortedArrayList(int arrayCount, int *arrayList, int *resultArray){

    if(arrayCount<=0)
        return NULL;

    int i,j;
    int *uniqueEle = malloc(sizeof(int)*arrayCount);
    int *count = malloc(sizeof(int)*arrayCount);
    int uniqueCount = 0;

    for(i=0; i<arrayCount; i++){
        int num = arrayList[i];
        int matchFound = 0;
        printf("Processsing Num: %d\n", num);
        for(j=0; j<uniqueCount; j++){
            if(uniqueEle[j] == num){
                count[j]++;
                matchFound=1;
                printf("Found num: %d\n Count increment: %d\n", num, count[j]);
                break;
            }
        }
        if(!matchFound){
            uniqueEle[uniqueCount] = num;
            count[uniqueCount] = 1;
            printf("New number added: %d\n", num);
            uniqueCount++;
        }
    }

    printf("\n=========================================\n");
    printf("Before Sorting:\n");

    for(i=0;i<uniqueCount;i++)
        printf("Number %d Count %d\n", uniqueEle[i], count[i]);

    for(i=0;i<uniqueCount-1;i++){
        for(j=i+1;j<uniqueCount;j++){
            if(count[i]>count[j]){
                int tempCount = count[i];
                count[i]=count[j];
                count[j]=tempCount;

                int tempNum = uniqueEle[i];
                uniqueEle[i]=uniqueEle[j];
                uniqueEle[j]=tempNum;
            }
        }
    }

    printf("\n=========================================\n");
    printf("After Sorting:\n");

    for(i=0;i<uniqueCount;i++)
        printf("Number %d Count %d\n", uniqueEle[i], count[i]);

    int index = 0;
    for(i=0;i<uniqueCount;i++){
        for(j=0;j<count[i];j++){
            resultArray[index++]=uniqueEle[i];
        }
    }

    free(uniqueEle);
    free(count);    

    return resultArray;
}

void printArray(int count, int *arrayList)
{
    int i=0;
    while(count--)
        printf("%d ", arrayList[i++]);
}

int main(int argc, char **argv){
    int arrayList[]={1,2,1,2,2,3};
    printf("Array List: ");
    printArray(sizeof(arrayList)/sizeof(arrayList[0]), arrayList);
    int *output=malloc(sizeof(int)*(sizeof(arrayList)/sizeof(arrayList[0])));
    output = sortedArrayList(sizeof(arrayList)/sizeof(arrayList[0]), arrayList, output);
    printArray(sizeof(arrayList)/sizeof(arrayList[0]), output);
    return 0;
}

Github Link for complete code

Output from above code

pi@SuyogB:~/Computational_Algoritthms/Interview_Questions $ ./Count_Frequency.bin
Array List: 1 2 1 2 2 3 
Processsing Num: 1
New number added: 1
Processsing Num: 2
New number added: 2
Processsing Num: 1
Found num: 1
 Count increment: 2
Processsing Num: 2
Found num: 2
 Count increment: 2
Processsing Num: 2
Found num: 2
 Count increment: 3
Processsing Num: 3
New number added: 3

=========================================
Before Sorting:
Number 1 Count 2
Number 2 Count 3
Number 3 Count 1

=========================================
After Sorting:
Number 3 Count 1
Number 1 Count 2
Number 2 Count 3


3 1 1 2 2 2

Summary:

The problem involves rearranging the elements of an array based on the frequency of each element's occurrence. The solution first counts how often each number appears, similar to creating a histogram. Then, it sorts the numbers by their frequency and reconstructs the array with the numbers ordered from least to most frequent. Finally, the newly arranged array is output.

So, it’s like a histogram approach because it first builds a frequency distribution of the array's elements before sorting and reconstructing the array based on that distribution.