Katkat
Back

Design an Indexable Deque with O(1) Access

Hudson River TradingSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenSoftware Engineering Fundamentals

Last updated

Tests understanding of low-level data structure design, memory layout, and trade-offs required to build a double-ended queue supporting strict O(1) random indexing and amortized O(1) push/pop operations.

Problem Statement

Standard queue and deque implementations often prioritize push/pop performance at both ends, but not all provide constant-time random access by index. In high-performance trading environments, systems frequently require sliding windows or order queues that allow rapid insertion/removal at boundaries alongside instant lookups by relative position.

Design an IndexableDeque class that provides random access by 0-based index while supporting dynamic push and pop operations at both ends.

Implement the following API:

class IndexableDeque:
    def __init__(self):
        """Initializes an empty deque."""
        pass

    def push_front(self, val: int) -> None:
        """Inserts val at the front of the deque in amortized O(1) time."""
        pass

    def push_back(self, val: int) -> None:
        """Inserts val at the back of the deque in amortized O(1) time."""
        pass

    def pop_front(self) -> int:
        """Removes and returns the front element. Raises IndexError if empty."""
        pass

    def pop_back(self) -> int:
        """Removes and returns the back element. Raises IndexError if empty."""
        pass

    def get(self, index: int) -> int:
        """Returns the element at 0-based index from the front in worst-case O(1) time."""
        pass

    def set(self, index: int, val: int) -> None:
        """Updates the element at 0-based index from the front in worst-case O(1) time."""
        pass

    def size(self) -> int:
        """Returns the number of elements currently stored in O(1) time."""
        pass

Example

deque = IndexableDeque()
deque.push_back(10)     # deque: [10]
deque.push_back(20)     # deque: [10, 20]
deque.push_front(5)     # deque: [5, 10, 20]

print(deque.get(0))     # Output: 5
print(deque.get(1))     # Output: 10
print(deque.get(2))     # Output: 20

deque.set(1, 15)        # deque: [5, 15, 20]
print(deque.get(1))     # Output: 15

print(deque.pop_front()) # Output: 5,  deque: [15, 20]
print(deque.pop_back())  # Output: 20, deque: [15]
print(deque.size())      # Output: 1

Constraints

  • -10^9 = size().
  • You cannot use built-in high-level deque classes (such as Python's collections.deque or C++ std::deque) to back the primary storage; implement the underlying buffer mechanics using a fixed or dynamic contiguous array.

Hints

Hint 1

A circular buffer (ring buffer) using a fixed-capacity array with a head offset and a current size variable allows mapping logical index `i` to physical index `(head + i) % capacity` in O(1) time.

Hint 2

When moving `head` backwards for `push_front`, use modulo arithmetic `(head - 1 + capacity) % capacity` to wrap around properly.

Hint 3

When the buffer becomes full, allocate a new array of double the capacity and linearize the elements starting from physical index 0.

Follow-up questions

  • How does a chunked-array layout (like C++ `std::deque`, which uses a map of fixed-size blocks) compare to a single resizing circular array in terms of memory fragmentation, cache locality, and re-allocation latency spikes?
  • In a high-frequency trading application where dynamic resizing latency spikes (jitter) are unacceptable, how would you design this data structure?
  • How could you adapt this structure into a bounded, wait-free Single-Producer Single-Consumer (SPSC) ring buffer?