Autocomplete Request Debouncer Cache

HardPython

Problem

Implement an autocomplete request optimizer for a mobile search box. Given a list of timestamped query updates, return the timestamps and query strings that should trigger an API call. A call should only be sent if the user has stopped typing for debounce_ms, the query length is at least min_length, and the same query has not been sent within the last cache_ttl_ms.

Constraints

1 <= len(events) <= 10^5
0 <= timestamp <= 10^9
Timestamps are non-decreasing
0 <= len(query) <= 100
1 <= debounce_ms, cache_ttl_ms <= 10^9

Function Signature

def optimize_autocomplete(events, debounce_ms, min_length, cache_ttl_ms):

CodePython 3

You need to log in / sign up to run or submit.Ln 2

Run your code to see test output here.