Goldman Sachs·Software Engineer·Technical Phone Screen·Intermediate

Intermediate

Jul 2026

Summary

Goldman Sachs SWE interview had me implement a double-ended queue from scratch, which sounds straightforward until you actually have to think through all the edge cases under pressure. Decent problem, nothing too wild.

Questions Asked (1)

Implement a double-ended queue (Deque) for strings from scratch, supporting addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast, and getSize, all in O(1) time. Include test cases covering edge cases.

Algorithms & Data StructuresTechnical Trade-offs

Author's notes

The O(1) constraint is what makes this non-trivial.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then choose a doubly linked list with sentinel nodes for O(1) operations. Implement the Deque class with careful pointer manipulation, and design test cases covering empty, single-element, and multi-element scenarios.

Pro tip: Use sentinel (dummy) head and tail nodes to eliminate null checks and simplify edge cases, making the code cleaner and less error-prone. Also, discuss time and space complexity trade-offs compared to using a dynamic array.

1. Clarify requirements and constraints

Confirm that operations must be O(1), the data type is string, and whether nulls are allowed. Discuss potential use cases to show understanding.

2. Choose data structure and design

Select a doubly linked list with sentinel nodes for O(1) operations. Explain why this is better than a dynamic array for frequent add/remove at both ends.

3. Implement core operations

Write methods for addFirst, addLast, removeFirst, removeLast, peekFirst, peekLast, and getSize. Ensure pointer updates are correct and handle empty deque cases.

4. Design test cases

Cover edge cases: empty deque, single element, multiple elements, and sequences of operations. Include tests for removing from empty (should throw exception or return null based on design).

5. Analyze complexity and trade-offs

State that all operations are O(1) time and O(n) space. Compare with alternative implementations (e.g., circular array) and discuss pros and cons.

Key Points to Mention

Use of sentinel nodes to simplify edge cases and avoid null checks.
O(1) time complexity for all operations due to direct pointer manipulation.
Handling of empty deque scenarios (e.g., throwing NoSuchElementException or returning null).
Trade-offs between linked list and array-based implementations (memory overhead, cache locality).
Test cases should include: empty, single element, multiple elements, and interleaved operations.
Consider thread-safety if relevant, but not required unless specified.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.