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.

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.

Hints

  1. 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.
  2. 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.
  3. 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).
  4. For the empty case, check count == 0 before any pop/peek and return None instead of indexing into the array.

Loading coding console...