Batch Key Lookups Into One HTTP Request per 100 ms With Callbacks

You are writing client code for a single-threaded, callback-based runtime, similar to a JavaScript event loop. A remote service exposes one batch endpoint that returns the values of several keys at once: ```text GET /get?keys=key1,key2,... Response: {"key1": 123, "key2": "abs"} ``` The runtime provides two primitives: ```python http_get_request(url, callback) # sends a GET request; when the response arrives, calls callback(response: dict) set_timeout(callback, ms) # calls callback() once, ms milliseconds from now ``` Implement `start_fetch(key, callback)`. Callers ask for one key at a time. Your code must not send one HTTP request per call. Instead, it collects the requested keys and sends them to the endpoint as one batch request every 100 ms. When a batch response arrives, every callback that was waiting on a key in that batch must be called. ```python def start_fetch(key, callback): # TODO: implement this ... ``` For example, given this driver: ```python def main(): start_fetch("foo", cb1) # t = 0 ms start_fetch("bar", cb2) # t = 30 ms start_fetch("foo", cb3) # t = 70 ms start_fetch("foo", cb4) # t = 120 ms ``` `http_get_request` must be called exactly twice. The response to the first request leads to calls of `cb1`, `cb2` and `cb3`, and the response to the second request leads to the call of `cb4`. You may add global state and helper functions. Explain how you schedule the 100 ms flush, and how you store the keys waiting to be sent together with the callbacks waiting on each key. ```hint Count the timers Work out how many timers the example needs and which `start_fetch` call should create each one. The other calls must be able to tell that a timer is already waiting. ``` ```hint The first response can arrive late The first response may come back after `cb4` has already been queued for the next batch. Make sure the code that handles a response can reach only the callbacks of the batch it belongs to. ``` ### Constraints and Clarifications - Assume a single-threaded runtime: `start_fetch`, timer callbacks and response callbacks each run to completion, one at a time. - `set_timeout(callback, ms)` runs `callback` once, `ms` milliseconds after `set_timeout` is called. - A key can be requested several times before its batch is sent, and every waiting callback must be called. In the example, `cb1` and `cb3` both wait on `"foo"`. - A key requested after its batch has been sent belongs to a later batch, even if the earlier request has not been answered yet. That is why `cb4` causes a second request. - A response can arrive at any later time, including after later `start_fetch` calls or after the next batch has been sent. ### Clarifying Questions - Is the 100 ms window measured from the first key that enters an empty batch, or is it a fixed tick every 100 ms whether or not keys are waiting? - If a key is requested more than once in a window, should it appear only once in the URL? - Does the callback given to `start_fetch` receive only the value of its own key, or the whole response dict? - What should happen when the request fails or the response omits a requested key? - Can keys contain commas or other characters that must be URL-encoded? ### What a Strong Answer Covers - Scheduling that arms exactly one timer per batch and produces exactly two requests for the example - A data structure that ties each waiting key to every callback waiting on it, with a deliberate choice about duplicate keys in the URL - Isolation between a batch that has been sent and keys queued after it, including responses that arrive late or out of order - Each callback called exactly once with the right value, and defined behavior for failed requests and missing keys - Why the design is safe on a single-threaded event loop, and what would have to change on a multi-threaded runtime ### Follow-up Questions - The server accepts at most a fixed number of keys per request. How do you change the flush, and how do responses map back to callbacks? - `"foo"` is still in flight when `cb4` asks for it. When would you attach `cb4` to the in-flight request instead of sending a second one, and what does that cost? - A response never arrives. How do you add a timeout and a retry without ever calling a callback twice? - How would the implementation change if `start_fetch` could be called from several threads at once?