Katkat
Back

Implement a String Deque

Goldman SachsSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This question evaluates competence with fundamental data structures and algorithms by requiring an implementation of a string double-ended queue (deque), checking understanding of constant-time (O(1)) operations, manipulation of node links or references, and correct handling of edge cases; category: Coding & Algorithms; level: practical implementation rather than purely conceptual. It is commonly asked to assess the ability to implement low-level data structure mechanics, guarantee performance bounds, and expose attention to correctness and boundary conditions in algorithmic coding tasks.

Implement a double-ended queue (Deque) that stores strings.

Your implementation must support the following operations:

  • addFirst(data): Insert data at the front of the deque.
  • addLast(data): Insert data at the back of the deque.
  • removeFirst(): Remove and return the front element. Return null if the deque is empty.
  • removeLast(): Remove and return the back element. Return null if the deque is empty.
  • peekFirst(): Return the front element without removing it. Return null if the deque is empty.
  • peekLast(): Return the back element without removing it. Return null if the deque is empty.
  • getSize(): Return the number of elements currently in the deque.

Requirements:

  • Implement the data structure from scratch; do not use a built-in deque or linked-list library.
  • All operations should run in O(1) time.
  • The deque should correctly handle edge cases such as inserting into an empty deque, removing the only element, and alternating front/back operations.
  • Add a small test method with several test cases covering normal operations and edge cases.