How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Tml.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Tml during technical interviews.

Implement a Resizable Deque | Tml Coding Question

Implement a Resizable Deque

Company: Tml

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a double-ended queue (deque) data structure backed by a circular array. Your deque should support insertion and removal from both ends and should automatically resize when it becomes full. Required operations: - `pushFront(value)`: Insert `value` at the front. - `pushBack(value)`: Insert `value` at the back. - `popFront()`: Remove and return the front element. If the deque is empty, handle the error clearly. - `popBack()`: Remove and return the back element. If the deque is empty, handle the error clearly. - `peekFront()`: Return the front element without removing it. - `peekBack()`: Return the back element without removing it. - `isEmpty()`: Return whether the deque is empty. - `size()`: Return the number of elements currently stored. Implementation requirements: - Use an array as the underlying storage. - Treat the array as circular so that operations at both ends are efficient. - When the array is full, allocate a larger array, copy the elements in logical deque order, and update internal pointers correctly. - Each operation should run in `O(1)` amortized time.

Quick Answer: This question evaluates proficiency in data structures and array-based implementations, specifically building a resizable double-ended queue (deque) backed by a circular array and understanding amortized O(1) operation costs.

Implement a double-ended queue (deque) data structure backed by a **circular array** that automatically resizes when it becomes full. You will be given two parallel lists, `operations` and `arguments`. `operations[i]` is the name of the method to call, and `arguments[i]` is a list holding that call's arguments (empty list for no-arg methods). Apply every operation in order to a fresh deque and return a list of the results. Supported operations: - `pushFront(value)`: Insert `value` at the front. Result: `None`. - `pushBack(value)`: Insert `value` at the back. Result: `None`. - `popFront()`: Remove and return the front element, or `None` if the deque is empty. - `popBack()`: Remove and return the back element, or `None` if the deque is empty. - `peekFront()`: Return the front element without removing it, or `None` if empty. - `peekBack()`: Return the back element without removing it, or `None` if empty. - `isEmpty()`: Return whether the deque is empty (boolean). - `size()`: Return the number of elements currently stored (integer). Implementation requirements: - Use a plain array as the underlying storage and treat it as **circular** so both ends are O(1) amortized. - When the array is full, allocate a larger array, copy elements in logical deque order, and reset the internal pointers. Return the list of results, one entry per operation.

Constraints

1 <= number of operations <= 10^5
Values fit in a 32-bit signed integer (negatives allowed).
popFront/popBack/peekFront/peekBack on an empty deque must return None (no exception thrown by the driver).
All operations must run in O(1) amortized time.

Examples

Input: (['pushBack', 'pushBack', 'pushFront', 'peekFront', 'peekBack', 'size', 'popFront', 'popBack', 'popFront', 'isEmpty'], [[1], [2], [0], [], [], [], [], [], [], []])

Expected Output: [None, None, None, 0, 2, 3, 0, 2, 1, True]

Explanation: After pushBack(1), pushBack(2), pushFront(0) the deque is [0, 1, 2]. peekFront=0, peekBack=2, size=3. popFront removes 0, popBack removes 2, popFront removes 1, leaving it empty so isEmpty=True.

Input: (['isEmpty', 'size', 'popFront', 'popBack', 'peekFront', 'peekBack'], [[], [], [], [], [], []])

Expected Output: [True, 0, None, None, None, None]

Explanation: Edge case: every operation on a brand-new empty deque. isEmpty=True, size=0, and all pop/peek operations return None instead of erroring.

Input: (['pushBack', 'pushBack', 'pushBack', 'pushBack', 'pushBack', 'pushBack', 'size', 'peekFront', 'peekBack'], [[10], [20], [30], [40], [50], [60], [], [], []])

Expected Output: [None, None, None, None, None, None, 6, 10, 60]

Explanation: Six pushBack calls exceed the initial capacity (4), forcing at least one resize. After resizing, logical order is preserved: front=10, back=60, size=6.

Input: (['pushFront', 'pushFront', 'pushFront', 'pushFront', 'pushFront', 'popBack', 'popBack', 'peekFront', 'size'], [[1], [2], [3], [4], [5], [], [], [], []])

Expected Output: [None, None, None, None, None, 1, 2, 5, 3]

Explanation: Five pushFront calls build [5, 4, 3, 2, 1] and trigger a resize. popBack twice removes 1 then 2; the new front (most recent pushFront) is 5, and size is 3.

Input: (['pushFront', 'popFront', 'isEmpty', 'pushBack', 'peekBack', 'popBack', 'isEmpty'], [[-7], [], [], [-9], [], [], []])

Expected Output: [None, -7, True, None, -9, -9, True]

Explanation: Negative values and alternating ends: pushFront(-7) then popFront returns -7, deque empty. pushBack(-9), peekBack=-9, popBack returns -9, deque empty again.

Hints

Track three things: the backing array, the index of the front element (head), and the current element count. The back index is always (head + count - 1) modulo capacity.
pushFront moves head one step counter-clockwise: head = (head - 1) mod cap. pushBack writes at (head + count) mod cap. Use modulo so the indices wrap around the circular array.
Resize only when count == capacity: allocate a 2x array, copy the count elements in logical order starting from head, then reset head to 0. This keeps the amortized cost O(1).
For the empty case, check count == 0 before any pop/peek and return None instead of indexing into the array.

Quick Overview

This question evaluates proficiency in data structures and array-based implementations, specifically building a resizable double-ended queue (deque) backed by a circular array and understanding amortized O(1) operation costs.