How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Goldman Sachs.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Goldman Sachs during technical interviews.

Implement a String Deque | Goldman Sachs Coding Question

Quick Overview

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 String Deque

Company: Goldman Sachs

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Technical Screen

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.

Quick Answer: 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, from scratch. The deque must support inserting and removing from both the front and back in O(1) time. You are given a list of operations to execute on one initially empty deque. Return a list containing the results of all operations that produce a value: removeFirst, removeLast, peekFirst, peekLast, and getSize. The addFirst and addLast operations do not produce output. In Python, null is represented as None. Therefore, removeFirst, removeLast, peekFirst, and peekLast should return None when the deque is empty. You may not use a built-in deque or linked-list library.

Constraints

0 <= len(operations) <= 100000
0 <= len(data) <= 100 for each inserted string
All operation names are valid
All deque operations must run in O(1) time
Do not use a built-in deque or linked-list library

Examples

Input: ([('addFirst', 'apple'), ('addLast', 'banana'), ('peekFirst',), ('peekLast',), ('getSize',), ('removeFirst',), ('removeLast',), ('removeLast',)],)

Expected Output: ['apple', 'banana', 2, 'apple', 'banana', None]

Explanation: After adding apple to the front and banana to the back, the deque is [apple, banana]. Peeks return apple and banana, size is 2, then removals return apple, banana, and finally None because the deque is empty.

Input: ([('addLast', 'a'), ('removeFirst',), ('getSize',), ('addFirst', 'b'), ('addLast', 'c'), ('removeLast',), ('removeLast',), ('peekFirst',)],)

Expected Output: ['a', 0, 'c', 'b', None]

Explanation: Removing the only element a makes the deque empty. Later b and c are added, removed from the back as c then b, and the final peek returns None.

Hints

A singly linked list can remove efficiently from the front, but what extra pointer information is needed to remove from the back in O(1)?
Be careful when the deque transitions between empty, one element, and multiple elements; both front and back pointers may need updates.