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
Coding & Algorithms
Software Engineer
Cursor
May 21, 2025
Software Engineer
Onsite - Coding
Coding & Algorithms
Medium

10

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
Priority queues and heaps
Request scheduling algorithms
Starvation prevention
Concurrent data structures
Resource management
How to Approach This
  1. Clarify input constraints and edge cases before writing code.
  2. Walk through your approach verbally and confirm with the interviewer before coding.
  3. Start with a brute force solution, then optimize. Mention time and space complexity.
  4. Test your solution with examples, including edge cases like empty input or duplicates.
  5. 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 Problems
Sample 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
Markdown supported

Related Questions