Design HashMap

Design HashMap is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Design Patterns pattern, in the Design (General/Specific) subpattern.

Problem statement

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 into the HashMap. If the key already exists in the map, update the corresponding value.

- int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

- void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.

Example 1:

Input ["MyHashMap", "put", "put", "get", "get", "put", "get", "remove", "get"] [[], [1, 1], [2, 2], [1], [3], [2, 1], [2], [2], [2]] Output [null, null, null, 1, -1, null, 1, null, -1]

Explanation MyHashMap myHashMap = new MyHashMap(); myHashMap.put(1, 1); // The map is now [[1,1]] myHashMap.put(2, 2); // The map is now [[1,1], [2,2]] myHashMap.get(1); // return 1, The map is now [[1,1], [2,2]] myHashMap.get(3); // return -1 (i.e., not found), The map is now [[1,1], [2,2]] myHashMap.put(2, 1); // The map is now [[1,1], [2,1]] (i.e., update the existing value) myHashMap.get(2); // return 1, The map is now [[1,1], [2,1]] myHashMap.remove(2); // remove the mapping for 2, The map is now [[1,1]] myHashMap.get(2); // return -1 (i.e., not found), The map is now [[1,1]]

Constraints:

- 0 <= key, value <= 106

- At most 104 calls will be made to put, get, and remove.

Topics and companies

Topics: Array, Hash Table, Linked List, Design, Hash Function.

Reported in interviews at Goldman Sachs, Amazon, Microsoft, Apple, LinkedIn, Oracle, Google, ServiceNow, Uber, VMware, ByteDance, eBay.

How to practise Design HashMap on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(1) average for put, get, and remove operations. Each operation hashes the key and traverses a short list (expected constant time with good hash distribution and low load factor). time and O(N + B), where N is the number of unique keys stored and B is the number of buckets (here, 10007). Each key-value pair is stored once, and the bucket array is fixed size. space.

Open Design HashMap in the code editor, or read the Design HashMap editorial for a worked solution with its approach and complexity analysis.

Where Design HashMap sits in the DSA pattern sheet

Problems related to Design HashMap

Other problems that use the same Design (General/Specific) and Design Patterns techniques:

Preparing this workspace.