Implement std::deque

Implementing a double-ended queue in C++ with O(1) operations

This hard coding problem tests your ability to design and implement a custom deque from scratch, meeting strict time-complexity guarantees. It is a favourite at trading firms and asset managers who hire systems engineers, as it requires both algorithmic insight and careful C++ implementation.

The core challenge is supporting amortized O(1) insertions and deletions at both ends, plus O(1) random access, without using standard containers or linked lists. This rules out simple approaches (like a singly-allocated buffer) and requires you to think through growth and allocation strategy. A secondary constraint—that element types need not be default-constructible—forces you to avoid placeholder allocations or in-place construction tricks that rely on default initialization.

• Circular-buffer logic and index wrapping
• Dynamic resizing with amortized cost analysis
• Placement new and explicit destruction to sidestep default construction
• Bounds checking and exception safety