Uber·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say

May 2026

Summary

Uber SWE coding round, one problem the whole time. It's basically LeetCode 1101 but with string timestamps and rider names instead of integers, so don't let the wrapper fool you into thinking it's something new.

Questions Asked (1)

Given a list of timestamped ride logs where each entry connects two riders, find the earliest timestamp at which all riders form a single connected component. Return "-1" if they never fully connect. Timestamps and rider names are strings. The logs are sorted in increasing timestamp order.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

Recognized it as a union-find problem pretty fast, which felt good.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as dynamic connectivity: process logs in timestamp order, union the two riders, and track the number of connected components. When the component count drops to 1, return the current timestamp; if the logs end without full connectivity, return '-1'.

Pro tip: Mention that you can optimize by precomputing the total number of unique riders and using a union-find with path compression and union by rank; also note that if the number of unique riders is 1, the answer is the first timestamp (or '0' if no logs).

1. Clarify and Define

Confirm that 'all riders' means all unique riders appearing in the logs, and that connectivity is undirected. Discuss edge cases: no logs, single rider, disconnected groups.

2. Choose Data Structure

Select Union-Find (Disjoint Set Union) with path compression and union by rank for near-constant time operations. Alternatively, consider BFS/DFS if logs are not streaming, but DSU is optimal for incremental connectivity.

3. Process Logs Sequentially

Iterate through logs in order. For each log, union the two riders. Maintain a count of connected components, initially equal to the number of unique riders. Decrement the count when a union merges two different components.

4. Check for Full Connectivity

After each union, if the component count becomes 1, return the current timestamp. If the loop finishes without reaching 1, return '-1'.

5. Analyze Complexity and Trade-offs

State time complexity O(N α(N)) where N is number of logs, and space O(R) for R riders. Discuss trade-offs: DSU is efficient but requires mapping rider names to indices; alternative approaches like graph traversal would be O(N * R) if repeated.

Key Points to Mention

Union-Find (Disjoint Set Union) with path compression and union by rank for efficient dynamic connectivity.
Tracking the number of connected components to detect when all riders are connected.
Handling string rider names by mapping them to integer indices for DSU.
Edge cases: no logs, single rider, riders never fully connect.
Time complexity: O(N α(N)) where N is number of logs; space O(R) for R riders.
Alternative approaches (e.g., BFS/DFS) and why DSU is preferred for incremental connectivity.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.