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

  • 0

    "Pasta" -> ["Tomato Sauce", "Onions", "Garlic"]
    "Chicken Curry" --> ["Chicken", "Curry Sauce"]
    "Fried Rice" --> ["Rice", "Onions", "Nuts"]
    "Salad" --> ["Spinach", "Nuts"]
    "Sandwich" --> ["Cheese", "Bread"]
    "Quesadilla" --> ["Chicken", "Cheese"]

    Output: ("Pasta", "Fried Rice") ("Fried Rice, "Salad") , ("Chicken Curry", "Quesadilla") ("Sandwich", "Quesadilla")

    Follow up: What is the time and space complexity?

  • 0

    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:
        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"],
              "Sandwich" : ["Cheese", "Bread"], "Quesadilla" : ["Chicken", "Cheese"] }
    print group_items(mydict)


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

  • 0

    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))
    					Set<String> dishSet = new HashSet<String>();
    					invertedMap.put(ing, dishSet);
    		for (Set<String> dishes : invertedMap.values())
    			if (dishes.size() > 1)

  • 1

    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"],
          "Salad" :         ["Spinach", "Nuts"],
          "Sandwich" :      ["Cheese", "Bread"],
          "Quesadilla" :    ["Chicken", "Cheese"] }
    def group_by_ingredients(d):
         d2 = {}
         for k,v in d.iteritems():
              for x in v:
         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)
    ['Sandwich', 'Quesadilla']
    ['Salad', 'Fried Rice']
    ['Chicken Curry', 'Quesadilla']
    ['Fried Rice', 'pasta']

  • 0

    @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()) {
    	      invertedMap.computeIfAbsent(ingredient, v -> new HashSet<String>()).add(entry.getKey());
    	for (Set<String> dishSet : invertedMap.values()) {
    	   if (dishSet.size() > 1) System.out.println(dishSet);

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.