Cisco
Online AssessmentRide-Share Surge Pricing Replay
A ride-share company is replaying a stream of pricing logs to detect anomalies in fares. Each ride log contains a request with timestamp t (in seconds since a fixed reference epoch) and a fare f.
The fairness team wants to know: for every ride in the log, was its fare strictly above the 90th percentile of fares in the past 5 minutes (300 seconds)?
Concretely, ride i is flagged as surge-anomalous if its fare f_i is strictly greater than the 90th percentile of fares in its window (t_i - 300, t_i].
The 90th percentile is computed using the nearest-rank convention: in a window of size n, the 90th percentile fare is the fare at the ceil(0.9 * n)-th position (1-indexed) after sorting all fares in the window in ascending order. The current ride itself counts toward the window (so n >= 1).
Notice that whenever a window has fewer than 10 rides (n < 10), ceil(0.9 * n) = n, which corresponds to the window's maximum fare. Since no element can be strictly greater than the maximum, a window of size < 10 can never flag (output is 0).
Output, for each ride in chronological order, 1 if it is surge-anomalous, 0 otherwise.
- ▸Line 1: Integer N (number of rides).
- ▸Lines 2..N+1: Two space-separated integers t_i and f_i (timestamp and fare) in non-decreasing order of timestamp.
- ▸Print N lines, each containing 1 if the corresponding ride is surge-anomalous, or 0 otherwise.
- 1 <= N <= 2 * 10^5
- 0 <= t_i <= 10^9
- 1 <= f_i <= 10^9
- Timestamps are non-decreasing.
6 0 1000 60 1200 120 5000 240 1100 360 6000 420 1300
0 0 0 0 0 0
At each ride, the 300-second window contains fewer than 10 rides (window size <= 6). By the nearest-rank convention, the 90th percentile is the maximum fare in the window. No ride can strictly exceed the maximum, so all outputs are 0.
1. Maintain active window rides with timestamp > t_i - 300 using a sliding window left pointer. 2. Maintain active fares in a dynamic Order Statistic Tree (PBDS `tree` in C++, or a coordinate-compressed Fenwick tree). 3. When inserting (fare, unique_id) into the ordered set, window size is n. 4. If n < 10, output 0. 5. If n >= 10, rank k = ceil(0.9 * n) = (9 * n + 9) / 10. Find the k-th smallest fare using `find_by_order(k - 1)`. If f_i > p90, output 1; else 0. 6. Remove expired rides older than t_i - 300 from the order statistic tree. 7. Time Complexity: O(N log N), Space Complexity: O(N).