Hackerrank - value of friendship (II)

Question

Problem statement

You're researching friendships between groups \$n\$ of new college students where each student is distinctly numbered from \$1\$ to \$n\$. At the beginning of the semester, no student knew any other student; instead, they met and formed individual friendships as the semester went on. The friendships between students are:

• Bidirectional

  If student \$a\$ is friends with student \$b\$, then student \$b\$ is also friends with student \$a\$.

• Transitive

  If student \$a\$ is friends with student \$b\$ and student \$b\$ is friends with student \$c\$ , then student \$a\$ is friends with student \$c\$. In other words, two students are considered to be friends even if they are only indirectly linked through a network of mutual (i.e., directly connected) friends. The purpose of your research is to find the maximum total value of a group's friendships, denoted by \$total\$. Each time a direct friendship forms between two students, you sum the number of friends that each of the \$n\$ students has and add the sum to \$total\$.

You are given \$q\$ queries, where each query is in the form of an unordered list of \$m\$ distinct direct friendships between \$n\$ students. For each query, find the maximum value of \$total\$ among all possible orderings of formed friendships and print it on a new line.

Input Format

The first line contains an integer, \$q\$, denoting the number of queries. The subsequent lines describe each query in the following format:

The first line contains two space-separated integers describing the respective values of \$n\$ (the number of students) and \$m\$ (the number of distinct direct friendships). Each of the \$m\$ subsequent lines contains two space-separated integers describing the respective values of \$x\$ and \$y\$ (where \$x<>y\$) describing a friendship between student \$x\$ and student \$y\$.

Constraints

1. 1 <= q <= 16

2. 1 <= n <= 100000

3. 1 <= m <= min(n(n-1)/2, 200000)

2. Output Format

For each query, print the maximum value of \$total\$ on a new line.

Sample Input 0

1

5 4

1 2

3 2

4 2

4 3

Sample Output 0

32

Explanation 0

The value of \$total\$ is maximal if the students form the m = 4 direct friendships in the following order:

1. Students \$1\$ and \$2\$ become friends:

   

We then sum the number of friends that each student has to get 1 + 1 + 0 + 0 + 0 = 2.

2. Students \$2\$ and \$4\$ become friends:

   

We then sum the number of friends that each student has to get 2 + 2 + 0 + 2 + 0 = 6.

3. Students 3 and 4 become friends:

   

We then sum the number of friends that each student has to get 3 + 3 + 3 + 3 + 0 = 12.

4. Students 3 and 2 become friends:

   

We then sum the number of friends that each student has to get 3 + 3 + 3 + 3 + 0 = 12.

When we add the sums from each step, we get total = 2 + 6 + 12 + 12 = 32. We then print 32 on a new line.

My introduction of algorithm

The algorithm is the hard one and also one of Hackerrank weekcode \$28\$ contest in January 2017, after the contest, I did post a question here. I am training myself, so I continued to study all other C# submissions on hackerrank, spent hours to rewrite a solution. Think about posting a second question on this algorithm, but I did not fully understand union find algorithm.

So, I read some union find questions on this site - my favorite one, studied a lecture note of union find, but then I came cross the tutorial on hackerearth - Disjoint set union, I felt more confident about my understanding with more examples with diagrams and clear discussion of various concern of disjoint set union as an algorithm, time complexity, ideas to improve the time complexity. So, I think that it is ready for review, because I can talk about one term weighted-union operation - and relate to the implementation in the following.

The algorithm I did code review is using the ideas in disjoint set union, for example, weighted-union operation (see the above hackerearth's tutorial link). It will balance the tree formed by performing the operations - the subset containing less number of elements will join the bigger subset. The class \$Graph\$ method \$MergeSmallGroupToLargeOne\$ is the example.

The code passes on test cases on Hackerrank. And also I learned a few things about the implementation, for example, apply constraints in the design, declare array with maximum size of friendships - \$m\$.

Hightlights of changes

User meaningful variable names and class names; Extract some code to form a new class called GroupManagement; Define a new function MergeSmallGroupToLargeOne inside struct Group.

Please join me to review this C# solution.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
  /* 
   * January 19, 2016
   */
  public struct Group
  {
    public int Links;
    public Stack<int> Nodes;

    /*
     * Small group will join the bigger group. 
     */
    public static void MergeSmallGroupToLargeOne(
        Group[] groups,
        int smallGroupId,
        int bigGroupId,
        int[] nodeGroupId)
    {
        groups[bigGroupId].Links += groups[smallGroupId].Links + 1;

        Stack<int> destination = groups[bigGroupId].Nodes;
        Stack<int> source = groups[smallGroupId].Nodes;

        while (source.Count > 0)
        {
            int node = source.Pop();
            nodeGroupId[node] = bigGroupId;
            destination.Push(node);
        }
    }

    /*
     * Go over the calculation formula
     * 
     */
    public static ulong CalculateValue(Group[] sortedGroups)
    {
        ulong additionalLinks = 0;
        ulong totalValueOfFriendship = 0;
        ulong totalFriends = 0;

        // Each group is maximized in order... additionalLinks added at end
        foreach (Group group in sortedGroups)
        {
            ulong links = (ulong)(group.Nodes.Count - 1);

            ulong lookupValue = FriendshipValueCalculation.GetLookupTable()[links];
            totalValueOfFriendship += lookupValue + totalFriends * links;

            additionalLinks += (ulong)group.Links - links;

            totalFriends += links * (links + 1);
        }

        totalValueOfFriendship += additionalLinks * totalFriends;

        return totalValueOfFriendship;
    }

    /*
     * filter out empty group, check Group class member 
     * @groupCount - total groups, excluding merged groups
     * @groupIndex - total groups, including merged groups
     * 
     * check Nodes in the stack, if the stack is empty, then the group is empty. 
     */
    public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
    {
        Group[] nonEmptyGroups = new Group[groupCount];

        int index = 0;
        for (int i = 1; i <= groupIndex; i++)
        {
            if (groups[i].Nodes.Count > 0)
            {
                nonEmptyGroups[index++] = groups[i];
            }
        }

        return nonEmptyGroups;
    }
  }

  /*
   * Design talk: 
   * 1 <= n <= 100,000, n is the total students
   * 1 <= m <= 2 * 100,000, m is the total friendship
   * @groups - 
   * @groupIdMap - 
   */
  public class GroupManagement
  {
    public Group[] groups;
    public int[] groupIdMap;
    public int groupIndex = 0;
    public int groupCount = 0;

    public GroupManagement(int totalStudents)
    {
        groups = new Group[totalStudents / 2 + 1];   //
        groupIdMap = new int[totalStudents + 1];         // less than 2MB
        groupIndex = 0;
        groupCount = 0;
    }

    /*
       1) neither in a group:  create new group with 2 nodes
       2) only one in a group: add the other
       3) both already in same group - increase Links
       4) both already in different groups... join groups
     * 
     */
    public void AddFriendshipToGroups(int id1, int id2)
    {
        int groupId1 = groupIdMap[id1];
        int groupId2 = groupIdMap[id2];

        if (groupId1 == 0 || groupId2 == 0)
        {
            if (groupId1 == 0 && groupId2 == 0)
            {
                groupIndex++;
                groupCount++;

                groups[groupIndex].Links = 1;
                groups[groupIndex].Nodes = new Stack<int>();
                groups[groupIndex].Nodes.Push(id1);
                groups[groupIndex].Nodes.Push(id2);

                groupIdMap[id1] = groupIndex;
                groupIdMap[id2] = groupIndex;
            }
            else if (groupId1 == 0)
            {
                // add student1 into student2's group
                groups[groupId2].Nodes.Push(id1);
                groups[groupId2].Links++;

                groupIdMap[id1] = groupId2;
            }
            else
            {
                // add student2 into studnet1's group
                groups[groupId1].Nodes.Push(id2);
                groups[groupId1].Links++;
                groupIdMap[id2] = groupId1;
            }
        }
        else
        {
            if (groupId1 == groupId2)
            {
                groups[groupId1].Links++;
            }
            else   // merge two groups 
            {
                groupCount--;
                int groupSize1 = groups[groupId1].Nodes.Count;
                int groupSize2 = groups[groupId2].Nodes.Count;

                if (groupSize1 < groupSize2)
                {
                    // small, big, groupId, nodeGroupId
                    Group.MergeSmallGroupToLargeOne(groups, groupId1, groupId2, groupIdMap);
                }
                else
                {
                    Group.MergeSmallGroupToLargeOne(groups, groupId2, groupId1, groupIdMap);
                }
            }
        }
    }
  }

  /*
  * descending
  */
  public class GroupComparer : Comparer<Group>
  {
    public override int Compare(Group x, Group y)
    {
        return (y.Nodes.Count - x.Nodes.Count);
    }
  }

  /*
  * add some calculation description here. 
  */
  public class FriendshipValueCalculation
  {
    public static long FRIENDSHIPS_MAXIMUM = 200000;

    public static ulong[] GetLookupTable()
    {
        ulong[] friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM];  // 1.6 MB

        ulong valueOfFriendship = 0;

        for (int i = 1; i < FRIENDSHIPS_MAXIMUM; i++)
        {
            valueOfFriendship += (ulong)i * (ulong)(i + 1);
            friendshipsLookupTable[i] = valueOfFriendship;
        }

        return friendshipsLookupTable;
    }
  }

  static void Main(String[] args)
  {
    ProcessInput();
    //RunSampleTestcase();
    //RunSampleTestcase2(); 
  }

  public static void ProcessInput()
  {
    GroupComparer headComparer = new GroupComparer();

    int queries = Convert.ToInt32(Console.ReadLine());
    for (int query = 0; query < queries; query++)
    {
        string[] tokens_n = Console.ReadLine().Split(' ');
        int studentsCount = Convert.ToInt32(tokens_n[0]);
        int friendshipsCount = Convert.ToInt32(tokens_n[1]);

        GroupManagement groupManager = new GroupManagement(studentsCount);

        for (int i = 0; i < friendshipsCount; i++)
        {
            string[] relationship = Console.ReadLine().Split(' ');

            int id1 = Convert.ToInt32(relationship[0]);
            int id2 = Convert.ToInt32(relationship[1]);

            groupManager.AddFriendshipToGroups(id1, id2);
        }

        // Get all groups large to small
        Group[] sortedGroups =
            Group.GetNonemptyGroups(
                groupManager.groupCount,
                groupManager.groupIndex,
                groupManager.groups);

        Array.Sort(sortedGroups, headComparer);

        Console.WriteLine(Group.CalculateValue(sortedGroups));
    }
  }

  /*
  *
  * Need to work on the sample test case
  * 1. student 1 and 2 become friends
  *  1-2 3 4 5,  we then sum the number of friends that each student has
  * to get 1 + 1 + 0 + 0 + 0 = 2. 
  * 2. Student 2 and 3 become friends:
  *  1-2-3 4 5, we then sum the number of friends that each student has to get
  * 2 + 2 + 2 + 0 + 0 = 6. 
  * 3. Student 4 and 5 become friends:
  * 1-2-3 4-5, we then sum the number of friends that each student has to get 
  * 2 + 2 + 2 + 1 + 1 = 8. 
  * 4. Student 1 and 3 become friends: (we hold to add 1 and 3 until 4 and 5
  *    are added to maximize the value.)
  * 1-2-3 4-5, we then sum the number of friends that each student has to get
  * 2 + 2 + 2 + 1 + 1 = 8. 
  * Total is 2 + 6 + 8 + 8 = 24.   
  */
  public static void RunSampleTestcase()
  {
    string[][] datas = new string[1][];
    datas[0] = new string[2];
    datas[0][0] = "5";
    datas[0][1] = "4";

    string[][] allFriendships = new string[1][];
    allFriendships[0] = new string[4];

    allFriendships[0][0] = "1 2";
    allFriendships[0][1] = "2 3";
    allFriendships[0][2] = "1 3";
    allFriendships[0][3] = "4 5";        

    Console.WriteLine(HelpTestCase(datas, allFriendships));
  }

  public static void RunSampleTestcase2()
  {
    string[][] datas = new string[1][];
    datas[0] = new string[2];
    datas[0][0] = "5";
    datas[0][1] = "4";

    string[][] allFriendships = new string[1][];
    allFriendships[0] = new string[4];

    allFriendships[0][0] = "1 2";
    allFriendships[0][1] = "3 2";
    allFriendships[0][2] = "4 2";
    allFriendships[0][3] = "4 3";

    Console.WriteLine(HelpTestCase(datas, allFriendships));
  }

  private static ulong HelpTestCase(string[][] datas, string[][] allFriendships)
  {
    GroupComparer headComparer = new GroupComparer();

    int studentsCount = Convert.ToInt32(datas[0][0]);
    int friendshipsCount = Convert.ToInt32(datas[0][1]);

    GroupManagement groupManager = new GroupManagement(studentsCount);

    for (int i = 0; i < friendshipsCount; i++)
    {
        string[] relationship = allFriendships[0][i].Split(' ');

        int id1 = Convert.ToInt32(relationship[0]);
        int id2 = Convert.ToInt32(relationship[1]);

        groupManager.AddFriendshipToGroups(id1, id2);
    }

    // Get all groups large to small
    Group[] sortedGroups =
        Group.GetNonemptyGroups(
            groupManager.groupCount,
            groupManager.groupIndex,
            groupManager.groups);

    Array.Sort(sortedGroups, headComparer);

    return Group.CalculateValue(sortedGroups); 
  }
}

Answer 1

Almost everything looks good except for a few bits, so we'll go top-to-bottom:

public int Links;
public Stack<int> Nodes;

You should never expose public fields in C#, especially in a struct. These should always be properties:

public int Links { get; set; }
public Stack<int> Nodes { get; set; }

Of course, if possible they should be immutable, get; private set; if possible. In your case neither setter can be private, but for the future we try to be as restrictive as possible until we don't need to be.

Then you have another group:

public Group[] groups;
public int[] groupIdMap;
public int groupIndex = 0;
public int groupCount = 0;

First, C# public member naming rules indicate that PascalCase should always be used; second, we talked about the properties thing already; third, the value 0 is the default for int types. .NET languages have mandatory default constructors on struct objects that initialize all fields/properties to their default value, for any numeric type (int, long, float, ulong) that's 0, for bool it's false, etc.

public Group[] Groups { get; set; }
public int[] GroupIdMap { get; set; }
public int GroupIndex { get; set; }
public int GroupCount { get; set; }

So obviously that's pretty simple stuff, you may or may not have been aware of.

---

Next, we'll get into some of the actual code and talk about things that can make life easier and whatnot.

C# has implicit typing available through the use of the var keyword (similar to Variant in VB.NET or let in F#. Something like the following:

Stack<int> destination = groups[bigGroupId].Nodes;
Stack<int> source = groups[smallGroupId].Nodes;

Can be implicitly typed:

var destination = groups[bigGroupId].Nodes;
var source = groups[smallGroupId].Nodes;

Whether or not you want to actually use LINQ is up to you, but I'll give you a nice example that you can try to apply more generally:

public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
{
    Group[] nonEmptyGroups = new Group[groupCount];

    int index = 0;
    for (int i = 1; i <= groupIndex; i++)
    {
        if (groups[i].Nodes.Count > 0)
        {
            nonEmptyGroups[index++] = groups[i];
        }
    }

    return nonEmptyGroups;
}

With LINQ (System.Linq) this can be made one line:

public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
{
    return groups
        .Where(g => g.Nodes.Count > 0)
        .ToArray();
}

That keeps it really simple. (It'll probably be slightly slower, LINQ is usually slower than a hand-written loop, which is why I leave it up to you if you like it or not.)

You have this method:

public static void MergeSmallGroupToLargeOne(
    Group[] groups,
    int smallGroupId,
    int bigGroupId,
    int[] nodeGroupId)
{
    groups[bigGroupId].Links += groups[smallGroupId].Links + 1;

    Stack<int> destination = groups[bigGroupId].Nodes;
    Stack<int> source = groups[smallGroupId].Nodes;

    while (source.Count > 0)
    {
        int node = source.Pop();
        nodeGroupId[node] = bigGroupId;
        destination.Push(node);
    }
}

Which on first glance shouldn't work. It wasn't until I remembered that Stack<T> is a reference type that I realized why it works. I have no idea if there's anything that can be done about it, but it confused me heavily for a moment. Perhaps instead of using destination just call groups[bigGroupId].Nodes.Push instead.

---

If you have access to C#6.0 then some of these method calls can become a little simpler:

public class GroupComparer : Comparer<Group>
{
    public override int Compare(Group x, Group y)
    {
        return (y.Nodes.Count - x.Nodes.Count);
    }
}

Can become:

public class GroupComparer : Comparer<Group>
{
    public override int Compare(Group x, Group y) =>
        y.Nodes.Count - x.Nodes.Count;
}

---

Casting in C# is expensive almost always, and you should do it as little as possible.

public class FriendshipValueCalculation
{
    public static long FRIENDSHIPS_MAXIMUM = 200000;

    public static ulong[] GetLookupTable()
    {
        ulong[] friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM];  // 1.6 MB

        ulong valueOfFriendship = 0;

        for (int i = 1; i < FRIENDSHIPS_MAXIMUM; i++)
        {
            valueOfFriendship += (ulong)i * (ulong)(i + 1);
            friendshipsLookupTable[i] = valueOfFriendship;
        }

        return friendshipsLookupTable;
    }
}

First: that FRIENDSHIPS_MAXIMUM should be a const, it doesn't need to be a static const (const members cannot be static) but it should be a const. Right now anyone can reassign it.

It should also be a private member since it's not used outside your class.

As far as naming, usually C# avoids SHOUTY_SNAKE_CASE but personally I use that casing type so that when I am looking at a name I know immediately that it's a constant. Generally const members follow the same naming convention as normal: public and protected are PascalCase and private is camelCase.

We have three casts here (yes, I did say three). The first two are obvious, casting i to ulong. The third is an implicit cast from i to long in the condition i < FRIENDSHIPS_MAXIMUM. Yes, that is a cast.

What can we do to fix this? First, since i has to fit within the range of an index of an array (which is always an Int32), then we can just either change the type of FRIENDSHIPS_MAXIMUM to int, or create a local variable which is an int version of it.

Next, We want to eliminate that ulong cast we do twice, but how? There are two methods: create a new local variable that is a ulong and manage it in the loop, or create a cast of i one time in the loop.

var bigI = (ulong)i;

Then use bigI in the loop.

I'm going to use the first version since it should be faster.

public class FriendshipValueCalculation
{
    // Remove implicit cast from `int` to `long`, make it a `const` since it shouldn't ever change, make it `private` since no one else needs it
    private const int FRIENDSHIPS_MAXIMUM = 200000;

    public static ulong[] GetLookupTable()
    {
        const int startIndex = 1;
        var friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM];  // 1.6 MB

        var valueOfFriendship = 0ul;

        var valueIndex = (ulong)startIndex;
        for (var i = startIndex; i < FRIENDSHIPS_MAXIMUM; i++, valueIndex++)
        {
            valueOfFriendship += valueIndex * (valueIndex + 1);
            friendshipsLookupTable[i] = valueOfFriendship;
        }

        return friendshipsLookupTable;
    }
}

The ul suffix on the 1 tells C# that I want that 1 to be an unsigned long or ulong. (Similar to the f suffix indicating float.) This allows the implicit type engine to appropriately determine what type that var really is.

The i++, valueIndex++ tells the compiler to increment both of those variables each time the loop iterates.

---

Finally, this if block should be seriously refactored:

if (groupId1 == 0 || groupId2 == 0)
{
    if (groupId1 == 0 && groupId2 == 0)
    {
        groupIndex++;
        groupCount++;

        groups[groupIndex].Links = 1;
        groups[groupIndex].Nodes = new Stack<int>();
        groups[groupIndex].Nodes.Push(id1);
        groups[groupIndex].Nodes.Push(id2);

        groupIdMap[id1] = groupIndex;
        groupIdMap[id2] = groupIndex;
    }
    else if (groupId1 == 0)
    {
        // add student1 into student2's group
        groups[groupId2].Nodes.Push(id1);
        groups[groupId2].Links++;

        groupIdMap[id1] = groupId2;
    }
    else
    {
        // add student2 into studnet1's group
        groups[groupId1].Nodes.Push(id2);
        groups[groupId1].Links++;
        groupIdMap[id2] = groupId1;
    }
}
else
{
    if (groupId1 == groupId2)
    {
        groups[groupId1].Links++;
    }
    else   // merge two groups 
    {
        groupCount--;
        int groupSize1 = groups[groupId1].Nodes.Count;
        int groupSize2 = groups[groupId2].Nodes.Count;

        if (groupSize1 < groupSize2)
        {
            // small, big, groupId, nodeGroupId
            Group.MergeSmallGroupToLargeOne(groups, groupId1, groupId2, groupIdMap);
        }
        else
        {
            Group.MergeSmallGroupToLargeOne(groups, groupId2, groupId1, groupIdMap);
        }
    }
}

Arrow-code is never appreciated, and nothing in that block becomes more complex when it's refactored to one level:

if (groupId1 == 0 && groupId2 == 0)
{
    groupIndex++;
    groupCount++;

    groups[groupIndex].Links = 1;
    groups[groupIndex].Nodes = new Stack<int>();
    groups[groupIndex].Nodes.Push(id1);
    groups[groupIndex].Nodes.Push(id2);

    groupIdMap[id1] = groupIndex;
    groupIdMap[id2] = groupIndex;
}
else if (groupId1 == 0)
{
    // add student1 into student2's group
    groups[groupId2].Nodes.Push(id1);
    groups[groupId2].Links++;

    groupIdMap[id1] = groupId2;
}
else if (groupId2 == 0)
{
    // add student2 into studnet1's group
    groups[groupId1].Nodes.Push(id2);
    groups[groupId1].Links++;
    groupIdMap[id2] = groupId1;
}
else if (groupId1 == groupId2)
{
    groups[groupId1].Links++;
}
else   // merge two groups 
{
    groupCount--;
    int groupSize1 = groups[groupId1].Nodes.Count;
    int groupSize2 = groups[groupId2].Nodes.Count;

    if (groupSize1 < groupSize2)
    {
        // small, big, groupId, nodeGroupId
        Group.MergeSmallGroupToLargeOne(groups, groupId1, groupId2, groupIdMap);
    }
    else
    {
        Group.MergeSmallGroupToLargeOne(groups, groupId2, groupId1, groupIdMap);
    }
}

Then we see that these two cases:

else if (groupId1 == 0)
{
    // add student1 into student2's group
    groups[groupId2].Nodes.Push(id1);
    groups[groupId2].Links++;
    groupIdMap[id1] = groupId2;
}
else if (groupId2 == 0)
{
    // add student2 into studnet1's group
    groups[groupId1].Nodes.Push(id2);
    groups[groupId1].Links++;
    groupIdMap[id2] = groupId1;
}

Do the same thing just in opposite directions. Well, that's not hard to deal with:

if (groupId1 == 0 || groupId2 == 0)
{
    var groupId = groupId1 + groupId2; // One of them is 0, so if we add them we'll get the ID for the other
    var id = groupId1 == 0 ? id1 : id2; // This (`a ? b : c`) is the ternary operator, if `groupId1 == 0` then `id1` is returned, else `id2` is returned

    groups[groupId].Nodes.Push(id);
    groups[groupId].Links++;
    groupIdMap[id] = groupId;
}

Now we've compressed our code more, and it's still extremely obvious what's going on. Our final block is:

if (groupId1 == 0 && groupId2 == 0)
{
    groupIndex++;
    groupCount++;

    groups[groupIndex].Links = 1;
    groups[groupIndex].Nodes = new Stack<int>();
    groups[groupIndex].Nodes.Push(id1);
    groups[groupIndex].Nodes.Push(id2);

    groupIdMap[id1] = groupIndex;
    groupIdMap[id2] = groupIndex;
}
else if (groupId1 == 0 || groupId2 == 0)
{
    var groupId = groupId1 + groupId2; // One of them is 0, so if we add them we'll get the ID for the other
    var id = groupId1 == 0 ? id1 : id2; // This (`a ? b : c`) is the ternary operator, if `groupId1 == 0` then `id1` is returned, else `id2` is returned

    groups[groupId].Nodes.Push(id);
    groups[groupId].Links++;
    groupIdMap[id] = groupId;
}
else if (groupId1 == groupId2)
{
    groups[groupId1].Links++;
}
else   // merge two groups 
{
    groupCount--;
    int groupSize1 = groups[groupId1].Nodes.Count;
    int groupSize2 = groups[groupId2].Nodes.Count;

    if (groupSize1 < groupSize2)
    {
        // small, big, groupId, nodeGroupId
        Group.MergeSmallGroupToLargeOne(groups, groupId1, groupId2, groupIdMap);
    }
    else
    {
        Group.MergeSmallGroupToLargeOne(groups, groupId2, groupId1, groupIdMap);
    }
}

---

Overall: very solid code, excellent work and I'm glad to see another person experimenting with the language. :) Hopefully you learn more and more about it, and become another highly-qualified developer in C#.

Answer 2

I think to improve your code you need to improve the documentation about your code. This is how it is expected in clean code.

This function has so many responsibilities, which makes it hard to understand. So I don't see the quality in this snippet. It is necessary to spend too much time reading it to understand what this does.

public class FriendshipValueCalculation{

    public static long FRIENDSHIPS_MAXIMUM = 200000;

    public static ulong[] GetLookupTable()
    {
        ulong[] friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM];  // 1.6 MB

        ulong valueOfFriendship = 0;

        for (int i = 1; i < FRIENDSHIPS_MAXIMUM; i++)
        {
            valueOfFriendship += (ulong)i * (ulong)(i + 1);
            friendshipsLookupTable[i] = valueOfFriendship;
        }

        return friendshipsLookupTable;
    }
  }