PriorityQueue and Heap-based Questions in C# Coding Interview
ericwu90
720

Hi, I'm currently preparing for technical interviews and will be applying only to C# specific roles.

There are a few patterns that require using some sort of priority queue or heap, and those aren't available in C#.

Is there a work-around for this issue? Or should I bank on these sorts of problems not coming up in a role that is heavy on C#?

And should they come up, is it enough to explain the optimal solution to the problem and implement it as if I did have a heap/priority queue data structure even if I won't be able to compile?

For example, I recently worked on the following question: Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

The approach that I should probably take is to use a dictionary to hold a collection of KeyValuePair<int,int> where the key is the number and the value is the frequency, and then add those to a MinHeap of size K which heapifies based on the KeyValuePair's value instead of its key. Unfortunately I can't do that in C#, so I opted for a Linq approach instead... but the complexity is probably worse. Please see below! And if you have any suggestions on how I can solve this problem more efficiently in C#, that would be super appreciated. Thanks!

/*

Given an unsorted array of numbers, find the top ‘K’ frequently occurring numbers in it.

Example:

Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]

Approach:
// Create a dictionary to hold numCount KeyValuePairs
// Iterate through entire input array, adding/incrementing key value pairs // O(N), O(N)
// Create a list of keyvaluepairs, which is a sorted list version of the dictionary, orderbydescending // O(n log n), O(N)
// Add the first K elements from that list, into a result list of numbers // O(K), O(K)
// return the result list

Complexity:
// O(N + N log N + K) => O (n log n + k)
// O(N + N + K) => O(N + K)

*/

using System;
using System.Collections.Generic;
using System.Linq;

class Solution
{
    static void Main(string[] args)
    {
        int[] example = new int[] {1, 3, 5, 12, 11, 12, 11};
        List<int> answer = FindTopKFrequentNumbers(example,2);
        foreach (int number in answer)
        {
            Console.Write(number + " ");
        }
    }
    
    public static List<int> FindTopKFrequentNumbers (int[] input, int k)
    {
        List<int> result = new List<int>();
        Dictionary<int, int> numCounts = new Dictionary<int, int>();
    
        foreach (int number in input)
        {
            if (!numCounts.ContainsKey(number))
            {
                numCounts.Add(number,0);
            }
            numCounts[number]++;
        }
        
        List<KeyValuePair<int, int>> sortedNumCounts = numCounts.OrderByDescending(numCount => numCount.Value).ToList();
        
        
        for(int i = 0; i < k; i++)
        {
            result.Add(sortedNumCounts[i].Key);
        }
        
        return result;
    }
}
Comments (3)