A Job Queue with Priorities

The interview question: "Design a job queue. Workers ask for the next job, the most urgent job goes first, and no job may be lost when the worker that took it crashes."

The expected answer: give out the highest priority first and, among equal priorities, the oldest job. Taking a job is only a lease: if the job isn't marked done within a timeout, it goes back in the queue for another worker. Real queues call this a visibility timeout.

Python's sort does the ordering. With key= it orders the items by what a function returns, reverse=True puts the biggest first, and the sort is stable: items with equal keys keep their order. For example, ideas sorted by votes, most votes first:

def by_votes(idea):
    return idea["votes"]

ideas.sort(key=by_votes, reverse=True)

Time comes from now(), and the tests move it with a hidden clock, in seconds. Three jobs are added at second 1000, then workers ask for jobs. Nobody ever finishes charge card:

POST /jobs  {"task": "send newsletter", "priority": 1}  →  201  {"id": 1, …, "status": "waiting"}
POST /jobs  {"task": "charge card", "priority": 5}  →  201  {"id": 2, …, "status": "waiting"}
POST /jobs  {"task": "resize photo", "priority": 5}  →  201  {"id": 3, …, "status": "waiting"}
at 1000  POST /jobs/next    →  200  {"id": 2, "task": "charge card", "status": "taken", "taken_at": 1000, …}
at 1010  POST /jobs/next    →  200  {"id": 3, "task": "resize photo", "status": "taken", "taken_at": 1010, …}
at 1020  POST /jobs/3/done  →  200  {"id": 3, "status": "done", …}
at 1029  POST /jobs/next    →  200  {"id": 1, "task": "send newsletter", "taken_at": 1029, …}
at 1029  POST /jobs/next    →  204  (nothing is waiting: charge card was taken only 29 seconds ago)
at 1030  POST /jobs/next    →  200  {"id": 2, "task": "charge card", "taken_at": 1030, …}
at 1059  POST /jobs/next    →  200  {"id": 1, "task": "send newsletter", "taken_at": 1059, …}

Your task: adding jobs, giving out the oldest waiting job and marking a job done already work. Make POST /jobs/next give the highest priority first (the oldest first among equals), save the second each job is taken in "taken_at", and put a job that was taken TIMEOUT (30) or more seconds ago back to "waiting".

Assignment
Follow the Coding Tutorial to write by_priority, sort the waiting jobs with it, save taken_at and send expired jobs back to the queue.

Hint
Use >=, not >: at second 1030 a job taken at 1000 has been out exactly 30 seconds and must come back. Put the timeout check at the top of the loop, before the waiting check, so a job that just came back is counted as waiting in the same request.