Hackerrank - value of friendship (II)

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

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

Sample Input 0

1

5 4

1 2`

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

public int Links;
public Stack 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 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 destination = groups[bigGroupId].Nodes;
Stack 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  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 destination = groups[bigGroupId].Nodes;
    Stack 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 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
{
    public override int Compare(Group x, Group y)
    {
        return (y.Nodes.Count - x.Nodes.Count);
    }
}

Can become:

public class GroupComparer : Comparer
{
    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

StackExchange Code Review Q#153253, answer score: 3