FastPrep
Problem · Union Find

Earliest Time All Users Are Connected

Learn this problem
● MediumUberFULLTIMEPHONE SCREEN
See Uber hiring insights

Problem statement

You are given a list of users and a list of ride-share log entries. Each log entry records a timestamp and two users who shared a ride. Once two users share a ride, they are considered connected. Connectivity is transitive: if A is connected to B and B is connected to C, then A is connected to C.

Each log entry is formatted as "timestamp userA userB", where timestamp is an integer. Process the logs in increasing timestamp order and return the earliest timestamp when all users are connected. If the users never all become connected, return -1.

Function

earliestFullConnection(users: String[], logs: String[]) → int

Complete the function earliestFullConnection in the editor.

earliestFullConnection has the following parameters:

  1. String users[]: all users in the system
  2. String logs[]: ride-share connection logs

Returns

int: the earliest timestamp when all users are connected, or -1 if this never happens

Examples

Example 1

users = ["A", "B", "C"]logs = ["1 A B", "3 B C"]return = 3
At timestamp 1, A and B are connected. At timestamp 3, C joins that component through B, so all users are connected.

Example 2

users = ["A", "B", "C", "D"]logs = ["5 A B", "1 C D", "10 B C"]return = 10
The logs are processed by timestamp: C-D at 1, A-B at 5, then B-C at 10 connects the two components.

Example 3

users = ["A", "B", "C"]logs = ["2 A B"]return = -1
User C never connects to the A-B component.

Constraints

  • Each log entry has the format "timestamp userA userB".
  • Logs may be provided out of timestamp order.
  • User names in logs are included in users.

More Uber problems

drafts saved locally
public int earliestFullConnection(String[] users, String[] logs) {
  // write your code here
}
users["A", "B", "C"]
logs["1 A B", "3 B C"]
expected3
checking account