Learn and practice the Hash Maps and Knowing What to Track patterns to solve coding interview problems.

Speedrun the Netflix Coding Interview: Top Problems in C++

Hash maps are powerful data structures that enable programmers to design more efficient solutions for certain problems. After practicing solving problems using hash maps, we will move to the more general problem-solving skill of figuring out the key characteristics of a problem, using various techniques to track them, in order to design remarkably efficient solutions for seemingly complex problems.

Hashing and Tracking

# Statement
Design a **HashMap** data structure that supports the following operations:

*  **Constructor():** Initializes the hash map object with an empty map to store the key-value pairs.

*  **Put(key, value):** Inserts a key-value pair into the hash map. If the specified key is already present in the hash map, the associated value is updated. Otherwise, the key-value pair is added to the hash map.

*  **Get(key):**  Returns the value associated with the specified key if the key exists in the hash map. Otherwise, it returns $-1$, indicating the absence of a mapping for the key.

* **Remove(key):** Removes the entry for the specified key from the hash map, effectively removing both the key and its associated value. This elimination only takes place when the key exists in the hash map.

> **Note:** Your implementation should not utilize the built-in hash table libraries.

**Constraints:**

* $0$ $\le$ `key` $\le$ $10^6$
* $0$ $\le$ `value` $\le$ $10^6$
* At most, $10^4$ calls can be made to the **Put**, **Get**, and **Remove** functions.

# Examples


# Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:



What is the output of the following sequence of function calls on a hash map object?

```text
Put(1, 500)
Put(2, 200)
Put(1, 150)
Get(1)
```

What is the output of the following sequence of function calls on a hash map object?
<pre><code class="language-text">Put(1, 500)
Put(2, 200)
Put(1, 150)
Get(1)
</code></pre>

What is the output of the following sequence of function calls on a hash map object?

```text
Put(2, 500)
Put(3, 100)
Put(3, 450)
Remove(3)
Get(3)
```

What is the output of the following sequence of function calls on a hash map object?
<pre><code class="language-text">Put(2, 500)
Put(3, 100)
Put(3, 450)
Remove(3)
Get(3)
</code></pre>

What is the output of the following sequence of function calls on a hash map object?

```text
Put(1, 100)
Put(3, 450)
Put(1, 100)
Get(4)
Remove(3)
Get(1)
```

What is the output of the following sequence of function calls on a hash map object?
<pre><code class="language-text">Put(1, 100)
Put(3, 450)
Put(1, 100)
Get(4)
Remove(3)
Get(1)
</code></pre>

Design HashMap

Design HashMap

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

## Try it yourself

Implement your solution in `MyHashMap.cpp` and `Bucket.cpp`  in the following coding playground.

#include <iostream>
// A class implementation of the bucket data structure

class Bucket {
public:
	// Initialize bucket here
	Bucket() {}

	// get value from bucket
	int Get(int hashKey) {
		// Write your code here
		return -1;
	}

	// put value in bucket
	void Update(int hashKey, int value) {
		// Write your code here
	}

	// delete value from bucket
	void Remove(int hashKey) {
		// Write your code here
	}
};

#include "Bucket.cpp"


class DesignHashMap {
public:
	// Use the constructor below to initialize the 
    // hash map based on the keyspace
	DesignHashMap() {
		// Write your code here
	}

	void Put(int key, int value) {
		// Write your code here
	}

	int Get(int key) {
		// Replace this placeholder return statement with your code
		return -1;
	}

	void Remove(int key) {
		// Write your code here
	}
};


Help me debug only the function Design HashMap . . I don't need the corrected code.I don't want explanations or code review. Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Please help me understand why this code failed for the last failed test case. Don't give me the corrected code. . If yes, then Just provide me the exact and to-the-point error that helps me run the code successfully on the test cases provided.

Your current task is to review only the Put, Get, Remove function and the other function(s) invoked in it/them. Do not review extra/helper files or functions not invoked in the solution function Put, Get, Remove. Do not review the code of data structures objects instantiated like a binary tree, linked list, trie, union find, etc., in the solution functions. Just review the solution/algorithm function of the problem. Also, Answer the following questions: Is the Hash Maps pattern used? Take your time and review the code.

Please provide a brief time complexity analysis of the function Put, Get, Remove. While calculating time complexity, include the time complexity of built-in C++ functions invoked by the code. The Answer should be to the point and in a few lines.

Please provide a brief Space complexity analysis of the function Put, Get, Remove. While calculating space complexity, include the space complexity of built-in C++ functions invoked by the code. Do not include the space used for the input parameters and the space used for just returning an output(not used as a scratch space). The Answer should be to the point and in a few lines

TwoDArray

#include <string>
#include <iostream>
#include <vector>
#include<sstream>
#include <algorithm>
using namespace std;

class TwoDArray : public DataStructure
{

 // define class attributes

private:
 void generateError(string data)
 {
 cerr << "MyTwoDArray is not parsable: " << data;
 exit(-1);
 }

public:
 std::vector<vector<int>> val;

 TwoDArray()
 {
 // constructor
 }
 TwoDArray(std::vector<vector<int>> v)
 {
 this->val = v;
 // constructor
 }
 
 // return value will be passed to user program
 void *construct(string str, int typeOfDs)
 {
 json j_complete = json::parse(str);
 vector<vector<int>> temp = j_complete;
 this->val = temp;
 // cout << this->val.size();
 return this;
 // parse test case in json string 'value' to your desired data structure
 }

 // input param contains return value of user program
 string traverse(void *input, int typeOfDs)
 {
 return " ";
 // TwoDArray your data structure 'input' to a json string representing a test case output
 }

 // override operator<< for your data structure if required
};

def evaluate_results(self) -> object:
        """
        self.__inputs is the list of inputs that are passed as input to function
        self.__actual_output is a list of outputs that is produced by the learner's code
        return : self.__edu__result object
        """

        class Bucket:
            # Initialize bucket here
            def __init__(self):
                self.bucket = []

            # get value from bucket
            def get(self, key):
                for (k, v) in self.bucket:
                    if k == key:
                        return v
                return -1

            # put value in bucket
            def update(self, key, value):
                found = False
                for i, kv in enumerate(self.bucket):
                    if key == kv[0]:
                        self.bucket[i] = (key, value)
                        found = True
                        break

                if not found:
                    self.bucket.append((key, value))

            # delete value from bucket
            def remove(self, key):
                for i, kv in enumerate(self.bucket):
                    if key == kv[0]:
                        del self.bucket[i]

        class DesignHashMap():
            def __init__(self):
                self.key_space = 2069
                self.buckets = [Bucket()] * self.key_space

            def put(self, key, value): 
                hash_key = key % self.key_space
                self.buckets[hash_key].update(key, value)

            def get(self, key):
                hash_key = key % self.key_space
                return self.buckets[hash_key].get(key)

            def remove(self, key):
                hash_key = key % self.key_space
                self.buckets[hash_key].remove(key)
        
        def main(input2, input3):
            input_hash_map = DesignHashMap()
            keys_list = []
            

            result = []
            result.append(0)
            for i in range(1, len(input2)):
                if input2[i] == "Put":
                    if not input3[i][0] in keys_list:
                        keys_list.append(input3[i][0])
                    input_hash_map.put(input3[i][0], input3[i][1])
                    result.append(0)
                elif input2[i] == "Get":
                    res = input_hash_map.get(input3[i][0])
                    result.append(res)
                elif input2[i] == "Remove":
                    input_hash_map.remove(input3[i][0])
                    result.append(0)
            return result
        
        
        expected_outputs = [] 
        expected = main(self.__inputs[0],self.__inputs[1])
        actual_output = self.__actual_outputs[0]

        if expected == actual_output:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.PASS)
        else:
            expected_outputs.append(expected)
            self.__edu_result.store_result(expected_outputs, TestCaseResult.FAIL)

        return self.__edu_result

#include <iostream>
#include <vector>
#include <queue>
#include "DesignHashMap.cpp"
#include <bits/stdc++.h>
#include "TwoDArray.cpp"
#include <string>
using namespace std;

bool find(vector< int > arr, int target){
	for (int i = 0; i < arr.size(); i++){
		if (arr[i] == target){
			return true;
		}
	}
	return false;
}

vector<int> hashMain( vector<string> input2, TwoDArray input3){

 DesignHashMap input_hash_map = DesignHashMap();
 
 vector<int> keys_list = {};

 vector<int> result = {};
 result.push_back(0);
 for (int i = 1; i < input2.size(); i++){
 if (input2[i] == "Put"){
			if (find(keys_list, input3.val[i][0]) == false){
 keys_list.push_back(input3.val[i][0]);
			}
 input_hash_map.Put(input3.val[i][0], input3.val[i][1]);
 result.push_back(0);
 }
 else if (input2[i] == "Get"){
 int res = input_hash_map.Get(input3.val[i][0]);
 result.push_back(res);
 }
 else if (input2[i] == "Remove"){
 input_hash_map.Remove(input3.val[i][0]);
 result.push_back(0);
 }
	}
 return result;
}

design_hashmap (1).yaml

testcases:
  - name: "testcase 1"
    inputs:
    - 1 : ["DesignHashMap", "Put", "Get"]
    - 2 : [[], [15,250], [15]] 
    output: 
    - 1 : [0,0,250]
  - name: "testcase 2"
    inputs:
    - 1 : ["DesignHashMap", "Get", "Get", "Get", "Remove", "Get"]
    - 2 : [[], [5], [15], [11], [11], [11]] 
    output: 
    - 1 : [0, -1, -1, -1, 0, -1]
  - name: "testcase 3"
    inputs:
    - 1 : ["DesignHashMap", "Get", "Get", "Put", "Get"]
    - 2 : [[], [5], [15], [15, 250], [15]] 
    output: 
    - 1 : [0, -1, -1, 0, 250]
  - name: "testcase 4"
    inputs:
    - 1 : ["DesignHashMap", "Put", "Put", "Get", "Remove", "Get"]
    - 2 : [[], [51, 300], [15, 750], [51], [51], [51]] 
    output: 
    - 1 : [0, 0, 0, 300, 0, -1]
  - name: "testcase 5"
    inputs:
    - 1 : ["DesignHashMap", "Put", "Put", "Get", "Remove", "Get"]
    - 2 : [[], [51, 300], [15, 750], [51], [51], [50]] 
    output: 
    - 1 : [0, 0, 0, 300, 0, -1]

def sum(input_1, input_2):
    return input_1+input_2

def validate_inputs(self) -> None:
 """
 self.__inputs is the list of inputs that are passed as input to function
 store the result using the self.store_result(error_msg, status)
 return : void
 """
 
 def is_valid_1d_array(arr):
 if not isinstance(arr, list):
 return False

 return all(isinstance(elem, str) and not isinstance(elem, bool) for elem in arr)


 def is_valid_2d_array(arr):
 if not isinstance(arr, list) or not all(isinstance(row, list) for row in arr):
 return False

 for row in arr:
 if any(elem is None or isinstance(elem, bool) for elem in row):
 return False
 if not all(isinstance(elem, int) for elem in row):
 return False

 return True


 def key_value(input2):
 for i in input2:
 for j in i:
 if not 0 <= j <= 1000000:
 return False

 return True


 def operation_and_calls_equal(input1, input2):
 for i, op in enumerate(input1):
 if op == "DesignHashMap" and input2[i] != []:
 return False
 elif op == "Put" and len(input2[i]) != 2:
 return False
 elif op == "Get" and len(input2[i]) != 1:
 return False
 elif op == "Remove" and len(input2[i]) != 1:
 return False

 return True


 def operation_valid(input1):
 op = input1[1:]
 for i in range(len(op)):
 if op[i] != "Put":
 if op[i] != "Get":
 if op[i] != "Remove":
 return False
 return True

 input1 = self.__inputs[0]
 input2 = self.__inputs[1]

 if not is_valid_1d_array(input1):
 self.store_result ("'input1' should be a valid 1D array of strings in the following format: ['DesignHashMap','Put','Get'...]", ValidationFunction.FAIL)
 elif not is_valid_2d_array(input2):
 self.store_result ("'input2' should be a valid 2D array of integers in the following format: [[key],[key,value],[key]...]", ValidationFunction.FAIL)
 elif not operation_and_calls_equal(input1, input2):
 self.store_result ("'DesignHashMap', 'Put', 'Get', 'Remove' should be followed by [],[int,int],[int],[int] respectively in the 'input2'", ValidationFunction.FAIL)
 elif len(input1) < 1 or len(input2) < 1:
 self.store_result ("input should not be an empty array", ValidationFunction.FAIL)
 elif len(input1) < 2 or len(input2) < 2:
 self.store_result ("input should have at least one call other than the constructor call", ValidationFunction.FAIL)
 elif not 1 <= len(input2[1:]) <= 10000:
 self.store_result ("'input2' length should be in the range [1,10000]", ValidationFunction.FAIL)
 elif len(input1) != len(input2):
 self.store_result ("'input1' length should be equal to 'input2' length", ValidationFunction.FAIL)
 elif input1[0] != "DesignHashMap":
 self.store_result ("'input1[0]' should have the value: 'DesignHashMap'", ValidationFunction.FAIL)
 elif not operation_valid(input1):
 self.store_result ("'input1[1:]' should have the values 'Get', 'Remove' or 'Put'", ValidationFunction.FAIL)
 elif not key_value(input2):
 self.store_result ("'key' and 'value' should be in the range [0,1000000]", ValidationFunction.FAIL)
 else:
 self.store_result("", ValidationFunction.PASS)

Hash Maps

Knowing What to Track

Conclusion

Design HashMap

Statement

Examples

Understand the problem

Figure it out!

Try it yourself