Skip to content

Instantly share code, notes, and snippets.

@lucasklaassen
Last active April 17, 2020 01:07
Show Gist options
  • Save lucasklaassen/a6019cb9cf5d9fc8223c596811ae5762 to your computer and use it in GitHub Desktop.
Save lucasklaassen/a6019cb9cf5d9fc8223c596811ae5762 to your computer and use it in GitHub Desktop.
Algorithms 1 Social network connectivity
import java.util.EmptyStackException;
import java.util.HashMap;
class MemberLogItem {
public int timestamp = 0;
public int follower = 0;
public int followee = 0;
public MemberLogItem(int timestamp, int follower, int followee) {
this.timestamp = timestamp;
this.follower = follower;
this.followee = followee;
}
}
public class Percolation {
private int members[] = new int[]{ 1,2,3,4,5,6,7,8,9,10 };
private int numberOfRoots = members.length;
private MemberLogItem[] memberLogItems;
private HashMap<Integer, Integer> memberRelations = new HashMap<Integer, Integer>();
public void setMemberLogItems(MemberLogItem[] memberLogItems) {
this.memberLogItems = memberLogItems;
}
private int findRoot(int memberId) {
boolean foundRoot = false;
int rootId = memberId;
while(!foundRoot) {
int newId = memberRelations.get(rootId);
if(newId == memberRelations.get(newId)) {
foundRoot = true;
}
rootId = newId;
}
return rootId;
}
private void makeFriends(int follower, int followee) {
int followerRoot = findRoot(follower);
int followeeRoot = findRoot(followee);
if(followerRoot != followeeRoot) {
numberOfRoots--;
memberRelations.put(followerRoot, followeeRoot);
}
}
public int solve() {
for(int i = 0; i < memberLogItems.length; i++) {
MemberLogItem memberLogItem = memberLogItems[i];
Integer followerRelation = memberRelations.get(memberLogItem.follower);
if(followerRelation == null) {
memberRelations.put(memberLogItem.follower, memberLogItem.follower);
}
Integer followeeRelation = memberRelations.get(memberLogItem.followee);
if(followeeRelation == null) {
memberRelations.put(memberLogItem.followee, memberLogItem.followee);
}
makeFriends(memberLogItem.follower, memberLogItem.followee);
if(numberOfRoots == 1) {
return memberLogItem.timestamp;
}
}
// If this error gets thrown, no solutions were found.
throw new EmptyStackException();
}
}
public class TestRunner {
public static void main(String[] args) {
Percolation percolation = new Percolation();
final MemberLogItem[] memberLogItems = new MemberLogItem[12];
memberLogItems[0] = new MemberLogItem(1234, 1, 5);
memberLogItems[1] = new MemberLogItem(1235, 2, 3);
memberLogItems[2] = new MemberLogItem(1236, 1, 6);
memberLogItems[3] = new MemberLogItem(1237, 5, 7);
memberLogItems[4] = new MemberLogItem(1238, 9, 4);
memberLogItems[5] = new MemberLogItem(1239, 8, 2);
memberLogItems[6] = new MemberLogItem(1240, 10, 1);
memberLogItems[7] = new MemberLogItem(1241, 5, 3);
memberLogItems[8] = new MemberLogItem(1242, 3, 8);
memberLogItems[9] = new MemberLogItem(1243, 9, 1);
memberLogItems[10] = new MemberLogItem(1244, 9, 2);
memberLogItems[11] = new MemberLogItem(1245, 9, 3);
percolation.setMemberLogItems(memberLogItems);
System.out.println(percolation.solve());
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment