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
Problem Analysis
The problem requires the implementation of a multi-level priority queue to manage LLM requests based on their priority (user-interactive vs background), age, and estimated cost. This can be approached...
Approach
-
Data Structure: Use a binary heap to maintain the priority queue. Each request will be an object containing fields like
priority,age,cost, and a unique identifier. -
Insertion:...
Submit Your Answer
