Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Hackerrank - week of code 28 - value of friendship - integrate changes by code review: http://codereview.stackexchange.com/a/153504/123986, fix grammar errors in spelling.
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
/*
* January 19, 2016
* code review on stackexchange.com
* January 24, 2016
* code review: http://codereview.stackexchange.com/a/153504/123986
* and then, implement the changes according to the review.
*/
public struct Group
{
// code review: properties, never expose public fields in C#
// private set; if possible. If possible they should be immutable.
public int Links {get; set;}
public Stack<int> Nodes {get; set;}
/*
* 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;
// code review: C# has implicit typing available through the use of the var keyword
var destination = groups[bigGroupId].Nodes;
var 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 are 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.
*
* Obsolete the method, using LINQ one which is short.
*/
[Obsolete]
public static Group[] GetNonemptyGroups_Loop(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) the function can be made one line
* That keeps it really simple.
*
* Fix null pointer run time error by adding extra checking: g.Nodes != null
* g => g.Nodes != null && g.Nodes.Count > 0
*/
public static Group[] GetNonemptyGroups(int groupCount, int groupIndex, Group[] groups)
{
return groups
.Where(g => g.Nodes != null && g.Nodes.Count > 0)
.ToArray();
}
}
/*
* 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 memebers should use Pascal case.
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
*
* code review:
* Arrow-code is never appreciated, and nothing in that block becomes more complex when it's
* refactored to one level.
*/
public void AddFriendshipToGroups(int id1, int id2)
{
int groupId1 = GroupIdMap[id1];
int groupId2 = GroupIdMap[id2];
//
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)
{
// code review: one of them is 0, so just add them together.
var groupId = groupId1 + groupId2;
var id = groupId1 == 0 ? id1 : id2; // use ternary operator
// push id from groupId == 0 to another group
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);
}
}
}
}
/*
* descending
*/
public class GroupComparer : Comparer<Group>
{
// code review: try C# 6.0 version, compile error
/*
public override int Compare(Group x, Group y) =>
y.Nodes.Count - x.Nodes.Count;
*/
public override int Compare(Group x, Group y)
{
return (y.Nodes.Count - x.Nodes.Count);
}
}
/*
* add some calculation description here.
* code review:
* Casting in C# is expensive almost always, and you should do it as little as possible
*/
public class FriendshipValueCalculation
{
// code review: the variable should be a const, it doesn't need to be a static const.
// Otherwise any one can reassign it. long -> int
public const int FRIENDSHIPS_MAXIMUM = 200000;
public static ulong[] GetLookupTable()
{
// code review: ulong[] -> var
var friendshipsLookupTable = new ulong[FRIENDSHIPS_MAXIMUM]; // 1.6 MB
// code review: ulong -> var, 0 -> 0ul, ul suffix
var valueOfFriendship = 0ul;
// code review:
const int startIndex = 1;
var valueIndex = (ulong)startIndex;
// code review: The i++, valueIndex++ tells the compiler to increment both of those variables
// each time the loop iterates.
for (var i = 1; i < FRIENDSHIPS_MAXIMUM; i++, valueIndex++)
{
valueOfFriendship += valueIndex * (valueIndex + 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);
}
}
@jianminchen

This comment has been minimized.

Copy link
Owner Author

@jianminchen jianminchen commented Mar 2, 2017

March 1, 2017
line 120 - line 127
public class GroupManagement
{
// public memebers should use Pascal case.
public Group[] Groups;
public int[] GroupIdMap;
public int GroupIndex = 0;
public int GroupCount = 0;

Should be based on the code review:
public Group[] Groups {get; set}
public int[] GroupIdMap {get; set;}
public int GroupIndex {get; set;}
public int GroupCount {get; set;}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment