Booking.com

Online Assessment
Online Assessment//Support Escalation Triple Review Total
Q1
Hard

Support Escalation Triple Review Total

TreesBinary TreeLowest Common AncestorBinary Lifting
Set 1 • min
Problem Statement

Customer support at Booking.com is organised as a strict reporting tree. The head of support sits at the top, and every other team member reports to exactly one person directly above them, while each person has at most two direct reports. Every team member also has a team code, a number that the quality assurance team likes to record.

Occasionally, a quality review picks three support cases handled by three different team members at once, and wants to know the single person lowest in the hierarchy who still sits on the reporting chain above every one of the three, so that one reviewer can oversee all three cases together. A team member counts as being on their own reporting chain, so if one of the three is the manager of the others, that manager is the review point. This shared reviewer is the natural escalation point that all three cases could reach by following the reporting chain upward.

You are given the layout of the whole support organisation, the team code of every member, and a long list of review requests where each request names three team members. For every request, find the review point for those three members and add together the team codes found at every review point across every request into one grand total that the quality team can record.

Implement the function sumOfTripleMeetingBadges(int n, vector<vector<long long>> nodes, int q, vector<vector<long long>> queries), which returns a long long.

Input Format
  • ▸n: the number of team members.
  • ▸nodes: the organisation layout and team code of every member (the exact column layout was not visible in the OA screenshot; the example below assumes nodes[i] = [manager of i, team code of i], with manager = -1 for the head).
  • ▸q: the number of review requests.
  • ▸queries: q rows, each naming three team members [a, b, c].
Output Format
  • ▸A single long long: the sum of the team codes of the review point (lowest common manager) of every request.
Constraints
  • Each member has at most two direct reports (binary tree).
  • Exact bounds on n and q were not visible in the OA screenshot; q is described as a long list, so each request must be answered in about O(log n).
Sample Test Cases
Example 1
Input
n = 5
nodes = [[-1, 10], [0, 20], [0, 30], [1, 40], [1, 50]]
q = 2
queries = [[3, 4, 2], [3, 4, 1]]
Output
30
Explanation

Illustrative example (input layout assumed; the OA's own sample was not visible).

Member 0 is the head; 1 and 2 report to 0; 3 and 4 report to 1.

Request (3, 4, 2): LCA(3, 4) = 1, LCA(1, 2) = 0 → team code 10.

Request (3, 4, 1): LCA(3, 4) = 1, and 1 is on its own chain → team code 20.

Total = 10 + 20 = 30.

Complexity
TimeO((n + q) log n)
SpaceO(n log n)
Expected Approach

The review point of three members is their lowest common ancestor, and LCA(a, b, c) = LCA(LCA(a, b), c). Build depths and a binary-lifting table with one BFS from the head, answer each request with two LCA queries, and add the team code of the result to a long long total.