Katkat
Back

Implement a Fixed-Capacity Deque

Applied IntuitionMachine Learning Engineer · Technical Screen
MediumMachine Learning EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates proficiency with double-ended queue semantics, fixed-capacity data structure design, constant-time (O(1)) operations, and correct handling of boundary conditions and wraparound.

Design and implement a fixed-capacity double-ended queue.

The data structure is initialized with an integer capacity k and must support the following operations in O(1) time:

  • insertFront(value): Insert value at the front. Return true if successful, or false if the deque is full.
  • insertLast(value): Insert value at the back. Return true if successful, or false if the deque is full.
  • deleteFront(): Delete the front element. Return true if successful, or false if the deque is empty.
  • deleteLast(): Delete the back element. Return true if successful, or false if the deque is empty.
  • getFront(): Return the front element, or -1 if the deque is empty.
  • getRear(): Return the back element, or -1 if the deque is empty.
  • isEmpty(): Return whether the deque is empty.
  • isFull(): Return whether the deque is full.

You may assume 1 <= k <= 1000 and values are integers. Explain your representation and handle wraparound correctly.