Friendship Time - Compute Overlapping Online Windows

Question

## Problem

A social platform logs each user's online sessions as `(user_id, start_time, end_time)`. Two users are "co-online" during any time window where both are simultaneously active.

Given a list of sessions and two user IDs `u` and `v`, return the total number of minutes they were co-online.

```python
def friendship_time(
    sessions: list[tuple[str, int, int]],
    u: str,
    v: str
) -> int:
```

## Example

```
sessions = [
  ("alice", 1, 5),
  ("alice", 8, 12),
  ("bob",   3, 10),
]
friendship_time(sessions, "alice", "bob")
# alice [1,5) and bob [3,10) overlap [3,5) = 2 min
# alice [8,12) and bob [3,10) overlap [8,10) = 2 min
# total = 4
Output: 4
```

## Follow-ups

1. How would you compute co-online time for all pairs efficiently (not just a given pair)?
2. What if a user can have overlapping sessions themselves -- how do you merge them first?
3. Extend to return the longest single contiguous co-online window, not just the total.
4. How does complexity change if the number of users is large (e.g., 100K users, 10M sessions)?

Friendship Time - Compute Overlapping Online Windows

Question Details

Full Details

Topics

More from Google