Fetch Every Page from a Data API, Then Compact Records to a Token Budget

This coding screen has two parts that build on each other: first collect all the data an API will return, then shrink the collected data to fit a token budget. ### Constraints and Clarifications - The API returns data in batches. You keep calling it, each call returning the next batch, until it returns no data. - Each record returned carries a token count, a non-negative integer. - If the fetched records total more than 20,000 tokens, they must be compacted to 10,000 tokens or fewer. If the total is 20,000 or fewer, they are kept unchanged. - The compaction was reported as a variant of a classic sliding-window problem. Assume the kept records must form one contiguous run of the fetched records, in their original order, and that the goal is to keep as many records as possible. ### Clarifying Questions - How does a call know which batch to return: does the API keep track of position, or do you pass back a cursor or offset from the previous response? Is an empty batch the only signal that the data has ended? - What should happen if a call fails or times out halfway through? - Is the target inclusive (at most 10,000 tokens) or strict (fewer than 10,000)? - If several runs of the same length fit the target, which one should be kept: the earliest, the most recent, or the one with the most tokens? - If one record alone exceeds 10,000 tokens, should it be dropped, truncated, or reported as an error? ### Part 1 — Fetch until the API returns no data The exact client interface is not reported. Assume it looks like this, and confirm it before coding: ```python def fetch_data(cursor: str | None) -> tuple[list[dict], str | None]: """Returns one batch of records, each a dict with at least a "tokens" field, plus the cursor to pass on the next call. The first call uses cursor=None. An empty list means there is no more data.""" ``` Write `fetch_all(fetch_data) -> list[dict]`, which keeps calling the API until it returns no data and returns every record in the order received. ```hint Pin down the end first Decide exactly which response ends the loop, then check that every other path through the loop either makes progress or stops. ``` #### What This Part Should Cover - A loop that passes the position along correctly and stops when no data comes back - Protection against an API that never returns an empty batch or repeats a cursor - Handling transient failures without losing or duplicating records - Collecting everything in memory versus streaming records to the next step ### Part 2 — Compact the records to a token budget Write `compact(records, trigger=20_000, target=10_000) -> list[dict]`. If the records' total tokens exceed `trigger`, return the longest contiguous run of records whose total is within `target`; otherwise return the records unchanged. For example, these token counts total 24,000, so compaction is required: ```text [4000, 3000, 5000, 2000, 1000, 6000, 3000] ``` No run of 4 records fits within 10,000 tokens. With an inclusive target, four runs of 3 records do: `[3000, 5000, 2000]`, `[5000, 2000, 1000]`, `[2000, 1000, 6000]` and `[1000, 6000, 3000]`. Which of them to return is one of the clarifying questions above. ```hint Reuse work between candidates Checking every run from scratch is quadratic or worse. Think about how a run's total changes when one of its ends moves by one record, and what non-negative token counts guarantee about that. ``` #### What This Part Should Cover - An algorithm faster than checking every run, why it is correct, and its complexity - The tie rule and the inclusive or strict boundary, applied consistently - Edge cases: a total exactly at the trigger, a record larger than the target, empty input - Why the trigger (20,000) and the target (10,000) differ ### What a Strong Answer Covers - Clarifies the API contract and the compaction rules early, before time is spent coding against the wrong reading - Working code for both parts, checked with a dry run on a small example - Correct time and space complexity - Reasoning about which records are worth keeping when data must be cut to a budget, and the alternatives to dropping them ### Follow-up Questions - Records keep arriving after the first fetch. How do you keep the collection within budget as records are appended, without recomputing from scratch each time? - Suppose the most recent record must always be kept. How does the algorithm change? - What if you should keep the run with the most tokens that still fits the target, rather than the most records? - Instead of dropping the records that do not fit, how could they be summarized, and what would that cost?