Calculate pairs in a Set (“Sherlock and Pairs” HackerRank challenge)

Question

Here is my second attempt at writing clean code for "Sherlock and Pairs" challenge. For my previous thread please look here: Calculate pairs in a Set ("Sherlock and Pairs" HackerRank challenge)

Problem statement:

Sherlock is given an array of N integers (A0,A1…AN−1) by Watson. Now Watson asks Sherlock how many different pairs of indices i and j exist such that i is not equal to j but Ai is equal to Aj.

That is, Sherlock has to count the total number of pairs of indices (i,j) where Ai=Aj AND i≠j.

Input Format

The first line contains T, the number of test cases. T test cases follow. Each test case consists of two lines; the first line contains an integer N, the size of array, while the next line contains N space separated integers.

Output Format

For each test case, print the required answer on a different line.

Constraints

1≤T≤10

1≤N≤105

1≤A[i]≤106

Things that I have changed in my code:

1. Removed dead code
2. Followed naming conventions. Camel case for all local variables.
3. Replaced class variables with parameters.

Things that I have kept the same:

1. Currently there are no messages being shown in the Console for the user. I have purposely kept it that way as on HackerRank while submitting the solution I cannot post any messages to the console.

Things that still need improvement:

1. I wanted to follow the single responsibility principle. However my CalculatePairsForAllTestCases function takes input from the user, splits it and then proceeds to the calculation. Can someone help me with how can I split that function further into Single responsibility functions?

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

namespace NoOfPairsInASet
{
    class Solution
    {
        static void Main()
        {
            int testCases = Convert.ToInt32(Console.ReadLine());
            CalculatePairsForAllTestCases(testCases);
        }

        private static void CalculatePairsForAllTestCases(int testCases)
        {
            for (int t = 0; t < testCases; t++)
            {
                int noOfElements = Convert.ToInt32(Console.ReadLine());
                string elements = Console.ReadLine();

                string[] arrayOfElements = elements.Split(' ');

                long[] data = arrayOfElements.Select(s => long.Parse(s)).ToArray();

                long totalPairs = CalculatePairs(data);
                Console.WriteLine(totalPairs);
            }
        }

        private static long CalculatePairs(long[] data)
        {

            Dictionary<long,long> countOfElements = GenerateDictionary(data);
            long sum = CalculateSum(countOfElements);
            return sum;
        }

        private static Dictionary<long, long> GenerateDictionary(long[] data)
        {
            Dictionary<long,long> countOfElements = new Dictionary<long, long>();
            const int DEFAULTCOUNT = 1;
            for (long i = 0; i < data.Length; i++)
            {
                if (countOfElements.ContainsKey(data[i]))
                {
                    IncrementCounter(data,countOfElements,i);
                }
                else
                {
                    countOfElements.Add(data[i], DEFAULTCOUNT);
                }
            }
            return countOfElements;
        }

        private static void IncrementCounter(long[] data,Dictionary<long, long> countOfElements, long i)
        {
            if (countOfElements != null) countOfElements[(data[i])]++;
        }

        private static long CalculateSum(Dictionary<long, long> countOfElements)
        {
            long sum = 0;
            if (countOfElements == null) return sum;
            sum = countOfElements.Where(item => item.Value > 1).Sum(item => CalculatePermutationOfValue(item.Value));
            return sum;
        }

        private static long CalculatePermutationOfValue(long n)
        {
            return n * (n - 1);
        }


    }
}

Please review the code and let me know how I could have written it better in terms of logic, coding practices or any other advice you might have.

Answer 1

1. To make the code flow more obvious and your code style more OOP-ish, instead of nesting methods in each other you should call them sequentially, so each method has single responsibility:

   static void Main()
   {
       int testCount = ReadTestCount();
       for (...)
       {
           //read array from console
           long[] array = ReadInputData();
           //do your math
           long result = CalculatePairsCount(array);
           //print result to console
           PrintOutput(result);
       }  
   }
   

2. I don't understand the use of dictionary if all your need to do is return the pair count. You dont actually need to return pairs themselves, right? Can't you just increment some value every time you find a pair then? Especially if that is one of those tasks, where they measure performance. I'm sorry if I am missing the point here. Edit: Ah, nevermind, I figured it out. But still, won't looping through collection be a lot faster than dictionary lookups, at least for small arrays?

       int sum = 0;
       for (int i = 0; i < data.Length; i++)
       {
           for (int j = i + 1; j < data.Length; j++)
           {
               if (data[i] == data[j])
               {
                   sum++;
               }
           }
       }
       return sum*2;
   

3. The naming convention for constants is CapitalCase.

4. You shouldn't use long if you have a 1≤A[i]≤106 restriction. Use byte instead.

Answer 2

private static Dictionary<long, long> GenerateDictionary(long[] data)
{
    Dictionary<long,long> countOfElements = new Dictionary<long, long>();
    const int DEFAULTCOUNT = 1;
    for (long i = 0; i < data.Length; i++)
    {
        if (countOfElements.ContainsKey(data[i]))
        {
            IncrementCounter(data,countOfElements,i);
        }
        else
        {
            countOfElements.Add(data[i], DEFAULTCOUNT);
        }
    }
    return countOfElements;
}  

If you are going to use a value of a Dictionary<TKey, TValue> you shouldn't use ContainsKey() but you should use TryGetValue().

This answer to what-is-more-efficient-dictionary-trygetvalue-or-containskeyitem states

ContainsKey uses the same check as TryGetValue, which internally refers to the actual entry location. The Item property actually has nearly identical code functionality as TryGetValue, except that it will throw an exception instead of returning false

So changing the above method to

private static Dictionary<long, long> GenerateDictionary(long[] data)
{
    Dictionary<long,long> countOfElements = new Dictionary<long, long>();
    const int DEFAULTCOUNT = 1;
    for (long i = 0; i < data.Length; i++)
    {
        long value;
        countOfElements.TryGetValue(data[i], out value);
        countOfElements[data[i]] = value + DEFAULTCOUNT;
    }
    return countOfElements;
}

also eleminates the IncrementCounter() method. But we can still do better, because we can just use a foreach loop like so

private static Dictionary<long, long> GenerateDictionary(long[] data)
{
    Dictionary<long,long> countOfElements = new Dictionary<long, long>();
    const int DEFAULTCOUNT = 1;
    foreach (var key in data)
    {
        long value;
        countOfElements.TryGetValue(key, out value);
        countOfElements[key] = value + DEFAULTCOUNT;
    }
    return countOfElements;
}