# Very Intesresting Que : Given dishes and its ingredients. Group dishes that has common ingredients

• E.g:
Input:
"Pasta" -> ["Tomato Sauce", "Onions", "Garlic"]
"Chicken Curry" --> ["Chicken", "Curry Sauce"]
"Fried Rice" --> ["Rice", "Onions", "Nuts"]

Follow up: What is the time and space complexity?

• This is an interesting yet simple question. I was trying to use 'sets' to compare intersections. I'm guessing the input is a hashmap.
EDIT: I guess using sets was not the best idea. I create additional dictionary:

``````def group_items(mydict):

d2 = collections.defaultdict(list)
for k, v in mydict.iteritems():
for name in v:
d2[name].append(k)

out = [i for i in map(tuple, d2.values()) if len(i) > 1]
return out

mydict = {"Pasta":["Tomato Sauce", "Onions", "Garlic"], "Chicken Curry":["Chicken", "Curry Sauce"], \
"Fried Rice":["Rice", "Onions", "Nuts"], "Salad":["Spinach", "Nuts"],

print group_items(mydict)

``````

output:

``````[('Sandwich', 'Quesadilla'), ('Salad', 'Fried Rice'), ('Chicken Curry', 'Quesadilla'), ('Fried Rice', 'Pasta')]
``````

• Assuming the input is map, following java code solves the problem. Complexity will be O(n^2) as each item needs to iterated over at least once. I simply invert the map from a dish->List<Ingredients> to Ingredient -> List<Dishes> .

``````static void printDishesWithCommonIngredients(Map<String, String[]> dishIngredientsMap)
{
Map<String, Set<String>> invertedMap = new HashMap<String, Set<String>>();
for (String dish : dishIngredientsMap.keySet())
{
String[] ingredients = dishIngredientsMap.get(dish);
for (String ing : ingredients)
{
if (invertedMap.containsKey(ing))
{
}
else
{
Set<String> dishSet = new HashSet<String>();
invertedMap.put(ing, dishSet);
}
}
}
for (Set<String> dishes : invertedMap.values())
{
if (dishes.size() > 1)
System.out.println(Arrays.toString(dishes.toArray()));
}
}
``````

• Similar to modqhx, basically creating an inverse dictionary and printing out values from it which are greater than 1 ingredient. So running complexity should be O(n) since we are running through each value (of each key) only once while creating a dictionary of equivalent size. So space will be O(n) as well?

``````d = { "pasta":          ["Tomato Sauce", "Onions", "Garlic"],
"Chicken Curry":  ["Chicken", "Curry Sauce"],
"Fried Rice" :    ["Rice", "Onions", "Nuts"],

def group_by_ingredients(d):
d2 = {}
for k,v in d.iteritems():
for x in v:
d2.setdefault(x,[]).append(k)
for k,v in d2.iteritems():
if len(v) > 1:
print v
``````

=============

``````>>> d
{'Chicken Curry': ['Chicken', 'Curry Sauce'], 'Sandwich': ['Cheese', 'Bread'], 'Salad': ['Spinach', 'Nuts'], 'Quesadilla': ['Chicken', 'Cheese'], 'Fried Rice': ['Rice', 'Onions', 'Nuts'], 'pasta': ['Tomato Sauce', 'Onions', 'Garlic']}

>>> group_by_ingredients(d)
['Fried Rice', 'pasta']
``````

• @dhawalverma got something similar:

``````public void group(Map<String, String[]> map) {

Map<String, Set<String>> invertedMap = new HashMap<>();
for (Map.Entry<String, String[]> entry : map.entrySet()) {
for (String ingredient : entry.getValue()) {