Queue Management - Task Scheduler with Priority and Expiry

Question

## Problem

Design a task queue that supports priority scheduling and expiry. Each task has: `id`, `priority` (int, higher = more urgent), `enqueue_time`, and `ttl_seconds` (time-to-live).

Implement:

```python
class TaskQueue:
    def __init__(self): ...
    def enqueue(self, task_id: str, priority: int,
                enqueue_time: int, ttl: int) -> None:
    def dequeue(self, current_time: int) -> str | None:
        # returns highest-priority non-expired task_id
        # expired tasks (enqueue_time + ttl <= current_time) are silently dropped
    def size(self, current_time: int) -> int:
        # count of non-expired tasks
```

## Example

```
q = TaskQueue()
q.enqueue("t1", 5, t=0, ttl=10)
q.enqueue("t2", 8, t=0, ttl=3)
q.enqueue("t3", 6, t=0, ttl=20)
q.dequeue(current_time=4)  -> "t1"  (t2 expired at t=3; t1 priority>t3)
q.dequeue(current_time=4)  -> "t3"
```

## Follow-ups

1. How do you handle expired-task cleanup lazily vs. eagerly?
2. What if two tasks have equal priority -- how do you break ties (FIFO? shortest TTL first)?
3. How would you make `dequeue` O(log n)?
4. Support `cancel(task_id)` that removes a task by ID efficiently.

Queue Management - Task Scheduler with Priority and Expiry

Question Details

Full Details

Topics

More from Google