11 Apr 2018
Problem Description
- There is a social network of n members and a log file containing m timestamps at which times pairs of members formed friendships.
- Determine the earliest time at which all members are connected.
- Assume the log file is sorted by timestamp and that friendship is an equivalence relation.
- Running time should be mlogn or better and use extra space proportional to n.
Personal Thoughts
- Model n members as n nodes in the union-find problem.
- m timestamps indicate that there are m connected links in the model. Here we assume that the log file not only contains the timestamp, but also the pair of nodes connected. The format of logs file looks like this: 1522814473 101 100 (timestamp friend_A_notation friend_B_notation).
- Then, we can use the weighted quick union as our helper class. The union method in the class takes O(log n) time and the find method also takes O(log n) time.
- We use an array to store the n nodes and each node store the its own corresponding index. The condition for all the nodes to be connected is that there is only one node left storing its own corresponding index. Hence, we may use a counter which is initialized to the length of the array.
- We can iterate through each line of log file and conduct find() method on each pair to see whether this pair is already connected. If true, we continue the looping, else, we conduct union() on that pair and decrement the counter we initialized previously by 1.
- When the counter is decreased to 1 during the iteration, that particular line of input will contains the earliest timestamp when all friends are connected.