Earliest Time a Friendship Log Connects Everyone, With Hop Limit and Unfriends

You are given a list of friendship log entries and the total number of users `n`. Each entry has the form ```text timestamp, userA connects to userB ``` meaning that from that timestamp on, the two users are directly connected. Find the earliest timestamp at which all users are connected to each other, directly or through a chain of connections. ### Constraints and Clarifications - Connections are undirected. - Assume timestamps are integers and that several entries may share a timestamp. The state at timestamp `T` is the network after every entry with a timestamp at most `T` has been applied. - User identifiers in the log are strings that must be mapped to the `n` users. ### Clarifying Questions - Is the log sorted by timestamp, or must it be sorted first? - What should be returned if the users never all become connected? - Can an entry connect two users who are already connected, or repeat an earlier entry? - Roughly how large are `n` and the log? That decides whether running graph searches at many timestamps is affordable in the follow-ups. ### Part 1 — Earliest time everyone is connected Return the earliest timestamp at which all `n` users form a single connected group. ```hint Count groups, not edges Think about a structure that tells you in near-constant time whether a new entry merges two separate groups. ``` #### What This Part Should Cover - A structure for incremental connectivity, and its amortized cost - Parsing and mapping user names, and processing entries in timestamp order - Ties in timestamps, the never-connected case, and `n = 1` ### Part 2 — Connected and within distance `k` Given an integer `k`, find the earliest timestamp from which all users are connected and every pair of users is at most `k` apart, where the distance between two users is the number of connections on the shortest chain between them. ```hint What only gets better Ask how the distance between two users can change as entries are added, and what that implies about the set of timestamps that satisfy the condition. ``` #### What This Part Should Cover - The monotonicity that makes "from this timestamp on" well defined - How the distance condition is checked, and what each check costs - How to avoid checking every timestamp, and the trade-off against maintaining distances incrementally ### Part 3 — Unfriend entries The log can now also contain entries of the form ```text timestamp, userB unfriends userC ``` which remove a direct connection. Find the timestamp at which all users are connected. ```hint What breaks Identify which operation the Part 1 structure cannot undo, and whether you must answer while the log streams in or can see the whole log first. ``` #### Clarifying Questions for this Part - Connectivity can now appear and disappear. Is the answer the first timestamp at which everyone is connected, or the timestamp from which everyone stays connected until the end of the log? - What does an unfriend between two users who are not directly connected mean: is it ignored, or is it an error? - If the same pair connects twice and then unfriends once, are they still connected? - Is the whole log available up front, or must each entry be handled as it arrives? #### What This Part Should Cover - Why the Part 1 structure no longer works, and what the naive fix costs - An efficient method for the chosen interpretation, offline or online - Complexity, and the policies for duplicate and invalid entries ### What a Strong Answer Covers - Clean parsing and an explicit definition of the network state at each timestamp - Union-find with near-constant amortized operations for Part 1 - A monotonicity argument for Part 2 and an honest cost analysis of the distance check - A clear statement of how deletions change the problem in Part 3, with a method that beats recomputing from scratch after every entry - Edge cases: ties, never connected, a single user, repeated or invalid entries ### Follow-up Questions - How would you report, for every unfriend entry, whether it split the network? - If the log streams in and Part 3 must be answered online, what changes? - How would you distribute the computation if the log were too large for one machine?