3
\$\begingroup\$

I got this test online last week. here is an example:

given this array:

{ 1 , 2 , 4 , 5 , 1 , 4 , 6 , 2 , 1 , 4 }

on condition that

index(x) < index (y)

find the number of possible pairs (x,y).

where x = y.

the answer would be:

count = 7 - (0,4), (0,8), (4,8), (1,7), (2,5), (2,9), (5,9)

Edit3: added picture to clarify the pairs are elements from the same array. the picture has the first 3 pairs.

enter image description here

the first solution I came up with which was obviously bad:

public static int solution(int[] A)
    {
        int count = 0;
        for (int i = 0; i < A.Length; i++)
        {
            for (int j = i + 1; j < A.Length; j++)
            {
                if (A[i] == A[j])
                    count++;
            }
        }
        return count;
    }

basically, just count the number of possible pairs in each loop.

then after a bit of struggle I managed to do this:

public static int solution(int[] A)
        {     
            int count = 0;
            var dict = new Dictionary<int, int>();
            for (int i = 0; i < A.Length; i++)
            {
                if (!dict.Any(x => x.Key == A[i]))
                    dict.Add(A[i], 1);
                else
                    dict[A[i]]++;
            }

            foreach (var item in dict)
            {
                count += Factorial(item.Value) / 2 * Factorial(item.Value - 2);
            }

            return count;
        }

1- count how many times the number is present.

2- calculate the possible pairs for each number which is given by this formula:

enter image description here

where n is the number of repetitions and r = 2 (pair, 2 items)

Factorial is just a simple implementation of the function.

I feel like there is a lot to improve on this. what do you think?

Edit: added the Factorial Function as requested:

public static int Factorial(int N)
        {
            return N == 0
                       ? 1
                       : Enumerable.Range(1, N).Aggregate((i, j) => i * j);
        }

Edit2: I tested both and got 20s for the first method and 500ms for the second improved method.

the 100000 was the limit set by the test details.

here is the code for the test:

int[] testArray = new int[100000];
Random x = new Random();
for (int i = 0; i < testArray.Length; i++)
{                
   testArray[i] = x.Next(1, 10);
}
Stopwatch sw = new Stopwatch();
sw.Start();
solution(testArray);
sw.Stop();

Edit4:

Well, it seems like I messed up!

calculating factorial for numbers bigger 19 in intger is not possible, out of range.

the worse is I didn't even have to calculate it.

in my formula since r is a constant I could simplify it to

n* (n -1) / 2

thus avoiding the entire thing.

\$\endgroup\$
4
  • \$\begingroup\$ It appears that your question is missing the Y array as stated by the condition index(x) < index (y). That indicates to me that the size of x has to be less than the size of y. Can you post a link to the test and/or check/edit your question? \$\endgroup\$
    – Alex Leo
    Aug 24 '20 at 6:59
  • \$\begingroup\$ the y is from the same array, also where could I post the code online? @AlexLeo \$\endgroup\$
    – Alaa Jabre
    Aug 24 '20 at 7:08
  • \$\begingroup\$ In other words Y = X+ 1 ? or Y is all the other elements with index greater than X? Add a link to the test in your question. \$\endgroup\$
    – Alex Leo
    Aug 24 '20 at 7:12
  • \$\begingroup\$ @AlexLeo I edited the question to add a clarification. \$\endgroup\$
    – Alaa Jabre
    Aug 24 '20 at 7:16
2
\$\begingroup\$

Based on the calculation of the number of pairs -your assertion is correct. The whole calculation method could be simplified by:

    public static List<KeyValuePair<int,int>> solution(int[] A)
    {

        //n(n-1)/2 number of pairs by a given set
        return  A.GroupBy(x => x).ToList().
            Select(y => new KeyValuePair<int, int>((y.Count() * (y.Count() - 1)) / 2, y.Key)).ToList();
    }
\$\endgroup\$
1
  • \$\begingroup\$ testing the performance, it seems like it did not suffer this was simple and fast just needed to sum the keys at the end since the method is required to return an integer so return A.GroupBy(x => x).ToList(). Sum(y => (y.Count() * (y.Count() - 1) / 2)); great answer, Thanks \$\endgroup\$
    – Alaa Jabre
    Aug 24 '20 at 10:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.