Schedule Priority Jobs with Cooldowns
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
# Schedule Priority Jobs with Cooldowns
Implement a scheduler for recurring jobs:
```text
addJob(job_id, priority, cooldown) -> bool
getJob() -> job_id or None
```
`addJob` inserts a new job and returns `false` if the ID already exists. Every successful `getJob` call selects the eligible job with the greatest priority; ties are broken by earlier insertion. The selected job remains registered but becomes ineligible for its configured number of subsequent `getJob` invocations. Calls that return `None` still count toward cooldown progress.
For example, a job with cooldown `3` selected on call 5 cannot be selected on calls 6, 7, or 8 and becomes eligible on call 9. A cooldown of `0` permits selection on the next call.
## Constraints
- Up to `200000` total operations.
- Priorities and cooldowns are non-negative integers.
- Job IDs are unique non-empty strings.
- Avoid scanning every registered job on each call.
## Example
Add `A` with priority 10 and cooldown 2, then `B` with priority 5 and cooldown 0. Four calls to `getJob` return `A, B, B, A`.
## Clarifications
Insertion order never changes after a job runs. Define the invocation counter precisely and explain how jobs move between waiting and eligible structures.
## Hints
One priority structure can hold eligible jobs while another structure orders cooling jobs by the invocation when they become eligible.
## Extensions
- Support priority updates and job removal.
- Use wall-clock release times instead of invocation counts.
- Make `getJob` safe for concurrent workers without returning one job twice.
Quick Answer: Implement a recurring-job scheduler that selects the highest-priority eligible job and enforces cooldowns measured in later retrieval calls. Preserve insertion-order tie-breaking while handling empty calls, zero cooldowns, duplicate IDs, large workloads, concurrent workers, updates, and removals.
You are given a recorded batch of scheduler commands and must
return the value that each command produces.
The scheduler supports exactly two commands.
- `addJob(job_id, priority, cooldown)` registers a new job. If a job with the
same `job_id` is already registered, the call changes nothing and reports
failure. Otherwise the job is registered and the call reports success. A job
that has just been registered is eligible straight away.
- `getJob()` selects and returns the eligible job with the greatest `priority`.
Ties are broken in favour of the job that was registered earlier. If no job is
eligible at that moment, the call returns nothing.
### The cooldown rule
Number the `getJob` calls `1, 2, 3, ...` in the order they occur. `addJob` calls
are not numbered and never advance that counter.
When `getJob` call number `t` selects a job whose cooldown is `c`, the job stays
registered but becomes ineligible for calls `t + 1` through `t + c`, and is
eligible again from call `t + c + 1` onwards. A cooldown of `0` therefore lets a
job be selected again on the very next call. A `getJob` call that returns nothing
still advances the counter, so it still moves every cooling job closer to being
eligible. Registration order is fixed at registration time and never changes,
including after a job is selected.
### Input encoding
`operations[i]` is the name of the i-th command, either `"addJob"` or
`"getJob"`. `args[i]` carries that command's arguments:
- for `"addJob"`, `args[i]` is exactly `[job_id, priority, cooldown]` — three
strings, where `priority` and `cooldown` are decimal representations of
non-negative integers;
- for `"getJob"`, `args[i]` is the empty list `[]`.
### Output encoding
Return a list of strings with one entry per command, in command order:
- for `"addJob"`: `"true"` if the job was registered, `"false"` if the id was
already taken;
- for `"getJob"`: the id of the selected job, or the empty string `""` if no job
was eligible. Job ids are never empty, so `""` is unambiguous.
### Example 1
```text
operations = ["addJob", "addJob", "getJob", "getJob", "getJob", "getJob"]
args = [["A", "10", "2"], ["B", "5", "0"], [], [], [], []]
output = ["true", "true", "A", "B", "B", "A"]
```
Both registrations succeed. Call 1 picks `A` (priority 10 beats 5), so `A` is
ineligible for calls 2 and 3. `B` wins calls 2 and 3 because its cooldown of `0`
lets it repeat immediately. At call 4 `A` is eligible again (`1 + 2 + 1 = 4`) and
outranks `B`.
### Example 2
```text
operations = ["addJob", "addJob", "getJob", "getJob", "getJob"]
args = [["x", "7", "5"], ["x", "99", "0"], [], [], []]
output = ["true", "false", "x", "", ""]
```
The second `addJob` is rejected because id `"x"` is already registered; its
priority `99` and cooldown `0` are discarded, leaving the original job untouched.
Call 1 selects `x`, whose cooldown of `5` keeps it ineligible until call
`1 + 5 + 1 = 7`, so calls 2 and 3 find nothing eligible and return `""`.
Constraints
- 0 <= operations.length <= 200000 (the total number of scheduler commands)
- args.length == operations.length
- operations[i] is either "addJob" or "getJob"
- args[i] has exactly 3 entries when operations[i] == "addJob", and 0 entries when operations[i] == "getJob"
- 1 <= job_id.length <= 20; job ids are non-empty ASCII strings
- 0 <= priority <= 10^12 (given as a decimal string)
- 0 <= cooldown <= 10^12 (given as a decimal string)
- Priorities, cooldowns and release call numbers exceed 2^31 - 1: use long in Java and long long / int64_t in C++ for every one of them
- The returned list has exactly operations.length entries
Examples
Input: ([], [])
Expected Output: []
Input: (['getJob'], [[]])
Expected Output: ['']
Hints
- Keep one counter that increases on every getJob call, including the calls that find nothing eligible, and store each job's cooldown as the earliest call number at which it may be chosen again.
- A job is always in exactly one of two states, cooling or eligible. Give each state its own ordered structure and you never have to look at a job that is still cooling.
- The tie-break rule 'registered earlier wins' never changes, so a job's ranking among eligible jobs is fixed the moment it is registered — it can be baked into a heap key.