Coding questions · Applied Intuition

Implement a Fixed-Capacity Deque

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.

Fixed-Capacity Deque Operations

Simulate a circular double-ended queue with O(1) operations and return one output per operation.

Examples

Example 1

Input: (3, [['insertLast',1], ['insertLast',2], ['insertFront',3], ['insertFront',4], ['getRear'], ['isFull'], ['deleteLast'], ['insertFront',4], ['getFront']])
Output: [True, True, True, False, 2, True, True, True, 4]

Explanation: Wraparound and full insert.

Example 2

Input: (1, [['isEmpty'], ['deleteFront'], ['insertFront',9], ['getRear']])
Output: [True, False, True, 9]

Explanation: Empty and singleton.

Hints

Choose a representation that makes the core operation simple.
Handle empty and boundary inputs before the main algorithm.