Skip to content
Hello Python
Data Structure1 Practice2 Interview

Deque

Double-ended queue supporting constant-time insertion and removal at both ends. This guide turns that contract into deliberate Python operations, interview invariants, and a runnable practice loop.

Recognize it when

Consider Deque when the prompt's constraints and required operations match this shape: Double-ended queue supporting constant-time insertion and removal at both ends.

Pybit studies a professional Deque interview workspace with precise technical objects.
On this page · Mental Model

Checking your account…

Sign in to save your code and progress across devices. The lesson and problem statement remain public.

Deque Code Labs

Mental Model

A deque is one ordered sequence with efficient access to both ends. Unlike a queue, neither end is intrinsically “front” or “back” until the algorithm assigns that meaning. Make the convention explicit: which operation admits new work, which expires old work, and what order remains inside.

Two Ends, One Ordered Sequence

collections.deque provides append, appendleft, pop, and popleft in O(1) time at their respective ends. Middle indexing is not the purpose of the structure. rotate(k) moves items around the ring; its work depends on the effective rotation distance, so it is not a free whole-deque reordering operation.

The official deque reference(opens in a new tab) also documents maxlen, which automatically discards the opposite-end item when a bounded deque is full.

Use Both Ends Deliberately

The operation name must match the intended end. A command runner makes mistakes immediately observable: left insertion followed by right removal is different from an ordinary FIFO queue.

Route Commands to Both Ends

Reference
from collections import deque

def run_deque_commands(commands):
    items = deque()
    results = []
    for command in commands:
        operation = command[0]
        if operation == 'append-right':
            items.append(command[1])
        elif operation == 'append-left':
            items.appendleft(command[1])
        elif operation == 'pop-left':
            results.append(items.popleft() if items else None)
        elif operation == 'pop-right':
            results.append(items.pop() if items else None)
    return results
Practice

Implement run_deque_commands(commands). Support append-right, append-left, pop-left, and pop-right; removals return the item or None when empty.

Public tests

  • Verify all four end operations

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Maintain a Bounded Recent Window

A deque with maxlen=k contains exactly the latest k appended items. Once full, appending a new item expires the oldest from the left. This is useful for bounded history, but a sliding-window aggregate still needs explicit updates when an expired value affects a sum, count, minimum, or maximum.

Keep Only Recent Values

Reference
from collections import deque

def recent_snapshots(values, capacity):
    recent = deque(maxlen=capacity)
    snapshots = []
    for value in values:
        recent.append(value)
        snapshots.append(list(recent))
    return snapshots
Practice

Implement recent_snapshots(values, capacity). After each append, record the current bounded deque from oldest to newest.

Public tests

  • Verify bounded oldest expiration
  • Verify zero-length boundary

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Choose deque or list

Choose deque for O(1) operations at both ends, a list for indexed access and right-end stack work, a queue convention when only FIFO behavior matters, and a heap when priority determines removal. A monotonic deque adds a stronger invariant: its stored candidates are ordered by value as well as position, allowing obsolete items to leave from one end and dominated items from the other.

Common Pitfalls

  • Calling pop when FIFO code requires popleft silently reverses processing order.
  • Assuming middle access is O(1) treats a deque like an array.
  • Using maxlen without accounting for the automatically expired item breaks aggregates.
  • Calling rotate repeatedly inside a loop can hide superlinear work.

Explain It in an Interview

State the meaning of both ends and the order invariant between them. For a window, say exactly when an index becomes stale and exactly why a candidate may be removed permanently. Count each item by how often it can enter and leave; many deque algorithms are linear because every item is appended once and removed at most once from each end.

Practice Deque Operations(opens in a new tab) establishes the API. Longest Continuous Subarray Within Limit(opens in a new tab) uses two monotonic deques to maintain changing minimum and maximum boundaries.

Python Version Note

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

OperationAverageWorstInterview note
Core Deque workflowO(c)O(c)Process the command stream once with collections.deque and collect only pop results.

Space

O(c) for the demonstrated Deque workflow.

Assumptions

  • The bound assumes deque or list-end operations; removing from the front of a Python list is O(n).
  • The bound counts the operations in Practice Deque Operations and does not hide Python slicing, sorting, or copying.

Invariants Worth Saying Aloud

  1. State the precise Deque invariant before coding and preserve it after every update, traversal step, or recursive return.
  2. Use collections.deque when both ends need constant-time updates. This remains true after every accepted operation.
  3. Keep mutation commands separate from the list of observable pop results. This remains true after every accepted operation.

When To Use Or Avoid Deque

Use It When

  • Use Deque when its representation directly supports the prompt's repeated query or update.
  • Use it when the invariant can be stated before coding and preserved after every operation.

Choose Another Tool When

  • Avoid it when a simpler Python sequence or mapping communicates the same contract with less state.
  • Avoid it when building the structure costs more time or space than the number of required queries can justify.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Leaving the core transition unfinished

Placeholder code cannot preserve the Deque invariant or satisfy the public contract.

Prevent it: Implement the smallest complete transition and run the public tests before adding optimizations.

Avoid

from collections import deque

def run_deque_commands(commands):
    pass

Use instead

from collections import deque

def run_deque_commands(commands):
    items = deque()
    results = []
    for command in commands:
        operation = command[0]
        if operation == "append-right":
            items.append(command[1])
        elif operation == "append-left":
            items.appendleft(command[1])
        elif operation == "pop-left":
            results.append(items.popleft() if items else None)
        elif operation == "pop-right":
            results.append(items.pop() if items else None)
    return results

Where you will hit this: Practice Deque Operations(opens in a new tab)

Breaking the central invariant

Uses list left removal, which raises on empty input and violates the required empty-pop result.

Prevent it: Keep this invariant visible while editing: State the precise Deque invariant before coding and preserve it after every update, traversal step, or recursive return.

Avoid

def run_deque_commands(commands):
    items = []
    results = []
    for command in commands:
        if command[0] == "pop-left":
            results.append(items.pop(0))
    return results

Use instead

from collections import deque

def run_deque_commands(commands):
    items = deque()
    results = []
    for command in commands:
        operation = command[0]
        if operation == "append-right":
            items.append(command[1])
        elif operation == "append-left":
            items.appendleft(command[1])
        elif operation == "pop-left":
            results.append(items.popleft() if items else None)
        elif operation == "pop-right":
            results.append(items.pop() if items else None)
    return results

Where you will hit this: Practice Deque Operations(opens in a new tab)

Hiding Python work inside the loop

Handle empty state, duplicate values, aliasing, and serialization boundaries explicitly in tests.

Prevent it: Account for every slice, copy, sort, membership test, and container mutation before claiming O(c).

Avoid

def run_deque_commands(commands):
    items = []
    results = []
    for command in commands:
        if command[0] == "pop-left":
            results.append(items.pop(0))
    return results

Use instead

from collections import deque

def run_deque_commands(commands):
    items = deque()
    results = []
    for command in commands:
        operation = command[0]
        if operation == "append-right":
            items.append(command[1])
        elif operation == "append-left":
            items.appendleft(command[1])
        elif operation == "pop-left":
            results.append(items.popleft() if items else None)
        elif operation == "pop-right":
            results.append(items.pop() if items else None)
    return results

Where you will hit this: Longest Continuous Subarray Within Limit(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.