L2 · Working engineerStacks & queues~5 min · 4 tests#42

Implement a Queue in Python

Build a FIFO Queue class with enqueue and dequeue in O(1) using collections.deque, and learn why list.pop(0) is O(n). Tested live in Python.

The problem

Implement a Queue (first in, first out):

enqueue(x) adds to the back
dequeue() removes and returns the front, or None if empty
size()

Every operation should be O(1).

Examples

Example 1

Input

run_ops(Queue, [], [["enqueue", 10], ["enqueue", 20], ["enqueue", 30], ["dequeue"]])

Expected output

[None, None, None, 10]

Example 2

Input

run_ops(Queue, [], [["enqueue", 1], ["enqueue", 2], ["dequeue"], ["dequeue"], ["size"]])

Expected output

[None, None, 1, 2, 0]

+ 2 hidden tests on Submit.

Edge cases to ask about

Dequeue from empty
Interleaved operations

Hints

0/3

How an interviewer scores this

0/9

1. Understand the problemRestate it, ask about edge cases and input size.
2. Write a brute-force solutionCorrect first, clever later.
3. Get the correct outputautoAll visible examples pass.
4. Analyse time complexityautoCommit to a Big-O in the Complexity Lab.
5. Analyse space complexityautoExtra memory, not the input.
6. Identify the bottleneckautoMeasure your code — where does it bend?
7. OptimiseUsually: a set or dict instead of a scan.
8. Explain why it worksSay it out loud to Solvi.
9. Test the edge casesautoSubmit passes every hidden test.

Python 3.13 · Queue

class Queue:
    def __init__(self):
        pass

    def enqueue(self, x):
        pass

    def dequeue(self):
        pass

    def size(self):
        pass

⌘/Ctrl + Enter runs the examples

Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.

Complexity Lab

What does this cost as n grows?

Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and read why.

Time complexity of the optimal solution

Space complexity (extra memory)

Pick both to reveal the answer.

From brute force to optimal

The progression an interviewer wants to hear, one step at a time.

Approach	Time	Space	Idea
list with pop(0)	O(n) dequeue	O(n)	Every dequeue shifts the remaining items left.
bestcollections.deque	O(1) both ends	O(n)	A doubly-linked block list built for this.

Walkthrough of the optimal approach (try it yourself first)

A queue removes from the front. list.pop(0) is O(n) because every remaining element shifts left, so use collections.deque and its O(1) popleft().

For threads, queue.Queue adds locking and blocking get() — mention it.

Complexity: O(1) time, O(n) space. deque.append and deque.popleft are O(1); list.pop(0) would be O(n).

Reveal the reference solution

from collections import deque

class Queue:
    def __init__(self):
        self._items = deque()

    def enqueue(self, x):
        self._items.append(x)

    def dequeue(self):
        return self._items.popleft() if self._items else None

    def size(self):
        return len(self._items)

The brute force, for comparison

class Queue:
    def __init__(self):
        self._items = []

    def enqueue(self, x):
        self._items.append(x)

    def dequeue(self):
        return self._items.pop(0) if self._items else None    # O(n)

    def size(self):
        return len(self._items)

Follow-ups interviewers ask

Implement it with two stacks (question 45).
Bounded queue with a max size.

Frequently asked interview questions

Core interview concepts, complexities, and follow-ups scored by hiring teams.

What is the time complexity of Implement a Queue in Python?

The optimal solution runs in O(1) time and O(n) auxiliary space. deque.append and deque.popleft are O(1); list.pop(0) would be O(n).

What is the brute-force approach, and how do you optimise it?

list with pop(0): O(n) dequeue time, O(n) space. Every dequeue shifts the remaining items left. collections.deque: O(1) both ends time, O(n) space. A doubly-linked block list built for this.

What follow-up questions do interviewers ask about Implement a Queue in Python?

Implement it with two stacks (question 45). Bounded queue with a max size.