Katkat
Back

Implement a Resizable Deque

TmlSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.