Goldman Sachs·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say

Apr 2026

Summary

Goldman Sachs SWE interview that had me building a HashMap from scratch, which sounds like a warmup until they start asking about load factors and resizing. More design-heavy than I expected for what looked like a coding question on the surface.

Questions Asked (1)

Design and implement a HashMap from scratch without using any built-in hash-table libraries. Your implementation should support put, get, and remove operations. Be prepared to discuss your bucket structure, hash function choice, load factor, and resizing strategy.

Algorithms & Data StructuresSystem DesignTechnical Trade-offs

Author's notes

Started with the obvious array-of-linked-lists approach and felt pretty good about it.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying requirements and constraints, then outline the core components: an array of buckets, a hash function, collision handling via chaining, and a resizing strategy. Walk through the implementation of put, get, and remove, explaining how each operation interacts with the bucket structure and load factor. Finally, discuss trade-offs and potential optimizations.

Pro tip: Demonstrate awareness of real-world considerations like thread-safety, hash collision attacks, and memory overhead, and mention how your design choices (e.g., load factor, resizing) affect performance in practice.

1. Clarify Requirements and Constraints

Ask about expected key/value types, performance requirements, and whether thread-safety is needed. This shows you think before coding.

2. Design Core Structure

Describe the bucket array, collision resolution (e.g., separate chaining with linked lists or trees), and initial capacity. Explain your hash function choice (e.g., using hashCode() and spreading).

3. Implement Operations

Walk through put, get, and remove: compute hash, find bucket, handle collisions, update size, and check load factor. Mention edge cases like null keys and resizing.

4. Discuss Resizing and Load Factor

Explain the load factor threshold (e.g., 0.75), when and how to resize (double capacity), and rehashing existing entries. Discuss trade-offs between time and space.

5. Analyze Complexity and Trade-offs

Summarize average and worst-case time complexities for operations, and discuss alternatives (e.g., open addressing) and their pros/cons.

Key Points to Mention

Hash function: use key's hashCode() and apply a supplemental hash (e.g., XOR with shifted bits) to reduce collisions.
Collision resolution: separate chaining with linked lists; consider converting to balanced trees (like Java 8) for worst-case O(log n).
Load factor: default 0.75 balances time and space; resizing doubles capacity and rehashes all entries.
Resizing strategy: double capacity when size exceeds threshold; rehash all existing entries to new buckets.
Time complexity: average O(1) for put/get/remove, worst-case O(n) or O(log n) with tree buckets.
Edge cases: null keys (handle specially), hash collisions, and concurrent modification (if thread-safety is required).

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