Last Updated: 31 Jul, 2022
The Food Inspector
Easy
Asked in company
Malay is the food inspector of the Surat district. There are two main shops in the district of Surat namely shop ‘A’ and shop ‘B’, having ‘N’ and ‘M’ number of food products denoted by array ‘ARR1’ and ‘ARR2’ respectively. He has been assigned the task to find the number of edible products with the same name but have different prices in those two main shops of the district based on which he can decide the inflation rate of food products in Surat.
But because there is another big food industry inspection, he doesn’t have time to manually check the prices of every product in both shops, so being his friend he asked you to help him find the count of products with the same name but different prices in both shops.
EXAMPLE :
Input: ‘N’ = 2, ‘M' = 2, ‘ARR1’ = [{“bread”, 10}, {“rice”, 20}], ‘ARR2’ = [{“milk”, 25}, {“rice”, 20}]
Output: 0
In this case, here the only same product in both shops is “rice” and the price is the same in both shops (i.e. 20). Thus there is no product with the same name but at different prices.
Input Format :
The first line will contain the integer ‘T’, the number of test cases.
The first line of each test case contains two integers, ‘N’ and ‘M’ separated by spaces.
Followed by ‘N’ lines, each containing the name of the product ‘foodItem’ and the non-negative integer price of the products ‘P’, denoting the food products of the shop ‘A’.
Followed by ‘M’ lines, each containing the name of the product ‘foodItem’ and the non-negative integer price of the products ‘P’, denoting the food products of the shop ‘B’.
Output format :
For each test case, print the number of food products having the same name but having different prices in shop ‘A’ and shop ‘B’.
Note :
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 10
1 <= ‘N’ <= 10^4
1 <= ‘M’ <= 10^4
It is guaranteed that ‘foodItem’ consists of only lower-case English letters.
It is guaranteed that the length of ‘foodItem’ is less than ‘10’.
It is guaranteed that the name (i.e. ‘foodItem’) of every product in a single shop is distinct.
0 <= ‘P’ <= 10^9
It is guaranteed that sum of the lengths of ‘foodItem’ is <= 10^5.
It is guaranteed that sum of ‘N’ over all test cases is <= 10^4
It is guaranteed that sum of ‘M’ over all test cases is <= 10^4
Time Limit: 1 sec
Approaches
The idea for this approach is to iterate on the products of any shop and try to find a product with the same name in another shop and match their prices.
So we can keep a variable ‘count’, denoting the number of unmatched products price, initially set to 0. Now we iterate on the products of shop ‘A’ (i.e. iterate on the array ‘ARR1’) and for each ‘i’ ∈ ‘[0, N-1]’ we try to find the product in shop ‘B’ (i.e. ‘ARR2’) that has the same name as ‘ith’ product of shop ‘A’ but have different price. If we find such a product in shop ‘B’ we increment the ‘count’ by ‘1’ otherwise if there exists a product with the same name and the same price or product with that name doesn’t exist we move to the next product.
Algorithm:
// The function will return the count of products with the same name and different prices.
Int differentPrices(N, M, ARR1, ARR2)
- Initialize the variable named ‘COUNT’ with the value of ‘0’.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Initialize the variable named ‘prodNameA’ with the value of the first of the pair ‘ARR1[i]’.
- Initialize the variable named ‘prodPriceA’ with the value of the second of the pair ‘ARR1[i]’.
- Run a for loop from ‘0’ to ‘M-1’ with a variable named ‘j’.
- Initialize the variable named ‘prodNameB’ with the value of the first of the pair ‘ARR2[j]’.
- Initialize the variable named ‘prodPriceB’ with the value of the second of the pair ‘ARR2[j]’.
- If ‘prodNameA == prodNameB’
- If ‘prodPriceA == prodPriceB’
- Increment ‘COUNT’ by ‘1’.
- Stop the loop.
- If ‘prodPriceA == prodPriceB’
- Return ‘COUNT’
The idea for this approach is to store the price of products of the shop ‘A’ first and then iterate on the products of shop ‘B’ and match the prices of products with the same name using the previously stored information.
To find the product of the shop ‘A’ with name as their key efficiently we can use a hashmap having string as the key and integer as the value. It is already mentioned in the constraints that all the products of each shop have no duplicate names in their respective shop. All the keys will be distinct in the HashMap.
Now after storing this information, we iterate on the products of shop ‘B’ and first try to find if there exists a product with the same name in the HashMap, and if there exists, we will match the prices and increment the count if they are different. The find operation will be O( 1 ) as the information is stored in a HashMap.
To understand much about HashMap read this article (Introduction to HashMap).
Algorithm:
// The function will return the count of products with the same name and different prices.
Int differentPrices(N, M, ARR1, ARR2)
- Create a HashMap with the name ‘PRODUCTS’ of the type having string-integer as key-value pair.
- Run a for loop from ‘0’ to ‘N-1’ with a variable named ‘i’.
- Insert the string-integer pair of ‘ARR1[i]’ into the HashMap ‘PRODUCTS’.
- Initialize the variable named ‘COUNT’ with the value of ‘0’.
- Run a for loop from ‘0’ to ‘M-1’ with a variable named ‘i’.
- Initialize the variable named ‘prodName’ with the value of the first of the pair ‘ARR2[i]’.
- Initialize the variable named ‘prodPrice’ with the value of the second of the pair ‘ARR2[i]’.
- If the key ‘prodName’ exists in the HashMap ‘PRODUCTS’
- Initialize the variable named ‘PRICE’ with the value of the integer corresponding to the key ‘prodName’ in the HashMap ‘PRODUCTS’.
- If ‘PRICE == prodPrice’
- Increment ‘COUNT’ by ‘1’.
- Return ‘COUNT’.