Skip to main content

8. Design HashMap

easyAsked at Confluent

Implement a HashMap without using built-in map APIs — Confluent uses it to see if you understand bucket chaining, since Kafka's partition assignment is hash-based at heart.

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

Problem

Design a HashMap supporting put(key,value), get(key) returning -1 if absent, and remove(key). Do not use any built-in dictionary or map implementation.

Constraints

  • 0 <= key, value <= 10^6
  • At most 10^4 calls total

Examples

Example 1

Input
put(1,1); put(2,2); get(1)
Output
1

Example 2

Input
put(2,1); put(2,2); get(2)
Output
2

Approaches

1. Direct address array

Allocate an array of size 10^6+1 and index by key.

Time
O(1) per op
Space
O(max_key)
this.a = new Array(1_000_001).fill(-1);
put(k,v){this.a[k]=v}
get(k){return this.a[k]}
remove(k){this.a[k]=-1}

Tradeoff:

2. Bucket chaining

Use a fixed number of buckets indexed by key mod B; each bucket is an array of [key, value] pairs. Linear-scan within a bucket on every op.

Time
O(1) amortized
Space
O(n)
class MyHashMap {
  constructor() { this.B = 1024; this.buckets = Array.from({length: this.B}, () => []); }
  _b(k) { return k % this.B; }
  put(k, v) {
    const bucket = this.buckets[this._b(k)];
    for (const pair of bucket) if (pair[0] === k) { pair[1] = v; return; }
    bucket.push([k, v]);
  }
  get(k) {
    for (const [pk, pv] of this.buckets[this._b(k)]) if (pk === k) return pv;
    return -1;
  }
  remove(k) {
    const b = this.buckets[this._b(k)];
    const i = b.findIndex(p => p[0] === k);
    if (i !== -1) b.splice(i, 1);
  }
}

Tradeoff:

Confluent-specific tips

Confluent will pivot this into Kafka's hash-based partition assignment — bonus signal if you call out that consistent hashing reduces rebalance churn when a consumer joins or leaves the group.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →