Implement a Priority Queue for LLM Request Scheduling
Last updated: May 21, 2025
Quick Overview
Build a priority queue that schedules LLM inference requests based on priority (user-interactive vs background), age, and estimated cost. Support priority boosting for aging requests and cancellation of stale requests.
Cursor
May 21, 202510
6
4,245 solved
Build a priority queue that schedules LLM inference requests based on priority (user-interactive vs background), age, and estimated cost. Support priority boosting for aging requests and cancellation of stale requests.
Cursor sends many concurrent LLM requests with different priorities. Tab completion is urgent and should preempt background indexing tasks. This question tests your ability to implement a scheduling data structure with real-world constraints.
What the Interviewer Expects
- Implement a multi-level priority queue with O(log n) insert and extract
- Support priority boosting for requests that have waited too long
- Implement cancellation of stale or superseded requests
- Handle fair scheduling between same-priority requests
- Discuss thread safety for concurrent access
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 priority inversion where a low-priority request blocks a high-priority one?
- How would you add rate limiting per priority level?
- How would you extend this to support request batching for GPU efficiency?
Sharpen Your Skills on Codemia
Practice similar problems with our interactive workspace, get AI feedback, and track your progress.
Practice DSA ProblemsSample Answer
Priority Queue Design
Use a binary min-heap where each element has a composite key: (priority_level, effective_timestamp). Priority levels: 0 (critical - user is waiting), ...
Priority Boosting and Cancellation
Every second, scan for requests older than a threshold (e.g., 5 seconds for priority 2, 10 seconds for priority 1) and boost their priority level by 1...
Submit Your Answer
