Uber Coding Interview: Shared Ride Groups

The interviewer opens

Hi, and thanks for joining. Welcome to your interview for the software engineer role at Uber. We'll work through a coding problem together, and I'd like you to think out loud as you code. If you need to step out or take a break, you can pause the interview anytime with the Pause button at the top right.

The problem is about grouping riders who've shared rides, which is the kind of thing a ride-sharing platform cares about. It's up in the Problem tab on the right, so please read it through, take your time, and ask me any questions before you start.

The problem

Riders who shared a ride are linked, and links carry through other riders: if A rode with B and B rode with C, then A, B and C form one group.

• n: the number of riders, labelled 0 to n-1.
• logs: a list of [time, a, b], meaning riders a and b (a != b) shared a ride at time; sorted by time in non-decreasing order.
• t: a cutoff time.

Return the number of distinct rider groups formed by the rides with time <= t. A rider with no such ride is a group alone. Pairs may repeat or appear in either order.

Example: n = 5, logs = [[1,0,1],[2,1,2],[4,3,4]], t = 3 → 3

Sizes: 1 <= n <= 10^5, 0 <= len(logs) <= 10^5.