Implement a Context Window Token Budget Allocator
Last updated: May 21, 2025
Quick Overview
Given a fixed token budget and multiple ranked context sources (current file, imports, related files, conversation history), implement an algorithm that allocates tokens to maximize the relevance of the assembled context for code generation.
Cursor
May 21, 20258
4
1,687 solved
Given a fixed token budget and multiple ranked context sources (current file, imports, related files, conversation history), implement an algorithm that allocates tokens to maximize the relevance of the assembled context for code generation.
LLM context windows have a fixed size. Cursor must decide how much of each context source to include in the prompt. This is essentially a knapsack problem where items have both a size (tokens) and a value (relevance score). The interviewer expects an efficient solution that handles real-world constraints.
What the Interviewer Expects
- Model the problem as a variant of the knapsack problem
- Implement an efficient allocation algorithm that respects minimum guarantees per source
- Handle variable-size chunks from each source
- Support priority overrides for user-specified context
- Demonstrate the algorithm with concrete examples
Key Topics to Cover
How to Approach This
- Clarify input constraints and edge cases before writing code.
- Walk through your approach verbally and confirm with the interviewer before coding.
- Start with a brute force solution, then optimize. Mention time and space complexity.
- Test your solution with examples, including edge cases like empty input or duplicates.
- Consider common patterns: sliding window, two pointers, hash map, BFS/DFS, dynamic programming.
Possible Follow-up Questions
- How would you handle the case where the current file alone exceeds the budget?
- How would you adapt the allocation when switching between Tab completion and Chat?
- What is the time complexity and can it run in real-time?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Problem Analysis
This problem can be modeled as a variant of the knapsack problem where:
- Each context source is an item with a weight (the number of tokens it consumes) and a value (its relevance score).
- The total...
Approach
- Input Parsing: Start by parsing the input to get the token budget and the list of context sources, each with its token cost, relevance score, and minimum allocation (if any).
- **Initial Alloc...
Submit Your Answer
