How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Two Sigma.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Two Sigma during technical interviews.

Implement a Hash Map with Separate Chaining and Resizing

Company: Two Sigma

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a hash map data structure from scratch, without using any built-in hash table types from your language's standard library (no `dict`, `HashMap`, `unordered_map`, `Map`, `set`, etc.). Plain arrays/lists and your own linked-list nodes are allowed. Your hash map must support two operations: - `put(key, value)` — insert the key-value pair. If the key already exists, update its value. - `get(key)` — return the value associated with the key, or `-1` if the key is not present. Design requirements: 1. **Collision handling.** Use a bucket array where each bucket holds a linked list (separate chaining). Multiple keys that hash to the same bucket must all be stored and retrievable correctly. 2. **Dynamic resizing.** Track the load factor (number of stored entries divided by the number of buckets). When an insertion pushes the load factor above `0.75`, grow the bucket array (e.g., double its size) and rehash every existing entry into the new array, so that operations remain average-case $O(1)$. You are given a sequence of operations to process. For every `get` operation, output the returned value. **Example** ``` put(1, 10) put(2, 20) get(1) -> 10 get(3) -> -1 put(2, 30) (update: key 2 now maps to 30) get(2) -> 30 ``` **Constraints** - $1 \le$ number of operations $\le 10^5$ - $0 \le key, value \le 10^9$ - `get` and `put` must run in average-case $O(1)$ time; a full rehash may take $O(n)$ but must be amortized across insertions. - Do not use any built-in hash table / dictionary / map / set container anywhere in your implementation.

Quick Answer: This question evaluates understanding of hash table fundamentals, including hashing, separate chaining collision resolution, linked-list bucket management, dynamic resizing, and rehashing to maintain load factor and amortized performance.

Implement a hash map **from scratch** (no built-in `dict`/`HashMap`/`unordered_map`/`Map`/`set`). Use a bucket array with **separate chaining** (each bucket is a linked list) for collisions, and **dynamic resizing**: when an insert pushes the load factor above `0.75`, double the bucket array and rehash every entry so operations stay average-case O(1). Support two operations: - `put(key, value)` — insert the pair; if the key exists, update its value. - `get(key)` — return the value for `key`, or `-1` if absent. **Driver / I-O format.** You are given `operations`, a list where each element is a triple `[type, key, value]`: - `type == 1` means `put(key, value)`. - `type == 2` means `get(key)` (the third field is unused; pass `0`). Return a list containing the result of **every `get`**, in the order they occur. **Example** ``` put(1, 10) put(2, 20) get(1) -> 10 get(3) -> -1 put(2, 30) # update: key 2 now maps to 30 get(2) -> 30 ``` Encoded as `operations = [[1,1,10],[1,2,20],[2,1,0],[2,3,0],[1,2,30],[2,2,0]]`, the answer is `[10, -1, 30]`.

Constraints

1 <= number of operations <= 10^5
0 <= key, value <= 10^9
operations[i] = [type, key, value] with type in {1 (put), 2 (get)}
get and put must run in average-case O(1) time (amortized rehash)
Do NOT use any built-in hash table / dictionary / map / set container anywhere

Examples

Input: [[1,1,10],[1,2,20],[2,1,0],[2,3,0],[1,2,30],[2,2,0]]

Expected Output: [10, -1, 30]

Explanation: put(1,10), put(2,20). get(1)->10. get(3)->-1 (absent). put(2,30) updates key 2. get(2)->30.

Input: [[1,5,1],[1,5,2],[1,5,3],[2,5,0]]

Expected Output: [3]

Explanation: Repeated puts on the same key overwrite the value; the final get(5) returns the latest value 3.

Input: []

Expected Output: []

Explanation: No operations -> no get results.

Input: [[2,100,0],[2,0,0]]

Expected Output: [-1, -1]

Explanation: Both gets run on an empty map, so each returns -1.

Input: [[1,0,0],[1,1,10],[1,2,20],[1,3,30],[1,4,40],[1,5,50],[1,6,60],[1,7,70],[1,8,80],[1,9,90],[1,10,100],[1,11,110],[1,12,120],[1,13,130],[1,14,140],[1,15,150],[1,16,160],[1,17,170],[1,18,180],[1,19,190],[1,20,200],[1,21,210],[1,22,220],[1,23,230],[1,24,240],[1,25,250],[1,26,260],[1,27,270],[1,28,280],[1,29,290],[2,0,0],[2,29,0],[2,30,0],[2,15,0]]

Expected Output: [0, 290, -1, 150]

Explanation: Inserting 30 keys forces several resizes (load factor crosses 0.75). After rehashing, every stored key is still retrievable: get(0)->0, get(29)->290, get(30)->-1 (never inserted), get(15)->150.

Input: [[1,0,0],[2,0,0],[2,1,0]]

Expected Output: [0, -1]

Explanation: A stored value of 0 must be distinguished from a missing key: get(0)->0 (present), get(1)->-1 (absent).

Input: [[1,1000000000,999999999],[1,8,42],[1,16,43],[1,24,44],[2,1000000000,0],[2,8,0],[2,16,0],[2,24,0],[2,7,0]]

Expected Output: [999999999, 42, 43, 44, -1]

Explanation: Large keys/values and keys 8/16/24 (which collide in the initial 8-bucket array) are all chained and retrieved correctly; get(7) is absent -> -1.

Hints

Keep a bucket array of linked-list heads. For a key, its bucket index is hash(key) % capacity; a good simple hash is (key * 2654435761) % capacity.
On put, walk the bucket's chain first: if the key is already there, overwrite its value; otherwise prepend a new node and increment the size counter.
Track load factor = size / capacity. When an insert makes it exceed 0.75, allocate a new array of double the capacity and rehash every existing node into it (indices change because capacity changed).
get walks the chain of the key's bucket and returns the matching value, or -1 if it reaches the end. Remember a stored value of 0 is different from 'not found' (-1).

Quick Overview

This question evaluates understanding of hash table fundamentals, including hashing, separate chaining collision resolution, linked-list bucket management, dynamic resizing, and rehashing to maintain load factor and amortized performance.