I am new to programming and I just came across this question. Now I started by using dictionary in python and then I got stuck, So how can I solve this? Please help me.
Given a list of pairs . Each pair contains a food item and its price, for ex: (apple, 120), (banana,200)… and so on. Specific food item may occur multiple times, for ex: (apple,200), (apple,280)… so on.
For each food item output the lowest, highest and average price(rounded down to nearest integer) for that item. The output list should be lexicographically (alphabetically) sorted by name of food.
Input:
first line contains one integer T i.e. no of test cases.
second line contains one integer N i.e. no of pair of fruits
next N line contains pair of fruits.
Output:
Output of result should be in following format:
case #i:
where i is the index of text case, starting from 1. Then for each test case output is one line format :
food item, its lowest price, its highest price, its average price
and output list of food items must be sorted item name in lexicographically order.
You can have a look at the default dict module in Python however you can solve this problem in C++ very easily using std :: map<string, std :: vector<int>>.
Use a dictionary with value as list and append the prices into it. Then you can manipulate it accordingly for finding the max min and average. Hope it helps!
Can you please explain it through a code?
And I am sorry I can’t give you the link because I came across this question when I was taking a test and now that test’s link is no more active.
Actually the main problem arouse when it is asked to display result in alphabetical order. So, how can I compare keys of same dict.
So can you please help me out with this?
Moreover, in this approach time complexity is not so favourable.
As mentioned earlier, you can solve the problem using all the different variants of dict container present in python i.e. dict, defaultdict, ordereddict.
Following code is the solution using defaultdict as it has some advantages over dict container i.e. it doesn’t raise KeyError when there is no value associated to the key rather it initialises the key with a default value which in this case is an empty list.
I suggest you read about the complete collections module through the following links:
from collections import defaultdict
def main():
for test in range(int(input().strip())):
fruit_prices = defaultdict(list) # Creating a defaultdict object by specifying the dafault value with which it should be intitialised with i.e. list.
"""
Creation of dictionary from the user-input.
"""
for _ in range(int(input().strip())):
fruit_price_pair = tuple(input().strip().split())
fruit_prices[fruit_price_pair[0]].append(int(fruit_price_pair[1]))
"""
Updating the dictionary according to what is asked in the problem statement.
"""
for fruit_name, price in fruit_prices.items():
fruit_prices[fruit_name] = [min(price), max(price), sum(price) // len(price)]
"""
Sorting the dictionary by keys using sorted().
NOTE: Do remember that, sorted() function returns a list of values which in this case is list of tuples. But if you convert the sorted list back to the dictionary object then sorted order will not remain same as dictionary stores data in an un-ordered fashion.
"""
fruit_prices = sorted(fruit_prices.items())
"""
Printing the data as suggested in the problem statement.
"""
print(f"Case #{test + 1}:")
for fruit_name, price_list in fruit_prices:
print(f"{fruit_name} {' '.join(map(str, price_list))}")
if __name__ == "__main__":
main()
Solution In C++
#include <iostream>
#include <array>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <string>
#include <numeric>
#include <algorithm>
#include <cmath>
#include <cstdio>
typedef unsigned long long ull_t;
typedef long long ll_t;
#define FAST_IO(value) std :: ios :: sync_with_stdio(value); std :: cin.tie(NULL)
#define MOD 1000000007 // Constant (prime number) used in most competitive programming problems to reduce the answer to a 32-bit integer.
#define PI 3.141592653589793 // Number of digits(15) of Pi which JPL uses for Interplanetary Caculations.
#define GOLDEN_RATIO 1.618033988749895 // Number of digits(15).
static void solve_problem(const std :: map <std :: string, std :: vector <int>> &);
int main(void) {
FAST_IO(0);
int test;
std :: cin >> test;
for(int t = 1; t <= test; ++t) {
int n;
std :: cin >> n;
std :: map <std :: string, std :: vector <int>> food_info;
for(int i = 0; i < n; ++i) {
std :: string food_name;
int food_price;
std :: cin >> food_name >> food_price;
food_info[food_name].push_back(food_price);
}
std :: cout << "Case #" << t << ":" << std :: endl;
solve_problem(food_info);
}
return 0;
}
static void solve_problem(const std :: map <std :: string, std :: vector <int>> & food_info) {
for(auto itr = food_info.begin(); itr != food_info.end(); ++itr) {
std :: cout << itr->first;
int min_val = *std :: min_element(itr->second.begin(), itr->second.end());
std :: cout << " " << min_val;
int max_val = *std :: max_element(itr->second.begin(), itr->second.end());
std :: cout << " " << max_val;
int avg_val = std :: accumulate(itr->second.begin(), itr->second.end(), 0) / itr->second.size();
std :: cout << " " << avg_val << std :: endl;
}
}
Ordered Dictionary doesn’t sorts the key, read the article carefully. Ordered Dictionary stores the keys in the same order in which they are inserted.
Moreover, in C++ the keys of the <map> container are sorted according to the key but not in the case of Python.
Internally, the elements in a map are always sorted by its key following a specific strict weak ordering criterion indicated by its internal comparison object (of type Compare).