Process queue with wait limits: Frontier Interview's solution

Question: Process queue with wait limits

Companies: Amazon

Difficulty: Medium

Problem statement

A single server works through a line of n processes in first-in, first-out order. Process i (0-indexed, in line order) can wait at most wait[i] seconds. Once that much time has passed, it gives up and leaves the line, even if it was never served.

The clock starts at t = 0 with all n processes in line. At every second t = 1, 2, 3, ... two things happen at the same moment:

The process at the front of the line is served and leaves.
Every process still in line with wait[i] <= t leaves because its limit has run out.

Implement:

def queue_sizes(wait: list[int]) -> list[int]:
    ...

Return the number of processes in line at t = 0, then after each second, up to and including the first second at which the line is empty.

Constraints

0 <= n <= 10^5
1 <= wait[i] <= 10^9
Aim for better than O(n^2).

Example 1

wait = [3, 1, 2, 10]
output = [4, 2, 1, 0]

At t=1 the process with wait 3 is served and the one with wait 1 expires, leaving [2, 10]. At t=2 the 2 is served. At t=3 the 10 is served.

Example 2

wait = [5, 1, 1, 2]
output = [4, 1, 0]

At t=1 the 5 is served and both 1s expire. At t=2 the 2 is served, and the line is empty.

Approach

Restate the rules precisely before coding, because the whole problem is in the timing:

At t = 0 all n processes are in line, in index order, and the answer starts with n.
At each second t = 1, 2, ... two things happen at once: the process at the front of the line is served and leaves, and every process with wait[i] <= t leaves because its limit has run out.
Record the queue size after each second. Stop after you record 0.

So the output has one entry per second from 0 to the second the line empties. Since at least one process leaves every second, there are at most n + 1 entries.

Brute force. Simulate literally with a deque: pop the front, then rebuild the deque keeping only w > t. Every second can rescan the whole line, so this is O(n^2). Say it, then improve it. It also makes a good checker for the fast version.

Optimal: bucket by expiry second, plus a lazy front pointer.

A process with wait[i] = w leaves by expiry at second w, unless it was served earlier. Put index i into bucket expires_at[w]. A wait larger than n can never matter, because the line is empty by second n, so clamp it to n + 1. This is a counting sort, so no comparison sort is needed.
Keep a gone[] flag per index and a running alive count.
Each second: move a front pointer forward past processes that are already gone, then serve the first live one. Then walk expires_at[t] and remove each process that is still there.

Invariants.

front never moves backward. Every index before it is gone, so the pointer moves at most n times in total.
Each index is marked gone exactly once, either by being served or by expiring, so alive is always the true queue size.
Each bucket is read once, at its own second.

Together these make the whole simulation linear. The order of the two removals within a second does not change the count. A process that is served and also expires that second is guarded by gone, so it is counted once.

If the interviewer does not want a counting sort, you can instead sort (wait, index) pairs and move a second pointer through them. That is O(n log n) and uses the same idea.

Code

from collections import deque
from typing import List


def queue_sizes(wait: List[int]) -> List[int]:
    """Size of the queue at t = 0, 1, 2, ... until it is empty (inclusive)."""
    n = len(wait)
    # Bucket indices by the second at which they expire. Anything with
    # wait > n is always served before it can expire, so clamp to n + 1.
    expires_at: List[List[int]] = [[] for _ in range(n + 2)]
    for i, w in enumerate(wait):
        expires_at[min(w, n + 1)].append(i)

    gone = [False] * n
    alive = n
    front = 0
    sizes = [alive]

    t = 0
    while alive > 0:
        t += 1
        # 1. Serve the first process still in line.
        while gone[front]:
            front += 1
        gone[front] = True
        alive -= 1
        # 2. Drop every process whose limit has been reached.
        for i in expires_at[t]:  # t <= n: one process leaves every second
            if not gone[i]:
                gone[i] = True
                alive -= 1
        sizes.append(alive)
    return sizes


def queue_sizes_brute(wait: List[int]) -> List[int]:
    q = deque(wait)
    sizes = [len(q)]
    t = 0
    while q:
        t += 1
        q.popleft()
        q = deque(w for w in q if w > t)
        sizes.append(len(q))
    return sizes


if __name__ == "__main__":
    assert queue_sizes([4, 4, 4]) == [3, 2, 1, 0]
    assert queue_sizes([]) == [0]
    assert queue_sizes([1]) == [1, 0]
    assert queue_sizes([1, 1, 1, 1]) == [4, 0]
    assert queue_sizes([5, 1, 1, 2]) == [4, 1, 0]
    assert queue_sizes([3, 1, 2, 10]) == [4, 2, 1, 0]
    assert queue_sizes([2, 9, 9, 9, 3]) == queue_sizes_brute([2, 9, 9, 9, 3])
    print("ok")

Complexity

Bucketing: O(n) time. There are n + 2 buckets and n entries.
Simulation: O(n) time in total. The front pointer and the bucket walks each touch every index at most once, and the loop runs at most n seconds.
Space: O(n) for the buckets, the gone flags and the output.
Brute force, for comparison: O(n^2) time and O(n) space.

Test cases

[3, 1, 2, 10] gives [4, 2, 1, 0]. At t=1 the 3 is served and the 1 expires. At t=2 the 2 is served. At t=3 the 10 is served.
[5, 1, 1, 2] gives [4, 1, 0]. At t=1 the 5 is served and both 1s expire. At t=2 the 2 is served.
[4, 4, 4] gives [3, 2, 1, 0]. Nothing expires, so one process is served per second.
[1, 1, 1, 1] gives [4, 0]. Everything leaves at t=1.
[1] gives [1, 0].
[] gives [0]. An empty line is recorded once.
[10**9] * 3 gives [3, 2, 1, 0]. Huge waits are clamped, so no 10**9-sized array is created.
A process that is served at the same second it expires (for example [1]) is counted as leaving once, not twice.

Follow-ups

Return only the number of seconds until the line is empty. Use the same loop and return t. It is also len(sizes) - 1.
Report which processes were served and which ones expired. Record the reason when you set gone[i], and return two lists or a per-index status. The complexity does not change.
Serving takes k seconds, or c servers work in parallel. For c servers, serve up to c live processes from front each second. For a service time of k, serve only on seconds where t % k == 0. Expiry still works by bucket, and the line still empties within O(n) seconds per server, so the total cost stays linear in n plus the number of seconds.
Processes arrive over time (arrival[i], wait[i]), and the limit is relative to arrival. The expiry second becomes arrival[i] + wait[i]. Buckets no longer fit in O(n) space, so use a min-heap on expiry. Keep the FIFO as a deque with lazy deletion and jump the clock over idle gaps. This costs O(n log n).
Answer queries "how many are in line at second t?" online. Precompute sizes once. Each query is sizes[min(t, len(sizes) - 1)].

Interviewer expectations

Mid-level (L4)

Pins down the timing rule (<=, size recorded at t=0, stop after 0) with an example before coding.
Writes a correct simulation, even if it is O(n^2), and handles the empty input and the "served and expired" double count.
States the complexity correctly.

Senior (L5)

Moves to O(n log n) or O(n) without help, using a sorted or bucketed expiry order plus a lazy front pointer.
Explains why the work is linear in total (each index is removed once, and the pointers only move forward).
Tests against the brute force and lists edge cases such as huge waits and all processes expiring at once.

Staff (L6+)

Generalizes cleanly to arrivals over time, several servers, or service times (heap plus lazy deletion) and says when buckets stop being valid.
Talks about how this models real request queues: deadline-aware load shedding, and the difference between dropping at dequeue and dropping on a timer.
Keeps the code small and organized around invariants, so that adding the follow-ups is a local change.