Booking.com
Online AssessmentDinner Rush Demand Tracker
The live operations desk at OpenTable, a Booking Holdings company, watches a busy Friday evening unfold one event at a time. Every minute exactly one thing happens: either a diner makes a reservation at some restaurant, or a diner cancels a reservation at some restaurant. Every restaurant in the city is identified by a numeric code so the monitoring software can process the whole evening automatically.
The desk defines the demand pressure at any minute as the combined count of active reservations at the two restaurants currently holding the most active reservations at that exact moment. When only one restaurant currently has any active reservations, the pressure is that lone count by itself, and when no restaurant has any active reservations at all, the pressure is zero.
At the end of the evening, the desk wants one number, the total demand pressure, which is simply the sum of the demand pressure recorded right after each of the n minutes. You must write a function that replays the whole evening from the event log and reports this total demand pressure.
It is guaranteed that the log never asks to cancel a reservation at a restaurant whose current count of active reservations is zero.
Implement the function sumTopTwoStockPressure(int n, vector<vector<int>> actions), which returns a long long.
- ▸n: the number of minutes (events).
- ▸actions: n rows, one event per minute (the exact column layout was not visible in the OA screenshot; the example below assumes [type, restaurant], with type 1 = reserve and type 2 = cancel).
- ▸A single long long: the sum of the demand pressure recorded after each minute.
- A cancel never targets a restaurant with zero active reservations.
- Exact bounds on n and restaurant codes were not visible in the OA screenshot; plan for an O(n log n) solution.
n = 6 actions = [[1, 5], [1, 7], [1, 5], [2, 5], [1, 9], [2, 7]]
12
Illustrative example (input layout assumed; the OA's own sample was not visible).
Minute 1: {5:1} → 1. Minute 2: {5:1, 7:1} → 2. Minute 3: {5:2, 7:1} → 3.
Minute 4: {5:1, 7:1} → 2. Minute 5: {5:1, 7:1, 9:1} → 2. Minute 6: {5:1, 9:1} → 2.
Total = 1 + 2 + 3 + 2 + 2 + 2 = 12.
Keep a hash map from restaurant to its active count, and a multiset holding every positive count. On each event, erase the restaurant's old count from the multiset (if positive), update it, and insert the new count (if positive). The pressure is the sum of the largest one or two elements of the multiset; add it to a long long total.