# The Double-Ended Gateway

> Some queues let you skip the line from both ends.

Canonical URL: <https://datadriven.io/problems/the_double_ended_gateway>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Implement MyDeque with push_front, push_back, pop_front, pop_back, peek_front, peek_back, is_empty. Do NOT use collections.deque. Test harness: ['MyDeque', args] then op sequences; returns parallel list (None for constructor/mutators, value for peek/pop, True/False for is_empty).

## Worked solution and explanation

### Why this problem exists in real interviews

The prompt explicitly bans `collections.deque`, so the interviewer wants to see whether you know why a Python `list` is a bad answer (popping from the front is O(n)) and whether you can build a doubly linked list cleanly under time pressure.

---

### 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.

---

### The solution

**Doubly linked list with explicit head and tail**

```python
class MyDeque:
    class _Node:
        __slots__ = ('val', 'prev', 'next')

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

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

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

    def push_back(self, x):
        node = MyDeque._Node(x)
        if self._tail is None:
            self._head = 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:
            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
```

> **Cost Analysis**
>
> Time: every operation is O(1) including `is_empty`, `peek_front`, `peek_back`, `push_front`, `push_back`, `pop_front`, `pop_back`. Space: O(N) for N elements, with a constant per-node overhead (val, prev, next).

> **Interviewers Watch For**
>
> Whether your `pop_front` correctly nulls `_tail` when the list becomes empty, whether you reach for a Python `list` (a red flag because `list.pop(0)` is O(n)), and whether you can articulate why the prompt bans `collections.deque` (which would let you skip the whole exercise).

> **Common Pitfall**
>
> Using a Python `list` and calling `lst.pop(0)` for `pop_front`. That works but is O(n) per call because every remaining element shifts left. Interviewers will press on this and ask for the doubly linked version.

---

## Common follow-up questions

- Implement the same deque with a fixed-capacity circular buffer. What changes when you hit capacity? _(Tests array-based deque design. The interesting part is the wraparound math (`(head + 1) % capacity`) and the resize-on-full strategy: allocate a new array, then unwind the ring into contiguous order.)_
- How would you support O(1) random access by index, like `deque[i]`? _(Tests recognition that linked lists cannot do this. The honest answer is: you cannot with a linked list; you would switch to an indexable circular buffer.)_
- Make the deque iterable in front-to-back order. What does `__iter__` look like? _(Tests iterator protocol. A `_Node` walk from `_head` along `.next` until `None`, yielding `node.val` each step.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_double_ended_gateway)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.