The Double-Ended Gateway

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

Build MyDeque, a queue we can add to, remove from and look at from either end without leaning on collections.deque, along with the run_deque_ops(operations, args) driver we use to replay a recorded session against it. A session always opens by constructing the deque, and each call's result lands at the same position in the list the driver returns.

Some queues let you skip the line from both ends.

Example

Input:

args = [[],[1],[2],[],[],[],[],[]], operations = ["MyDeque","push_back","push_front","peek_front","peek_back","pop_front","pop_back","is_empty"]

Output:

[null,null,null,2,1,2,1,true]

Worked solution and explanation

Why this problem exists in real interviews

This is pointer bookkeeping dressed up as a queue. Banning collections.deque forces you to own both ends yourself: a stack or a head-only linked list cannot hand back the oldest item from the front while also popping the newest from the back. Anyone can write push_back. What separates candidates is the empty transition: the moment the deque drains, head and tail must both reset, and the moment it refills, both must point at the same node. Miss one and the next peek_back reads a ghost from the previous session.

Break down the requirements

Step 1: Pick a structure with O(1) at both ends

A doubly linked list gives O(1) push and pop at both ends. A circular buffer with a moving head/tail also works, but resizing is fiddly to get right in 20 minutes.

Step 2: Maintain head, tail, and a size counter

Every mutator updates head or tail (or both, when the deque becomes empty or non-empty). Track _size so is_empty is O(1) and you do not have to walk the list.

Step 3: Handle the empty-deque transitions

The two tricky cases are: (a) inserting into an empty deque, where head and tail must point to the same node, and (b) popping the last element, where both head and tail must reset to None. Most bugs in deque implementations live here.

Step 4: Drive the deque from the operation log

The harness hands you two parallel lists: operations (method names, with the first one meaning construct) and args (the positional arguments for each call). When you construct the deque, build a small table from each method name to its bound method, then walk both lists together and append every return value (None for the constructor and the pushes) to the results list.

The solution

Doubly linked list driven by an operation log
class _Node:
    __slots__ = ("val", "prev", "next")

    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None


class MyDeque:
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0

    def push_front(self, x):
        node = _Node(x)
        if self._head is None:
            self._head = node
            self._tail = node
        else:
            node.next = self._head
            self._head.prev = node
            self._head = node
        self._size += 1

    def push_back(self, x):
        node = _Node(x)
        if self._tail is None:
            self._head = node
            self._tail = node
        else:
            node.prev = self._tail
            self._tail.next = node
            self._tail = node
        self._size += 1

    def pop_front(self):
        node = self._head
        self._head = node.next
        if self._head is None:
            # the deque just drained: the tail must go too
            self._tail = None
        else:
            self._head.prev = None
        self._size -= 1
        return node.val

    def pop_back(self):
        node = self._tail
        self._tail = node.prev
        if self._tail is None:
            self._head = None
        else:
            self._tail.next = None
        self._size -= 1
        return node.val

    def peek_front(self):
        return self._head.val

    def peek_back(self):
        return self._tail.val

    def is_empty(self):
        return self._size == 0


def run_deque_ops(operations, args):
    results = []
    dispatch = {}
    for op, call_args in zip(operations, args):
        if op == "MyDeque":
            deque = MyDeque()
            dispatch = {
                "push_front": deque.push_front,
                "push_back": deque.push_back,
                "pop_front": deque.pop_front,
                "pop_back": deque.pop_back,
                "peek_front": deque.peek_front,
                "peek_back": deque.peek_back,
                "is_empty": deque.is_empty,
            }
            results.append(None)
        else:
            method = dispatch[op]
            results.append(method(*call_args))
    return results

Common follow-up questions