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


  • -1
    Z

    E.g:
    Input:
    "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
    M

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

    output:

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

  • 0
    D

    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))
    				{
    					invertedMap.get(ing).add(dish);
    				}
    				else
    				{
    					Set<String> dishSet = new HashSet<String>();
    					dishSet.add(dish);
    					invertedMap.put(ing, dishSet);
    				}
    			}
    		}
    		for (Set<String> dishes : invertedMap.values())
    		{
    			if (dishes.size() > 1)
    				System.out.println(Arrays.toString(dishes.toArray()));
    		}
    	}
    

  • 1
    T

    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:
                   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)
    ['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.