CODING CHALLENGE · N°15

Trim History to a Token Budget

Easy AI EngineeringAgentsContext

Every agent turn re-sends the whole conversation, so the history has to fit the context budget. The standard move: keep the most recent messages that fit and drop the oldest. Implement the trimmer at the heart of context management.

The problem

Implement trim_history(counts, budget). counts is a list of the token counts of the messages in a conversation, oldest first. Keep as many of the most recent messages as fit within budget tokens (walking from the end, stopping at the first message that would push the total over budget), and return their counts in original order.

EXAMPLE 1
Input counts=[5, 5, 5, 5], budget=12
Output [5, 5]
the two most recent fit (10); a third would be 15 > 12
EXAMPLE 2
Input counts=[10, 1, 1, 1], budget=3
Output [1, 1, 1]
the big old message is dropped
EXAMPLE 3
Input counts=[100], budget=50
Output []
a single message over budget can't be kept
CONSTRAINTS
  • Keep the most recent messages — walk from the end and stop at the first that would exceed the budget.
  • Return the kept counts in their original (oldest-first) order.
  • The kept messages form a contiguous suffix of the input.
SOLVE IT YOURSELF

Your turn — write it

Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are right above and Reveal solution is one click away.

YOUR TASK

Implement trim_history(counts, budget) — keep the most recent messages that fit the token budget, drop the oldest, and return the kept counts oldest-first.

HINTS — 3 IDEAS
  1. Iterate the list in reverse (newest first), accumulating a running total.
  2. Stop as soon as adding the next message would exceed the budget.
  3. Collect the kept counts, then restore their original order before returning.
CPython · WebAssembly
Approach, complexity & discussion — open after you solve

The approach

Trim a conversation to fit a token budget while keeping the essentials. Always keep the system message, then keep the most recent turns that fit, dropping (or summarizing) the oldest until you are under budget. Count tokens, not messages, and trim at message boundaries.

Complexity

Time O(n) over the messages.

Common mistakes

  • Dropping the system message when the history gets long — it must always survive.
  • Trimming by message count instead of token count, so you blow the budget on a few long messages.
  • Cutting in the middle of a message rather than at a clean boundary.

Where this shows up

Token-budget trimming is core context engineering: every long-running agent must compact its history to stay under the context window without losing the system prompt or recent state. The “keep system plus the most recent turns that fit” rule is the baseline every chat and agent loop needs.

Finished this one? 0 / 75 Challenges done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Challenges