Day 17 of 30 days of Data Structures and Algorithms and System Design Simplified — Hash Table/Hashing
Welcome back peeps. Hope all’s well. In this post we will cover Hash Table follows —
What and Why Hash Table(in 2–3 sentences)?
How does hash table work?
Important Patterns and Techniques in Hash Table Questions
Most Important Questions with Solutions
Tips and Techniques to solve Hash Table Questions Fast.
Complete Data Structures and Algorithm Series
Github —
Projects Videos —
All the projects, data structures, SQL, algorithms, system design, Data Science and ML , Data Analytics, Data Engineering, , Implemented Data Science and ML projects, Implemented Data Engineering Projects, Implemented Deep Learning Projects, Implemented Machine Learning Ops Projects, Implemented Time Series Analysis and Forecasting Projects, Implemented Applied Machine Learning Projects, Implemented Tensorflow and Keras Projects, Implemented PyTorch Projects, Implemented Scikit Learn Projects, Implemented Big Data Projects, Implemented Cloud Machine Learning Projects, Implemented Neural Networks Projects, Implemented OpenCV Projects,Complete ML Research Papers Summarized, Implemented Data Analytics projects, Implemented Data Visualization Projects, Implemented Data Mining Projects, Implemented Natural Leaning Processing Projects, MLOps and Deep Learning, Applied Machine Learning with Projects Series, PyTorch with Projects Series, Tensorflow and Keras with Projects Series, Scikit Learn Series with Projects, Time Series Analysis and Forecasting with Projects Series, ML System Design Case Studies Series videos will be published on our youtube channel ( just launched).
Subscribe today!
System Design Case Studies — In Depth
Design Instagram
Design Messenger App
Design Twitter
Design URL Shortener
Design Dropbox
Design Youtube
Design API Rate Limiter
Design Web Crawler
Design Facebook’s Newsfeed
Design Yelp
Design Uber
Design Tinder
Design Tiktok
Design Whatsapp
Most Popular System Design Questions
Mega Compilation : Solved System Design Case studies
Hash Table
Importance : High
Note : New Hash Table questions with solutions are added every day. So keep checking this post daily.
Let’s dive in!
What is Hash Table?
Hash Tables are data structures which use associative method to store data in the form of key — value pair. Keys are mapped to the unique values.
The key — value pairing makes the data organization and access very efficient. Each unique key is mapped to a value; thus makes the access a constant operation O(1) .
Hash Tables are very efficient and fast.
Examples of Hash Table problems —
Two Sum
Next greater Element
Peak Element
Subarray Sum
4Sum
Increasing Subsequences etc
How does Hash Table work?
A hash table works by taking the key of the element you want to add or find, running it through a hash function, which produces an index in the table where the value is stored. When searching for a value, the key is run through the same hash function to find the index where the value is stored.
Hashing is a technique which converts a collection of key values to key indexes which are mapped to values. Unique indexes or keys are generated by using modulo operator i.e hash function.
key % SIZELinear probing is one the most popular hashing technique which is used to search the next empty location in the list by traversing through the next cells.
Important Patterns and Techniques in Hash Table Questions
Important patterns and techniques in hash table questions include understanding the basic operations of a hash table (put, get, and delete), handling collisions (chaining, open addressing), and analyzing the time and space complexity of different hash table implementations.
Hash tables are generally used in the questions/solutions —
- Involving dictionaries
- Duplicate in the array
- Find unique target sum
- Index by keys
- Binary Tree questions etc.
Patterns → Questions like below belong to Hash Table( not limited to):
Find duplicates
Find unique characters/count
Majority Element
Two Sum
Next greater Element
Peak Element
Subarray Sum
4Sum
Increasing Subsequences etc
Most Important Questions with Solutions
Note : New Hash Table questions with solutions are added every day. So keep checking this post daily.
Golden rule is — Learn by doing/implementing
In this we will see most important Hash Table questions.
Two Sum
Question —
Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example :
Input: nums = [2,7,11,15], target = 9
Output: [0,1]Solution :
Main Logic/Idea —
The main logic is to map values to the index in the hashmap. Values are calculated by subtracting the element by the target element in each iteration. If the target is found, then return the index of the element and corresponding index of the difference found in the hashmap.
Implementation —
def twoSum(self, nums: List[int], target: int) -> List[int]:
res = {}
for index, num in enumerate(nums):
ans = target - num
if ans in res:
return [res[ans],index]
res[num] = index
returnQuestion Link
Similar Pattern —
Count Number of Pairs With Absolute Difference K
Number of Pairs of Strings With Concatenation Equal to Target
Find All K-Distant Indices in an Array
Check Distances Between Same Letters
Two Sum III — Data structure design
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
First Unique Character in a String
Question —
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example :
Input: s = "leetcode"
Output: 0Solution :
Main Logic/Idea —
The main logic is — map character to its count in the given string. Keep iterating the list and check if the character is already present in the hashmap or not. If present then increment the count else add the character and give the count as 1. Once done iterate through the hashmap and return the index of that element where the count is 1. If not found, then return -1.
Implementation —
def firstUniqChar(self, s: str) -> int:
l={}
for i in s:
if i not in l:
l[i]=1
else:
l[i]+=1
for t,v in l.items():
if v == 1:
return s.index(t)
return -1Question Link
Similar Pattern —
Full Code Video Explanation ( In progress. Subscribe today for updates) :
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
Next Greater Element I
Question —
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example :
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]Solution :
Main Logic/Idea —
The main logic is to add the elements from num2 and see if there’s same element is nums1. If there’s an element in nums1 take its index and store it in the ans array after checking if there’s any corresponding greater element in nums2.
Implementation —
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
nIndx = {no:index for index,no in enumerate(nums1)}
ans = [-1] * len(nums1)
stck = []
for i in range(len(nums2)):
curr = nums2[i]
while stck and curr > stck[-1]:
val = stck.pop()
ix = nIndx[val]
ans[ix] = curr
if curr in nIndx:
stck.append(curr)
return ansQuestion Link
Similar Pattern —
Sum of Total Strength of Wizards
Full Code Video Explanation ( In progress. Subscribe today for updates) :
Note : New Hash Table questions with solutions are added every day. So keep checking this post daily.
Complexity Analysis
Read complexity analysis post before calculating hash table complexity.
Assuming that time to compute hash functions is constant. The complexity of hash table —
Search : O(1)
Insert : O(1)
Delele : O(1)
Tips and Techniques to solve Hash Table Questions Fast.
Remember, the main gist of hash table is key and value pairing.
So, before solving the hash table related questions; learn how to —
- Insert/delete/access the indexes in the dictionaries and hash set.
- Know how to implement two pointers technique.
- Know how to implement sliding window technique.
- Know how to implement hash set.
That’s it for now. Day 18 : Trees coming soon !
Let me know if you have questions in the comment section below. Subscribe/ Follow, Like/Clap as it will encourage me to write more in my free time and Stay Tuned!!
Read More —
11 most important System Design Base Concepts
6. Networking, How Browsers work, Content Network Delivery ( CDN)
13. System Design Template — How to solve any System Design Question
Some of the other best Series —
30 days of Data Structures and Algorithms and System Design Simplified
Data Science and Machine Learning Research ( papers) Simplified **
100 days : Your Data Science and Machine Learning Degree Series with projects
Complete Data Visualization and Pre-processing Series with projects
Exceptional Github Repos — Part 1
Exceptional Github Repos — Part 2
Tech Newsletter —
If you are interested, you can join my newsletter through which I send tech interview tips, techniques, patterns, hacks — Software Development, ML, Data Science, Startups and Technology projects to more than 30K readers. You can subscribe to Tech Brew :
For Python Projects —
For complete 60 days of Data Science and ML : Day 1 — Day 60 : Quick Recap of 60 days of Data Science and ML
Follow for more updates. Stay tuned and keep coding!
For other projects, tune to —
Build Machine Learning Pipelines( With Code)
Recurrent Neural Network with Keras
Clustering Geolocation Data in Python using DBSCAN and K-Means
Facial Expression Recognition using Keras
Hyperparameter Tuning with Keras Tuner
Custom Layers in Keras
