How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Google.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Google during technical interviews.

Find Earliest Fully Connected Time | Google Coding Question

Find Earliest Fully Connected Time

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given `n` people labeled `0` to `n - 1` and a list of friendship logs. Each log has the form `(timestamp, personA, personB, action)`, where `action` is either `"friend"` or `"unfriend"`. Friendship is undirected. Process the logs in chronological order. After each event, consider the current friendship graph. Return the earliest timestamp at which all `n` people belong to a single connected component. If that never happens, return `-1`. Notes: - Logs may not be sorted. - If multiple logs have the same timestamp, process them in input order. - Because edges can be both added and removed, the problem requires handling dynamic connectivity rather than only incremental unions.

Quick Answer: This question evaluates a candidate's understanding of dynamic graph connectivity, time-ordered event processing, and state maintenance in graphs, including handling both edge insertions and deletions.

You are given `n` people labeled from `0` to `n - 1` and a list of friendship logs. Each log is a tuple `(timestamp, action, u, v)` where `action` is either `'FRIEND'` or `'UNFRIEND'`. A `'FRIEND'` log means an undirected friendship edge between `u` and `v` becomes active. An `'UNFRIEND'` log means that edge is removed. After each log is applied, consider the current friendship graph. Return the earliest timestamp at which the graph becomes fully connected, meaning every person can reach every other person through some chain of friendships. If this never happens, return `-1`. Special case: if `n <= 1`, return `0` because a single person is already connected. The input logs may be unsorted. Process them in increasing timestamp order. If multiple logs have the same timestamp, process them in their original input order.

Constraints

1 <= n <= 2 * 10^5
0 <= len(logs) <= 2 * 10^5
Each log is `(timestamp, action, u, v)` where `action` is `'FRIEND'` or `'UNFRIEND'`
0 <= u, v < n and u != v
Logs are valid: a `'FRIEND'` event only appears when that pair is currently not friends, and an `'UNFRIEND'` event only appears when that pair is currently friends

Examples

Input: (4, [(3, 'FRIEND', 1, 2), (1, 'FRIEND', 0, 1), (2, 'FRIEND', 2, 3), (4, 'FRIEND', 0, 3)])

Expected Output: 3

Explanation: After sorting by time, the edges are added as 0-1, 2-3, then 1-2. At timestamp 3, all 4 people become connected for the first time.

Input: (4, [(1, 'FRIEND', 0, 1), (2, 'FRIEND', 2, 3), (3, 'FRIEND', 1, 2), (4, 'UNFRIEND', 1, 2), (5, 'FRIEND', 0, 2)])

Expected Output: 3

Explanation: The graph is fully connected at timestamp 3. It later becomes disconnected at 4, but the earliest connected time is still 3.

Input: (3, [(5, 'FRIEND', 0, 1), (6, 'UNFRIEND', 0, 1)])

Expected Output: -1

Explanation: Person 2 is never connected to the others, so the graph is never fully connected.

Input: (1, [])

Expected Output: 0

Explanation: With only one person, the graph is trivially connected from the start.

Input: (3, [])

Expected Output: -1

Explanation: There are no friendship events, so more than one person can never become connected.

Input: (3, [(1, 'FRIEND', 0, 1), (2, 'UNFRIEND', 0, 1), (3, 'FRIEND', 1, 2), (4, 'FRIEND', 0, 1)])

Expected Output: 4

Explanation: The friendship 0-1 is removed and later added again. Only at timestamp 4 do all three people become connected.

Hints

Think of each friendship edge as being active over a whole interval of event indices, not just at one moment.
A segment tree over time plus a Union-Find that supports rollback lets you handle edge deletions efficiently.

Quick Overview

This question evaluates a candidate's understanding of dynamic graph connectivity, time-ordered event processing, and state maintenance in graphs, including handling both edge insertions and deletions.