Debounced Local Search Filter

MediumPython

Problem

A search bar at Acme Shop filters a local list of item names as the user types. To avoid recomputing on every keystroke, the search should be debounced: only process a query if no newer query arrives within debounce_ms milliseconds.

Write a function that takes a list of item names, a list of timestamped query updates, and a debounce interval. Return the filtered results for each query that actually executes after debouncing.

Formal Specification

Input:
- items: a list of strings
- events: a list of [timestamp, query] pairs sorted by non-decreasing timestamp
- debounce_ms: a non-negative integer
Output:
- A list of [run_timestamp, filtered_items] pairs, in execution order
A query matches an item if the query appears as a case-insensitive substring of the item.
If the query is an empty string, all items match.
An event executes at timestamp + debounce_ms only if no later event occurs at or before that execution time.

Constraints

1 <= len(items) <= 10^4
0 <= len(events) <= 10^4
0 <= debounce_ms <= 10^6
0 <= timestamp <= 10^9
events is sorted by non-decreasing timestamp
Each item and query is a string of length 0 to 100

Function Signature

def debounced_search(items, events, debounce_ms):

Write a function that takes a list of item names, a list of timestamped query updates, and a debounce interval. Return the filtered results for each query that actually executes after debouncing.

Formal Specification

Input:
- items: a list of strings
- events: a list of [timestamp, query] pairs sorted by non-decreasing timestamp
- debounce_ms: a non-negative integer
Output:
- A list of [run_timestamp, filtered_items] pairs, in execution order
A query matches an item if the query appears as a case-insensitive substring of the item.
If the query is an empty string, all items match.
An event executes at timestamp + debounce_ms only if no later event occurs at or before that execution time.