Debounced Local Search Filter | Dataford Interview Questions

Your question is Debounced Local Search Filter. Start with the requirements on the right.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

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):