The Queue Disguise

A medium Python interview practice problem on DataDriven. Write the Python and run it against test cases, with instant feedback.

Domain
Python
Difficulty
medium
Seniority
L4
Asked in
Citadel

Problem

Jobs must leave our queue in the order they arrived, even when new jobs land between pickups. Build a JobQueue class with push, pop, peek and empty, then have run_queue_operations replay the operations log against a fresh queue (each entry's arguments sit at the same position in args) and return one result per operation.

A queue in sheep's clothing.

Example 1

Input:

args = [[],[101],[102],[],[],[]], operations = ["JobQueue","push","push","peek","pop","empty"]

Output:

[null,null,null,101,101,false]

Example 2

Input:

args = [[],[],[205],[],[],[]], operations = ["JobQueue","empty","push","empty","pop","empty"]

Output:

[null,true,null,false,205,true]

Worked solution and explanation

What this really is

This is an arrival-order problem wearing a class-design costume. The log interleaves pushes with pickups. Every pop and peek has to see the oldest job still waiting, and empty has to count jobs that arrived after the last pickup. Anyone can write the dispatcher. What separates candidates is where they take jobs from. Taking from the end of a list hands out the newest job (103 where the log expects 101). pop(0) gets the order right but shifts every remaining job on each pickup, which makes a long log quadratic.

Step 1: Keep arrivals and pickups apart

_pending collects new arrivals with append. _ready is the batch currently being handed out, and _cursor points at its oldest job not yet served. Nothing is ever removed from the front of a list, so nothing shifts.

Step 2: Swap batches only when _ready runs out

_refill returns early while _cursor is still inside _ready. Once every ready job has been served, the pending list becomes the new ready batch in one assignment and _pending starts over. Arrival order survives because append already stored the pending jobs oldest first.

Step 3: Make empty look at both lists

A job pushed after the last swap sits in _pending while _ready looks finished. empty is true only when the cursor has passed the end of _ready and _pending holds nothing. The second visible example (push 205, then empty) is exactly that state.

Step 4: Replay the log in step with args

zip(operations, args) pairs each name with its arguments. The constructor and every push record None, pop and peek record the job, and empty records the bool.

A ready batch with a cursor, refilled from pending arrivals
class JobQueue:
    def __init__(self):
        self._pending = []
        self._ready = []
        self._cursor = 0

    def push(self, job):
        self._pending.append(job)

    def _refill(self):
        # Swap in the pending batch only once every ready job has been handed out.
        if self._cursor < len(self._ready):
            return
        self._ready = self._pending
        self._pending = []
        self._cursor = 0

    def pop(self):
        self._refill()
        job = self._ready[self._cursor]
        self._cursor += 1
        return job

    def peek(self):
        self._refill()
        return self._ready[self._cursor]

    def empty(self):
        return self._cursor >= len(self._ready) and not self._pending


def run_queue_operations(operations, args):
    queue = None
    results = []
    for op, arg in zip(operations, args):
        if op == "JobQueue":
            queue = JobQueue()
            results.append(None)
        elif op == "push":
            queue.push(arg[0])
            results.append(None)
        elif op == "pop":
            results.append(queue.pop())
        elif op == "peek":
            results.append(queue.peek())
        elif op == "empty":
            results.append(queue.empty())
    return results
Take from the front
jobs.pop(0) returns the right job, but Python shifts every remaining element left on each call: O(n) per pickup, O(n^2) over a log of n pickups.
Cursor over a ready batch
Reading _ready[_cursor] and advancing the cursor is O(1). Each job is appended once and handed out once, so the whole log is O(n).

Common follow-up questions