You’re building the typeahead search bar for a large e-commerce marketplace (millions of DAUs). Every keystroke can trigger a backend suggestion request, but sending a request per keypress increases cost and hurts P99 latency. To protect the system, the frontend uses debouncing: only fire a request after the user has stopped typing for delay_ms.
Given a chronological stream of input events, simulate a debouncer and return the list of requests that would actually be sent.
Implement debounce_requests(events, delay_ms).
(t_ms, text):
t_ms is an integer timestamp in milliseconds (non-decreasing order).text is the full current input value after that keystroke.t_ms + delay_ms with that event’s text.Return a list of fired requests as tuples (fire_time_ms, text) in chronological order.
Input:
events = [(0, "h"), (50, "he"), (120, "hel"), (400, "hell")]delay_ms = 200Output:
[(320, "hel"), (600, "hell")]Explanation:
"hel".Input:
events = [(0, "a"), (200, "ab")]delay_ms = 200Output:
[(200, "a"), (400, "ab")]Explanation: The second event arrives exactly at 200ms, so the first request has already fired at 200ms (it is not canceled).
0 <= len(events) <= 2 * 10^50 <= t_ms <= 10^9, timestamps are non-decreasing0 <= delay_ms <= 10^9text length <= 200 and contains printable ASCII< scheduled_time.