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:

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

Things that I have kept the same:

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:

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.

Nikita B · Accepted Answer · 2015-08-27 12:21:31Z

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);
    }  
}

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;
```
The naming convention for constants is CapitalCase.
You shouldn't use long if you have a 1≤A[i]≤106 restriction. Use byte instead.

Community · Accepted Answer · 2017-05-23 12:40:49Z

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;
}

I think DEFAULTCOUNT is supposed to be the initial value of dictionary entry. And you use it as increment step. Personally, I would just use value + 1. :) — Nikita B
– Nikita B, Commented Aug 27, 2015 at 12:56
@NikitaBrizhak I would do this also, but as the op provided a const which fit the need, I just used it ;-) — Heslacher
– Heslacher, Commented Aug 27, 2015 at 12:57

Stack Exchange Network

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

2 Answers 2

You must log in to answer this question.

Linked

Hot Network Questions

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

2 Answers 2

You must log in to answer this question.

Linked

Related

Hot Network Questions