← Goldman Sachs Interview Insights

Goldman Sachs·Software Engineer·Onsite - Coding / Algorithms·Intermediate

IntermediatePrefer not to say
May 2026

Summary

Goldman Sachs SWE interview with a data structures implementation question. Pretty straightforward coding round but the constraint of not using built-in hash tables means you actually have to think through the internals, which tripped me up a bit.

Questions Asked (1)

Q1

Design and implement a HashMap from scratch (no built-in hash table libraries allowed) that supports put, get, and remove operations on integer keys and values.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I knew what a hash map was conceptually but actually building one without reaching for the language's built-in felt weird.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements (e.g., expected load, collision handling, thread-safety) and then propose a design using an array of buckets with separate chaining (linked lists or balanced BSTs). Implement put, get, and remove with proper resizing and hash function, and analyze time/space complexity and trade-offs.

Pro tip: Mention that you would use a prime number for the bucket array size and a good hash function (like multiplying by a prime and using bitwise operations) to minimize collisions, and discuss how you would handle resizing to maintain O(1) average time.

1. Clarify Requirements and Constraints

Ask about expected number of elements, load factor, thread-safety, and whether keys/values are integers only. Confirm that no built-in hash table libraries are allowed.

2. Design the Data Structure

Propose an array of buckets, each bucket being a linked list (or a balanced BST for worst-case O(log n)). Choose a hash function (e.g., key * 2654435761 mod 2^32, then mod bucket count) and a collision resolution strategy (separate chaining).

3. Implement Core Operations

Write pseudocode or code for put (insert or update), get (retrieve), and remove (delete). Include resizing logic: when load factor exceeds threshold (e.g., 0.75), double the array size and rehash all elements.

4. Analyze Complexity and Trade-offs

Discuss average O(1) time for put/get/remove, worst-case O(n) with linked lists or O(log n) with BSTs. Mention space complexity O(n). Compare separate chaining vs. open addressing and when to use each.

5. Test and Optimize

Outline test cases: empty map, single element, collisions, resizing, removal of non-existent key. Suggest optimizations like using a prime bucket count, caching hash codes, or using a balanced tree for high-collision scenarios.

Key Points to Mention

  • Hash function design: use a good mixing function (e.g., multiply by a prime, XOR shifts) to distribute keys uniformly.
  • Collision resolution: separate chaining with linked lists (or balanced BSTs for worst-case guarantees).
  • Load factor and resizing: maintain load factor below a threshold (e.g., 0.75) and double the array size when exceeded, rehashing all elements.
  • Time complexity: average O(1) for put/get/remove, worst-case O(n) with linked lists or O(log n) with BSTs.
  • Space complexity: O(n) for n elements, with overhead for buckets and nodes.
  • Trade-offs: separate chaining vs. open addressing (e.g., linear probing) in terms of cache performance, clustering, and deletion complexity.

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