Skip to main content

706. Design HashMap

easyAsked at Twilio

Design HashMap is Twilio's data-structure-from-scratch probe: implement put, get, and remove without using any built-in hash table. The grading bar is the chained-bucket design — modulo-bucket + linked-list-of-(key,value) — with explicit collision handling.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Twilio loops.

  • Glassdoor (2026-Q1)— Reported in Twilio backend SWE phone-screen sessions as a 'show-me-collision-handling' warm-up.
  • LeetCode Discuss (2025-11)— Listed in Twilio interview reports for platform-engineering candidates.

Problem

Design a HashMap without using any built-in hash table libraries. Implement the MyHashMap class: MyHashMap() initializes the object with an empty map; void put(int key, int value) inserts a (key, value) pair, updating value if key exists; int get(int key) returns the value or -1 if the key doesn't exist; void remove(int key) removes the key and its value if it exists.

Constraints

  • 0 <= key, value <= 10^6
  • At most 10^4 calls will be made to put, get, and remove.

Examples

Example 1

Input
put(1,1), put(2,2), get(1), get(3), put(2,1), get(2), remove(2), get(2)
Output
[null, null, null, 1, -1, null, 1, null, -1]

Approaches

1. Single big array indexed directly by key (rejected for memory)

Pre-allocate an array of size 10^6 + 1; index directly by key.

Time
O(1) per op
Space
O(MAX_KEY)
class MyHashMapDirect {
  constructor() {
    this.data = new Array(1_000_001).fill(-1);
  }
  put(key, value) { this.data[key] = value; }
  get(key) { return this.data[key]; }
  remove(key) { this.data[key] = -1; }
}

Tradeoff: Trivially correct but allocates 10^6 entries up front regardless of usage. Twilio interviewers explicitly reject this — the question is testing whether you can build a hashmap, not exploit the bounded key range.

2. Chained buckets (separate chaining, optimal)

Fixed-size bucket array; each bucket is a list of (key, value) pairs. Hash by modulo, scan the bucket linearly for the key.

Time
O(1) average, O(n) worst-case
Space
O(n)
class MyHashMap {
  constructor() {
    this.numBuckets = 1024; // power-of-2 for fast modulo via &
    this.buckets = Array.from({ length: this.numBuckets }, () => []);
  }
  _hash(key) {
    return key & (this.numBuckets - 1); // == key % 1024 for power-of-2
  }
  put(key, value) {
    const bucket = this.buckets[this._hash(key)];
    for (const pair of bucket) {
      if (pair[0] === key) { pair[1] = value; return; }
    }
    bucket.push([key, value]);
  }
  get(key) {
    const bucket = this.buckets[this._hash(key)];
    for (const pair of bucket) {
      if (pair[0] === key) return pair[1];
    }
    return -1;
  }
  remove(key) {
    const bucket = this.buckets[this._hash(key)];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) { bucket.splice(i, 1); return; }
    }
  }
}

Tradeoff: Average O(1) per op assuming the load factor stays bounded. Bucket count is fixed at 1024 here for simplicity — a production design would resize when n/buckets exceeds a threshold (e.g., 0.75). The bitwise AND (key & (numBuckets - 1)) is the standard speed-up for power-of-2 bucket counts.

3. Open addressing with linear probing (alternative)

Single flat array. On collision, walk forward until you find the key or an empty slot.

Time
O(1) average, O(n) worst
Space
O(n)
// Sketch — open addressing requires tombstones for delete to work
// correctly. Cleaner to demo chained buckets in an interview.

Tradeoff: Better cache locality than chained buckets, but delete is tricky (requires tombstones or rehashing on remove). Twilio interviewers prefer chained buckets for clarity; mention this as an alternative when discussing tradeoffs.

Twilio-specific tips

Twilio's bar on Design HashMap is the explicit collision-handling design. State up front: 'I'll use chained buckets with modulo hashing; on collision, walk the bucket linearly.' Don't just code — narrate the load-factor and resize policy. Mentioning that Java's HashMap converts a bucket from linked list to balanced tree when its size exceeds 8 (since JDK 8) is a strong system-design signal.

Common mistakes

  • Using `splice(i, 1)` inside the loop without breaking — works here because of the early return, but a common bug pattern.
  • Forgetting that put() must UPDATE existing values, not just append — the for loop check is mandatory.
  • Using a prime number of buckets without explaining why — primes reduce clustering but for power-of-2 buckets bitwise AND is the win; pick one tradeoff and own it.

Follow-up questions

An interviewer at Twilio may pivot to one of these next:

  • How would you implement rehashing when load factor exceeds a threshold? (Allocate 2x buckets, rehash every entry, swap.)
  • How would you make this thread-safe? (Striped locks — N mutexes, lock per (bucket-index % N).)
  • What's the worst-case complexity of get with adversarial keys? (O(n) if all keys hash to the same bucket — Java's tree-conversion trick keeps it at O(log n).)

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why is the bitwise AND trick (`key & (numBuckets - 1)`) valid?

Because for any power-of-2 N, `key % N === key & (N - 1)`. The lower log2(N) bits encode the modulo, and AND-with-mask extracts them in a single cycle versus a slower modulo instruction.

Should you resize on every insert?

No — resizing is amortized. The standard policy is to resize when n/buckets exceeds a load factor (e.g., 0.75). Each insert is then amortized O(1) because the resize work is distributed across all inserts since the previous resize.

Free learning resources

Curated free links for this problem.

Practice these live with InterviewChamp.AI

Drill Design HashMap and other Twilio interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →