The data structure, which is just a simple combination of key-value pairs, can be your key to solving majority coding questions!
I recently started with May Leetcode Challenge, and so far almost all the questions that I solved were solved using maps! And that's not it, maps can help you a lot in many tricky situations, especially during coding interviews.
When you are clueless about what to do? just give maps a try it is very likely that you will end up getting a solution. It won't be perfect, it won't be the most memory or time-efficient solution but, you'll get an answer.
This can be the point between getting an offer and not getting an offer!
During my preparation for Amazon Interview, I went through hundreds of interview experience, I did the same during my Google Interview also!
And a whooping, 60%-70% of the questions could be solved using some implementation of maps.
Not only this, but many senior developers, interviewers, and my friends also have suggested Maps as the goto solution when you don't have anywhere to go!
Some reasons why I feel Maps can be really helpful are:
You can access data in O(1) time complexity
Generally, in Tech Interviews there is more focus on minimizing time complexity compared to space. The map is the perfect candidate for this!
Ease of accessing data, as a key can be literally anything!
What is a Map? Understanding it logically
A Map is a data structure in which we can store data in a format of key-value pairs.
To understand it more effectively let's take an example of a hypothetical world. In this imaginary world, every person is associated with a Unique Identification number.
The organization that runs this hypothetical world is very insecure and tracks every person with a GPS, by using the Unique ID (sorry this world doesn't have any concerns about your privacy).
So whenever they need to find any person, they just use the unique ID of that person and boom! They know where he/she is.
As this ID is unique for every person they can find any person within seconds and minimum efforts.
How does it work?
Map stores all the entries in a key-value format in table
| KEY | VALUE |
-----------------------
| 1 | A |
-----------------------
| 2 | B |
-----------------------
| 456 | PQO |
-----------------------
| 789 | A |
Some rules that you must remember
- A key can not be repeated again (It must be unique)
- A value can be repeated many times
- The data type of key must be consistent. For a particular map, all the keys should be either an INT or STRING, etc. (Python Dictionary can have multiple Datatypes as key values, but it is not suggested that you do that)
That is the structure of a map. Whenever a new entry comes it is appended to the table. If the key is already present you can modify the current value.
But, I guess you can do all this with normal arrays and vectors also. Then why do you need a map for this?
Let me ask you some questions.
Does array or vectors have the has_key or find or findKey method?
Can you access the values with an index which is a string, char, object, or struct?
NO! you can not do all this with simple arrays or vectors!
In arrays and vectors data is stored serially so the index range from 0 to n. But, in a map, we define the index so we can access the index in O(1). And the map provides us with a function that can tell us whether a particular exists or not!
This is the biggest USP of Maps!
How to use it?
I'll tell you some basic and important functions related to maps in the C++ language. The key logic behind these functions remains the same only their name and usage changes, so don't worry if your favorite language is JAVA or Python. I'm sure you'll figure it out by using the documentations.
Photo by Kevin Ku on UnsplashLibraries required
#include <bits/stdc++.h> //STL library (SUGGESTED)
OR
#include <map> //Only Map will be included
OR
#include <unordered_map> //Only Unordered Map will be included
- Defining a Map The unordered map also follow a similar process
map<int, string> peopleTracker;
/*
key: int
value: string:
name of map: peopleTracker
*/
- Inserting data elements Inserting Data is very similar to inserting data in an array or vector
peopleTracker[234] = "Mr John Doe";
/*
key: 234 and value:"Mr John Doe"
*/
- Key Collisions Here comes the tricky part, what is the entry already exits? Don't worry you'll simply override the previous Data
peopleTracker[234] = "Mr Dane John";
/*
value changed from "Mr John Doe" -> "Me Dane John"
*/
Now you want to check if there is an entry for some value or not. Here comes the find method!
if(peopleTracker.find(234) != peopleTracker.end())
cout << "Entry for 234 exits" << endl;
mapName.find method will return a pointer to the end of the map if there is no entry with matching key, else it will point to the entry with the corresponding key!
To learn more about maps and hash-table refer to this cheatsheet which was suggested by Trey Huffine.
Now enough of knowledge, its time to practice!
Try to solve these seven problems on Leetcode.
Not all problems can be solved using a map, but figuring out where to use the map is also a skill! So go give your brains some exercise and try to solve these questions!
I hope you'll understand where and how you can use maps and hash tables. With consistent practice, you'll be able to master this data structure.
Once again thank you for reading!
Happy Coding :)
Originally published on Medium.com
Top comments (3)
I think one weakness of maps and sets is that an object can have a hash or compareTo to live in the container but also other members not part of the key. These objects should be searchable, updatable, even key updatable such that they are relocated in the container.
What you have pointed out is somewhat very advanced issue
But my general focus here was how it can help in tech interviewes
Sure, hash is cool, the main cost being the hash function itself. The main variance is whether the bucket is a list to search or if you jump to another bucket on miss with quadratic, linear, double hash. The main control is the initial bucket count. Some hash maps/sets can expand, doubling in bucket count, but cleanup is a challenge, so going big initially is wise. Buckets are often pointers, so 8 bytes each is pretty cheap!
Do you have an opinion about bucket count, like is a prime better than a mod 2 number for randomizing buckets?
The trade off in choosing hash is lookup speed versus lack of ordering. In comparison, a tree or trie allows range search, prefix search, sorted output but a bit slower lookup, tree imbalance vulnerability, a bit more memory cost. Linked list, tree, trie allows no danger of too high a load factor, infinite expansion. All but array have extra overhead to size. Array, vector are fast but expensive to expand, insert, delete, sort. Skip list combines tree and linked list! So many choices!