PracHub
QuestionsPremiumLearningGuidesInterview PrepNEWCoaches

Quick Overview

This question evaluates understanding of graph connectivity and temporal event processing, examining how pairwise interactions over time can merge components into a single connected set.

  • medium
  • Uber
  • Coding & Algorithms
  • Software Engineer

Find Earliest Full Connectivity Timestamp

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given: - A list of all user IDs in a ride-sharing system. - A chronological text log of ride-sharing events. Each relevant event contains a timestamp and two users, indicating that the two users shared a ride at that time. Two users are considered connected if they have directly shared a ride, or if they are connected through a chain of shared rides. For example, if user A shared with user B, and user B shared with user C, then A, B, and C are all connected. Return the earliest timestamp at which all users in the given user list become part of one connected component. If the users never all become connected, return an appropriate sentinel value such as `-1` or `null`. Example: ```text users = ["A", "B", "C", "D"] logs = [ "100 A B shared_ride", "120 C D shared_ride", "150 B C shared_ride" ] ``` Output: ```text 150 ``` Explanation: At timestamp `100`, A and B are connected. At timestamp `120`, C and D are connected. At timestamp `150`, the two groups are merged, so all users are connected for the first time. Follow-up questions: 1. What if the log contains multiple event types, and only some of them should create connections? 2. What if the log is not sorted by timestamp? 3. What is the time complexity of your approach? 4. How would your approach change if the log is very large and must be processed as a stream?

Quick Answer: This question evaluates understanding of graph connectivity and temporal event processing, examining how pairwise interactions over time can merge components into a single connected set.

Part 1: Earliest Timestamp of Full Connectivity

You are given a list of unique user IDs and a chronologically sorted list of ride logs. Each log has the form 'timestamp user_a user_b' and means those two users shared a ride at that time. Two users are connected if they have directly shared a ride or are linked through other users. Return the earliest timestamp when all listed users belong to one connected component. Return 0 if there are 0 or 1 users, and -1 if full connectivity never occurs.

Constraints

  • 0 <= len(users) <= 100000
  • All user IDs in users are unique
  • 0 <= len(logs) <= 200000
  • Each timestamp is a non-negative integer
  • Every log references users from the given users list

Examples

Input: (['A', 'B', 'C', 'D'], ['100 A B', '120 C D', '150 B C'])

Expected Output:

Explanation: The first two logs create two groups, and the third log merges them into one.

Input: (['A', 'B', 'C'], ['5 A B'])

Expected Output:

Explanation: User C never becomes connected to the others.

Input: (['A'], [])

Expected Output:

Explanation: A single user is already fully connected.

Input: (['A', 'B'], ['7 A B', '8 A B'])

Expected Output:

Explanation: The users become fully connected at the first log.

Hints

  1. A disjoint set union structure can merge groups efficiently as each log arrives.
  2. Track how many connected components remain so you can stop as soon as it becomes 1.

Part 2: Earliest Full Connectivity with Multiple Event Types

You are given a list of unique user IDs, a chronologically sorted list of system logs, and a list of event types that create connections. Each log has the form 'timestamp user_a user_b event_type'. Only logs whose event_type appears in connect_event_types should connect the two users. Return the earliest timestamp when all listed users belong to one connected component. Return 0 if there are 0 or 1 users, and -1 if full connectivity never occurs.

Constraints

  • 0 <= len(users) <= 100000
  • All user IDs in users are unique
  • 0 <= len(logs) <= 200000
  • Each event type is a single token with no spaces
  • Every log references users from the given users list

Examples

Input: (['A', 'B', 'C', 'D'], ['100 A B shared_ride', '110 A C message', '120 C D shared_ride', '150 B C shared_ride'], ['shared_ride'])

Expected Output:

Explanation: The message event is ignored, so all users connect only at timestamp 150.

Input: (['A', 'B', 'C'], ['5 A B follow', '7 B C shared_ride', '9 A C carpool_bonus'], ['shared_ride', 'carpool_bonus'])

Expected Output:

Explanation: The follow event is ignored. The shared_ride and carpool_bonus events fully connect the graph by 9.

Input: (['A', 'B'], ['10 A B message'], ['shared_ride'])

Expected Output:

Explanation: No allowed event type appears.

Input: ([], [], ['shared_ride'])

Expected Output:

Explanation: An empty user list is considered already fully connected.

Hints

  1. Convert the allowed event types to a set so membership checks are fast.
  2. Ignore logs with irrelevant event types and only union users for relevant ones.

Part 3: Earliest Full Connectivity from Unsorted Logs

You are given a list of unique user IDs and a list of ride logs that are not guaranteed to be sorted. Each log has the form 'timestamp user_a user_b'. Two users are connected if they have directly shared a ride or are linked through other users. Return the earliest timestamp when all listed users belong to one connected component. Return 0 if there are 0 or 1 users, and -1 if full connectivity never occurs.

Constraints

  • 0 <= len(users) <= 100000
  • All user IDs in users are unique
  • 0 <= len(logs) <= 200000
  • Each timestamp is a non-negative integer
  • Every log references users from the given users list

Examples

Input: (['A', 'B', 'C', 'D'], ['150 B C', '100 A B', '120 C D'])

Expected Output:

Explanation: Sorting by timestamp gives 100, 120, 150, and full connectivity first appears at 150.

Input: (['A', 'B', 'C'], ['20 A B', '10 B C'])

Expected Output:

Explanation: After sorting, B and C connect at 10, then A joins at 20.

Input: (['A', 'B', 'C'], ['5 B C', '5 A B'])

Expected Output:

Explanation: Both logs have the same timestamp, so the network becomes fully connected at time 5.

Input: (['A', 'B'], [])

Expected Output:

Explanation: With no logs, two users never become connected.

Hints

  1. If logs are not sorted, think about what must happen before a one-pass connectivity algorithm becomes valid.
  2. After sorting by timestamp, the same disjoint set union approach from the basic problem still works.

Part 4: Report the Complexity of the Connectivity Approach

You are asked to report the asymptotic complexity of the union-find approach for the earliest-connectivity problem. The inputs num_users and num_logs are provided only to define the symbols n and m. If logs_sorted is True, the algorithm processes logs directly with union-find. If logs_sorted is False, the algorithm must sort the logs first and then process them. Return the exact complexity labels for time and extra space.

Constraints

  • 0 <= num_users <= 10^18
  • 0 <= num_logs <= 10^18
  • logs_sorted is either True or False

Examples

Input: (4, 3, True)

Expected Output:

Explanation: Sorted logs need only the union-find pass.

Input: (4, 3, False)

Expected Output:

Explanation: Unsorted logs require sorting before union-find processing.

Input: (1, 0, True)

Expected Output:

Explanation: The reported formula depends on the algorithmic setup, not on the specific small values.

Input: (100000, 0, False)

Expected Output:

Explanation: If sorting is required in the plan, report the unsorted-log complexity form.

Hints

  1. Union-find handles each merge/find in amortized near-constant time, summarized as alpha(n).
  2. When logs are unsorted, sorting dominates the extra work and usually requires storing the logs.

Part 5: Earliest Full Connectivity in a Log Stream

You are given a list of unique user IDs and a very large stream of ride logs in nondecreasing timestamp order. Each log has the form 'timestamp user_a user_b'. You should conceptually process the logs one by one without sorting them or storing all past logs. Two users are connected if they have directly shared a ride or are linked through other users. Return the earliest timestamp when all listed users belong to one connected component. Return 0 if there are 0 or 1 users, and -1 if full connectivity never occurs.

Constraints

  • 0 <= len(users) <= 100000
  • The log stream can be much larger than memory, so the intended solution should not store all logs
  • Log timestamps are already in nondecreasing order
  • Every log references users from the given users list

Examples

Input: (['A', 'B', 'C', 'D'], ['100 A B', '120 C D', '150 B C'])

Expected Output:

Explanation: A single pass over the ordered stream is enough to detect the first moment of full connectivity.

Input: (['A', 'B', 'C'], ['1 A B', '2 A B', '3 B C', '4 A C'])

Expected Output:

Explanation: The duplicate connection at 2 changes nothing, and the graph becomes fully connected at 3.

Input: (['A', 'B', 'C'], ['1 A B'])

Expected Output:

Explanation: The stream ends before all users join one component.

Input: ([], [])

Expected Output:

Explanation: No users means the system is trivially fully connected.

Hints

  1. Because the stream is already time-ordered, you can update connectivity as each event arrives and stop immediately once one component remains.
  2. A disjoint set union structure lets you keep only component information instead of the full history.
Last updated: May 23, 2026

Loading coding console...

PracHub

Master your tech interviews with 7,500+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement stream queries and bounded-difference subarrays - Uber (medium)
  • Implement Minesweeper and Word Search - Uber (medium)
  • Implement Store Autocomplete - Uber (medium)
  • Simulate a Rank-Based Tournament - Uber (medium)
  • Implement Cache Eviction And Seat Assignment - Uber (medium)