Degree of Array – Interview Question

Degree of Array – Interview Question

November 9, 2018 Uncategorized 0


Find the degree of an array where degree of an array is the maximum frequency of any element in the array. Also find the smallest possible sub-array with the same degree.

To begin with, make sure you understood the question correctly. Write a sample array on the whiteboard and ask them if the degree you calculated is correct. Ask about how to handle collisions i.e. if two elements have same count, how do we want to handle such scenarios

Sample Array: [1,2,3,4,5,1,7,9,1,2,5,3]
In order to find the degree of the array, we will have to loop through the array and count the occurrence of each element. Once we have the counts, we can find the element with maximum count.
To find the count, we can use a HashTable where key is the element and count is the value. As we loop through the array, we add the key with value 1, if it doesn’t exist or incrementing the value if it exists.

However, we also need to find the min sub array with same degree. To get that, we will have to keep track of the first index and last index of each element. So value in the hastable needs to be 3 things instead of just a simple count.
So, we can create another object like this:


Class ElementInfo{
Int count
Int leftIndex
Int rightIndex
}

Now when we loop through the array, if the element doesn’t exist in HashTable we can add the element key with value 1, leftIndex as the index where we are at and right index as i.
If we see the same element again, we increment the count, and update rightIndex as the currentIndex.
Let’s take a look at the pseudo code:


Dictionary elementInfo
Loop(I = 0 -> arr.Length - 1)
{
If( ! elementInfo.ContainsKey(arr[i]))
elementInfo.Add(arr[i],
new ElementInfo() {count = 1, leftIndex = i, rightIndex = i } )
else
{
elementInfo[arr[i]].count = elementInfo[arr[i]].count + 1;
elementInfo[arr[i]].rightIndex = i;

}

}

Loop through Dictionary
{
Get Values with Max count.
}

Loop through Values with max count
{
Find element with minimum right Index - Left Index
}

Next the interviewer might ask you to write the actual code on the whiteboard.
Please make sure to take care of all the edge cases.
The GitHub link to the actual working code is here.
I will be adding more such interview questions to my youtube channel, please subscribe to my channel Coach4Dev for more such questions.