Algorithm · Google · Hard
Requirements Base problem Given N individuals and a time-ordered event log. Each record has the form (timestamp, person_a, person_b, action), where action ∈ {friend}. Find the first timestamp when all N individuals belong to the same connected group, meaning friendship may be established through intermediate people. Follow-up 1 (segment tree) Using the same event history, answer many timestamped questions of the form: "are X and Y connected at time t?". Follow-up 2 (fully…
Checking your access…