Problem Statement

Ride-Share Surge Pricing Replay The ride-share company is replaying a stream of pricing logs to detect anomalies. Each log entry is a ride request with a timestamp t (in seconds since a fixed reference epoch) and a fare f (in cents). The pricing-fairness team has a question: for every ride in the log, was its fare strictly greater than the 10% of fares charged within 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 — the current ride together with every earlier ride whose timestamp lies in (t_i - 300, t_i] (a half-open window ending at t_i , looking back 300 seconds). Rides are replayed in the order given, which is chronological; when several rides share a timestamp, their listed order is their order in time. The 90th percentile is computed using the nearest-rank convention: with n rides in the window, the 90th-percentile fare is the fare of the k -th ride after sorting