All-Pairs Connection Formation Time | Dataford Interview Questions

Aurora Innovation models communication among members of an autonomous vehicle engineering team as timestamped acquaintance events. Given n people and a list of direct connections, determine the earliest time at which every person is connected to every other person through a direct or indirect path.

A connection is undirected. Events may be provided in any order, and multiple events may have the same timestamp. All events with the same timestamp are considered available simultaneously.

Formal Specification

Implement earliest_full_connectivity(n, connections).

n is an integer representing people labeled 0 through n - 1.
connections is a list of [timestamp, person_a, person_b] records.
Return the earliest timestamp at which the graph is connected.
Return -1 if the graph never becomes fully connected.
A person is always considered connected to themself.

Constraints

1 <= n <= 2 * 10^5
0 <= len(connections) <= 2 * 10^5
0 <= timestamp <= 10^9
0 <= person_a, person_b < n
person_a != person_b
Duplicate connections may appear.
The input list is not necessarily sorted by timestamp.

Function Signature

def earliest_full_connectivity(n, connections):

Your question is All-Pairs Connection Formation Time. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem