Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures

# Introduction
Before solving any challenges regarding Hash Tables, it is necessary to look at the implementations of **`unordered_map`**, and **`unordered_set`** and see how they are different. Both are implemented in C++ STL. It is also a common misconception that these two structures are the same, but they are very different from each other.

 ## 🔍 `unordered_map`
`unordered_map` is a container which is implemented using the **Map** interface. It stores an element in the form of `key-value` pairs; it *maps* the values to keys. 

It provides the basic functionality of hashing along with some helper functions that help in the process of insertion, deletion, and search.

Some of the key features of `unordered_map` are given below:

- An `unordered_map` stores `key-value` pairs (examples given below) to map a key to the value:  
$$abc->123$$
$$ xyz->456$$

- `unordered_map` cannot contain duplicate keys. It can, however, have duplicate values. 

* `unordered_map` does not store elements in any order either by the `key` or the `value`.

* `unordered_map` uses a hash table for its implementation. It takes the key and then maps it into the range of hash table using the hash function.

- On average, the complexity of the basic operation is $O(1)$.  It will go up to $O(n)$ in the worst-case.



# 🔍 `unordered_set`
`unordered_set` is a container in C++ which is implemented using the **Set** interface. It is also built in the same way as `unordered_map`, i.e., using the Hash Table, but it is still quite different from the `unordered_map`. 

Some of the key features of `unordered_set` are listed below:


- `unordered_set` is a container that implements the `Set` interface, and this interface only stores values, not a `key-value` pair. The `value` of an element will be its `key` at the same time.

$$1->1$$
$$abc->abc$$




- `unordered_set` does not allow storing duplicate elements as a **set** can only contain unique elements.

* On average, the complexity of the basic operation is $O(1)$.  It will go up to $O(n)$ in the worst-case.

# Member Functions

Some of the commonly used member functions of `unordered_map` and `unordered_set` are given below:
| Function    |  Definition   |
| --- | --- |
| `end()`    | Returns an iterator that is pointing to the position following the last element of the container    |
|  `erase(iterator/key)`   |  Remove the element pointed by the iterator/ corresponding to the given key   |
| `find(key)`    |  Search element with the given key. If the element is present, it will return an iterator to it. If not, it will return an iterator to the `end`   |
|  `insert(key)` / `insert(key,value)`  |  Insert new element in the container. It does not insert element with duplicate key in the container|
---



This lesson will discuss the difference between unordered_map and unordered_set and look at some of their key features. 

unordered_map vs unordered_set

Introduction