Most common occurrence of an int in an array

Question

I am prepping for a junior level interview in C#. I am hoping I can get some feedback on how to improve my code to print the most common occurrence of an int in an array.

using System;
using System.Collections;
namespace FrequentInt
{
 class MainClass
 {
 static void CommomOcurrence (int [] array, Hashtable hs)
 {
 int mostCommom = array[0];
 int occurences = 0;
 foreach (int num in array) 
 {
 if (!hs.ContainsKey (num)) {
 hs.Add (num, 1);
 } 
 else 
 {
 int tempOccurences = (int)hs [num];
 tempOccurences++;
 hs.Remove (num);
 hs.Add (num, tempOccurences);
 if (occurences < tempOccurences)
 {
 occurences = tempOccurences;
 mostCommom = num;
 }
 }
 }
 foreach(DictionaryEntry entry in hs)
 {
 Console.WriteLine("{0}, {1}", entry.Key, entry.Value);
 }
 Console.WriteLine ("The commmon numer is " + mostCommom + " And it appears " + occurences + " times");
 }
 public static void Main (string[] args)
 {
 int[] array = new int[20]{ 3,6,8,5,3,5,7,6,4,3,2,3,5,7,6,4,3,4,5,7}; 
 Hashtable hs = new Hashtable ();
 CommomOcurrence (array, hs);
 }
 }
}

Answer 1

The one thing I find really wrong is that you're using a HashTable.
It is not generic, which means it will box every int to an object.
Use a Dictionary<int, int> instead.

And there is no reason to supply it as a parameter: it should be local to the method, so declare it there.

Last thing: you don't need the if-else to check if a Key is present.
Dictionary has a method TryGetValue for that. It also has an indexer.

Also realize, this will only find one number. If two numbers appear an equal number of times, only the first one will be found.

static void CommonOccurrence(int[] numbers) {
 var counts = new Dictionary<int, int>();
 foreach (int number in numbers) {
 int count;
 counts.TryGetValue(number, out count);
 count++;
 //Automatically replaces the entry if it exists;
 //no need to use 'Contains'
 counts[number] = count;
 }
 int mostCommonNumber = 0, occurrences = 0;
 foreach (var pair in counts) {
 if (pair.Value > occurrences ) {
 occurrences = pair.Value;
 mostCommonNumber = pair.Key;
 }
 }
 Console.WriteLine ("The most common number is {0} and it appears {1} times",
 mostCommonNumber, occurrences);
}

• Quill: I would suggest placing the Console.WriteLine outside the function, and simply returning mostCommonNumber and occurrences.

Answer 2

Whenever you're dealing with collections in C#, there's often a simple Linq solution.

Instead of using a Hashtable or Dictionary to group together and count each occurrence, use the .GroupBy method on the integers. This makes each integer a key with a list of values for each occurrence.

Then all you need to do to find the largest is to order by occurrence and take the first result. Using Linq's .OrderByDescending and .First methods do this for you.

static void CommonOccurrence(int[] numbers)
{
 var groups = numbers.GroupBy(x => x);
 var largest = groups.OrderByDescending(x => x.Count()).First();
 Console.WriteLine("The most common number is {0} and it appears {1} times", largest.Key, largest.Count());
}

---

If you wanted to take the same approach without relying on Linq to group and sort for you, you can make separate methods for each action you need to perform, as per the Single Responsibility Principle:

static void CommonOccurrence(int[] numbers)
{
 var dictionary = GroupByOccurrence(numbers);
 var mostCommonNumber = KeyOfLargestValue(dictionary);
 var occurrences = dictionary[mostCommonNumber];
 Console.WriteLine("The most common number is {0} and it appears {1} times", mostCommonNumber, occurrences);
}
static Dictionary<int, int> GroupByOccurrence(int[] numbers)
{
 var result = new Dictionary<int, int>();
 foreach (int i in numbers)
 {
 if (!result.ContainsKey(i))
 {
 result[i] = 0;
 }
 result[i]++;
 }
 return result;
}
static int KeyOfLargestValue(Dictionary<int, int> dictionary)
{
 int result = dictionary.Keys.First();
 foreach (var entry in dictionary)
 {
 if (entry.Value > dictionary[result])
 {
 result = entry.Key;
 }
 }
 return result;
}

• Aaron: Thanks, but I was told not to depend on libraries like Linq for interviews
• Gallant: It depends on the interviewer, I suppose. I always ask if I can use certain libraries, and a lot of the times they will be interested/impressed in seeing it solved both ways. See my updated answer on a manual implementation.
• JounceCracklePop: LINQ is a core part of C# and probably about 50% of the code I write. I'd be ecstatic if an interviewee came up with Gallant's solution. Not allowing LINQ is as silly as not allowing a Dictionary or HashSet; at that point, you're not writing C#, you're doing Sudoku.

Answer 3

This is on top of the points by @Dennis_E.

Single responsibility principle

CommomOcurrence is poorly named (+ has a typo too), but most importantly, it doesn't follow the single responsibility principle. It does too much:

• Builds a map of counts
• Prints the map of counts
• Prints the most frequent item with its count

Multiple smaller methods, each with a single clear responsibility would score you extra points at interviews. Such methods are easier to understand, and easier to unit test too. Also easier to give a good name.

Naming

As mentioned earlier, CommomOcurrence is poorly named. So are the names occurences and tempOccurences. It would be better to rename these:

• occurences -> maxOccurrences
• tempOccurences -> occurences

Algorithm

Your algorithm using a map of counts is fine. But, if the goal is to find the element that occurs the most, then you can do a bit better: once you found an element that occurs more times then the number of remaining elements, you can stop searching. If you want to know the number of occurrences, then you can scan the remaining elements to find the final count, but no need to count the other elements at that point.