In data structures, hashing is a technique for mapping a large amount of data into small tables using a hashing function. It is also referred to as the message digest function. It is a technique for distinguishing one item from a group of similar items.
It stores data in an array format using hash tables. Each value in the array has its index number. Hash tables employ a technique to generate these unique index numbers for each value stored in an array format. This is known as the hash technique.
Rather than finding the data, you only need to find the index of the desired item. Indexing lets you quickly scan the entire list and retrieve the item you want. Indexing is also useful in inserting operations when inserting data at a specific location. You can update and retrieve data in seconds, no matter how large or small the table is.
Let's solve one problem of minimum index sum for common elements of two lists using hashing.
Minimum Index Sum for Common Elements of Two Lists using hashing.
This means we have to find the common elements in both lists given to us.
The goal is to try all index sums ranging from 0 to the sum of sizes. Check for pairs with the given sum for each sum. We print and return once we find one or more pairs.
Example
Given below is the cartoon names given in two lists.
Minimum Index Sum for Common Elements of Two Lists using hashing example:
Explanation: Tom&Jerry is the only common cartoon in the two list
Algorithm
Take the two lists as input values.
Declare the map as well as a vector.
Insert the list 1 values into the map using their indexes.
Check if the element from list 2 is present in the map and set the minimum to the maximum value of the integer.
If found, add the sum of the current index and the found element index to the sum and save it.
If the min is less than the sum, store the sum into a minimum.
Remove the new element from the resultant vector.
If the sum equals the minimum, just add the value to the resultant vector.
We'll get our answer if we print the output vector.
Explanation
Implementation In C++💻
/*
Minimum Index Sum for Common Elements of Two Lists using hashing.
*/
#include<bits/stdc++.h>
#include<unordered_map>
#include<vector>
using namespace std;
void getCartoonString(vector<string> list1, vector<string> list2)
{
unordered_map<string, int> map;
for (int index = 0; index < list1.size(); index++)
map[list1[index]] = index;
vector<string> print;
int minimum = INT_MAX;
for (int j = 0; j < list2.size(); j++)
{
if (map.count(list2[j]))
{
int sum = j + map[list2[j]];
if (sum < minimum)
{
minimum = sum;
print.clear();
print.push_back(list2[j]);
}
else if (sum == minimum)
print.push_back(list2[j]);
}
}
for (int i = 0; i < print.size(); i++)
cout <<"Common name in both the list is:\n"<<" "<< print[i] << " ";
}
int main()
{
string s;
vector<string> commonThings1;
int i=0;
cout<<"Enter cartoon names in the list 1:\n";
while(i<5)
{
getline(cin,s);
commonThings1.push_back(s);
i++;
}
vector<string> commonThings2;
int j=0;
cout<<"Enter cartoon names in the list 2:\n";
while(j<5)
{
getline(cin,s);
commonThings2.push_back(s);
j++;
}
getCartoonString(commonThings1, commonThings2);
return 0;
}
You can also try this code with Online C++ Compiler
/*
Minimum Index Sum for Common Elements of Two Lists using hashing.
*/
import java.util.HashMap;
import java.util.Vector;
import java.util.Scanner;
public class codingNinjas
{
public static void getCommonString(Vector<String> list1, Vector<String> list2)
{
Vector<String> print = new Vector<String>();
HashMap<String, Integer> map = new HashMap<>();
for (int index = 0; index < list1.size(); index++)
map.put(list1.get(index), index);
int minimum = Integer.MAX_VALUE;
for (int a= 0; a< list2.size(); a++)
{
if (map.containsKey(list2.get(a)))
{
int sum = a+ map.get(list2.get(a));
if (sum < minimum)
{
minimum = sum;
print.clear();
print.add(list2.get(a));
}
else if (sum == minimum)
print.add(list2.get(a));
}
}
for (int i = 0; i < print.size(); i++)
System.out.println("Common name in both the list is:\n "+print.get(i) + " ");
}
public static void main(String[] args)
{
Vector<String> commonThings1 = new Vector<String>();
Scanner myObj = new Scanner(System.in);
System.out.println("Enter cartoon names in the list 1:\n");
String first = myObj.nextLine();
String second = myObj.nextLine();
String third = myObj.nextLine();
String fourth = myObj.nextLine();
String fifth = myObj.nextLine();
System.out.println("Enter cartoon names in the list 2:\n ");
String first_1 = myObj.nextLine();
String second_2 = myObj.nextLine();
String third_3 = myObj.nextLine();
String fourth_4 = myObj.nextLine();
String fifth_5 = myObj.nextLine();
commonThings1.add(first);
commonThings1.add(second);
commonThings1.add(third);
commonThings1.add(fourth);
commonThings1.add(fifth);
Vector<String> commonThings2 = new Vector<String>();
commonThings2.add(first_1);
commonThings2.add(second_2);
commonThings2.add(third_3);
commonThings2.add(fourth_4);
commonThings2.add(fifth_5);
getCommonString(commonThings1, commonThings2);
}
}
You can also try this code with Online Java Compiler
# Minimum Index Sum for Common Elements of Two Lists using hashing.
import sys
def find(list1, list2):
Map = {}
for i in range(len(list1)):
Map[list1[i]] = i
res = []
minsum = sys.maxsize
for j in range(len(list2)):
if list2[j] in Map:
Sum = j + Map[list2[j]]
if (Sum < minsum):
minsum = Sum
res.clear()
res.append(list2[j])
elif (Sum == minsum):
res.append(list2[j])
print(*res, sep = " ")
list1 = []
list1.append(input("Enter 5 cartoons:"))
list1.append(input())
list1.append(input())
list1.append(input())
# Creating list2
list2 = []
list2.append(input("\nEnter 5 more cartoons:"))
list2.append(input())
list2.append(input())
list2.append(input())
find(list1, list2)
You can also try this code with Online Python Compiler
O(l*x) is the, where ‘x’ is the length of the resultant list used to store the result.
'l’ is the maximum string length.
Frequently Asked Questions🤔
What is hashing, explain with an example?
Hashing is intended to solve the problem of efficiently finding or storing an item in a collection. For example, if we have a list of 10,000 English words and want to see if a specific word is on the list, it would be inefficient to compare the word with all 10,000 items until we find a match.
What is a hash key in a data structure?
A hash table is a data structure used to store key-value pairs. A hash function is used to perform arithmetic operations on the key. The output (also known as the hash value or hash) is the index of the key-value pair in the hash table.
What is the need for hashing?
Compared to other data structures, hashing provides a more secure and adjustable method of retrieving data. It is faster than looking for lists and arrays. In the extreme range, hashing can recover data saved in a tree in 1.5 probes.
What is a list?
A list is an ordered data structure that contains elements separated by commas and enclosed in square brackets.
Describe the differences between a map and a set.
While a map provides an interface for storing key-value pairs, a set is a collection of data that cannot contain duplicate entries.
Conclusion
In this blog, we went through the solution to the problem statement, the minimum index sum for common elements of two lists problem, including the algorithm and the implementation using hashmap in different languages.
117+ registered 