Find All Possible Recipes from Given Supplies

Medium

Amazon

7 views

Topics:

GraphsArraysStrings

You are given information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The i<sup>th</sup> recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. A recipe can also be an ingredient for other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

For example:

recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"] Output: ["bread"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour".

recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich","burger"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

How would you approach this problem? What data structures would you use? What is the time and space complexity of your solution? Can you handle edge cases such as cyclic dependencies?

Find All Possible Recipes from Given Supplies

Medium

Amazon

7 views

Topics:

GraphsArraysStrings

You are given information about n different recipes. You are given a string array recipes and a 2D string array ingredients. The i<sup>th</sup> recipe has the name recipes[i], and you can create it if you have all the needed ingredients from ingredients[i]. A recipe can also be an ingredient for other recipes, i.e., ingredients[i] may contain a string that is in recipes.

You are also given a string array supplies containing all the ingredients that you initially have, and you have an infinite supply of all of them.

Return a list of all the recipes that you can create. You may return the answer in any order.

Note that two recipes may contain each other in their ingredients.

For example:

recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"] Output: ["bread"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour".

recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread".

recipes = ["bread","sandwich","burger"], ingredients = [["yeast","flour"],["bread","meat"],["sandwich","meat","bread"]], supplies = ["yeast","flour","meat"] Output: ["bread","sandwich","burger"] Explanation: We can create "bread" since we have the ingredients "yeast" and "flour". We can create "sandwich" since we have the ingredient "meat" and can create the ingredient "bread". We can create "burger" since we have the ingredient "meat" and can create the ingredients "bread" and "sandwich".

How would you approach this problem? What data structures would you use? What is the time and space complexity of your solution? Can you handle edge cases such as cyclic dependencies?

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the data types and possible values for the ingredients in both the recipes and supplies?
If a recipe requires an ingredient that's unavailable, should that recipe still be included in the dependency resolution, potentially leading to no craftable recipes?
If multiple recipes can be crafted, is the order of the returned recipes significant?
Can a recipe require multiple instances of the same ingredient, and if so, how is that represented in the input?
Is there a guarantee that the dependencies among recipes will not create a circular dependency, resulting in an infinite loop?

Brute Force Solution

Approach

We're trying to figure out which recipes we can make given some supplies. The brute force method tries to make every possible recipe and checks if we have all the ingredients for it. If we do, then that recipe is a possibility.

Here's how the algorithm would work step-by-step:

Start with the first recipe.
Check if we have all the ingredients needed for that recipe.
If we do, then we can make it, and we add it to our list of possible recipes.
If we don't, then we can't make it, and we move on to the next recipe.
Repeat this process for every single recipe.
At the end, we'll have a list of all the recipes we can possibly make with the supplies we have.

Code Implementation

def find_all_possible_recipes_brute_force(recipes, ingredients, supplies):
    possible_recipes = []

    for recipe_index in range(len(recipes)): 
        recipe = recipes[recipe_index]
        can_make_recipe = True

        # Iterate through the ingredients needed for the current recipe
        for ingredient in ingredients[recipe_index]:
            if ingredient not in supplies:
                can_make_recipe = False
                break

        # Add recipe if we can make it
        if can_make_recipe:
            possible_recipes.append(recipe)

    return possible_recipes

Big(O) Analysis

Time Complexity

O(r * (i + s)) – Let r be the number of recipes, i be the average number of ingredients per recipe, and s be the number of supplies. The algorithm iterates through each of the r recipes. For each recipe, it checks if all its ingredients are present in the supplies. This check involves, on average, iterating through i ingredients and for each ingredient, checking its presence in the s supplies (we can assume a contains operation takes O(1) or O(s) depending on the data structure used for supplies). Therefore the time complexity for checking one recipe is i+s (assuming efficient lookup in supplies), and since we do this for r recipes, the total time complexity is O(r * (i+s)).

Space Complexity

O(1) – The brute force approach, as described, iterates through the recipes and ingredients. It only requires a few variables to keep track of the current recipe and whether its ingredients are available from the supplies. No auxiliary data structures that scale with the number of recipes or ingredients are created. Therefore, the space used is constant, independent of the input size.

Optimal Solution

Approach

The best way to solve this problem is to figure out which recipes can actually be made given the available supplies. We can achieve this by thinking about the dependencies between the recipes and supplies, and systematically checking which recipes are unlockable.

Here's how the algorithm would work step-by-step:

First, we need to understand which supplies each recipe needs.
Then, we can create a list of recipes that we initially *cannot* make because we are missing ingredients.
We can then repeatedly check if any of those 'unmakeable' recipes *can* now be made because we've obtained the needed supplies (either raw materials or other recipes we've already crafted).
Every time we 'unlock' a new recipe, we add it to our list of available supplies and repeat the checking process.
We continue this process until no new recipes can be made. The recipes we successfully made during this process are our answer.

Code Implementation

def find_all_recipes(recipes, ingredients, supplies):
    recipe_ingredients = {}
    for i in range(len(recipes)): 
        recipe_ingredients[recipes[i]] = ingredients[i]

    unmakeable_recipes = set(recipes)
    available_supplies = set(supplies)
    crafted_recipes = []

    while True:
        newly_crafted = False
        for recipe in list(unmakeable_recipes):
            can_make = True
            for ingredient in recipe_ingredients[recipe]:
                if ingredient not in available_supplies:
                    can_make = False
                    break

            if can_make:
                # If recipe can be made, remove from unmakeable
                unmakeable_recipes.remove(recipe)
                available_supplies.add(recipe)
                crafted_recipes.append(recipe)
                newly_crafted = True
        # Stop if no new recipes are crafted in an iteration.
        if not newly_crafted:
            break

    return crafted_recipes

Big(O) Analysis

Time Complexity

O(n * m) – Let n be the number of recipes and m be the total number of ingredients across all recipes. The algorithm iterates through the recipes (n) to determine which are unmakeable initially. The core of the algorithm involves repeatedly checking if unmakeable recipes can now be made by iterating through their ingredients (m in total, across all recipes). In the worst case, each recipe might depend on the output of every other recipe, leading to potentially checking all recipes multiple times until no further recipes can be produced. The dominant operation is the nested looping between checking recipes and their dependencies so the time complexity can be estimated as O(n * m).

Space Complexity

O(N) – The auxiliary space complexity is determined by the data structures used to store dependencies and track unlockable recipes. We store a list of unmakeable recipes, which in the worst case could contain all N recipes. Furthermore, we might store the supplies needed for each recipe. In the worst case, these structures could hold information proportional to the total number of recipes and ingredients, hence N. Therefore, the auxiliary space complexity is O(N), where N represents the total number of recipes and ingredients.

Edge Cases

Case	How to Handle
Empty recipes or supplies lists	Return an empty list since no recipes can be made.
Recipe requires a supply not in the supplies list	Recipe cannot be made so it should not be included in the output.
Cyclic dependencies between recipes (recipe A needs recipe B, which needs recipe A)	The algorithm needs to detect cycles and avoid infinite loops by using cycle detection (e.g., using topological sort or DFS with visited and recursion stack sets).
Supplies list is extremely large, potentially leading to memory issues.	Consider using a more memory-efficient data structure for storing the supplies, or chunk the processing if the recipes are independent.
Recipe list is extremely large, potentially leading to time out issues	Optimize the algorithm to reduce redundant checks by utilizing efficient graph traversal or memoization techniques.
A recipe requires the same ingredient multiple times, exceeding available supply	The solution must correctly track ingredient counts and ensure that sufficient quantities are available for each recipe.
No recipes can be made from the available supplies.	The algorithm should correctly identify that no recipes can be created and return an empty list.
Recipe ingredient quantities are extremely large and could cause integer overflow issues.	Use appropriate data types (e.g., long) or consider using a modulo operation if applicable, or handle ingredient counts using library functions to prevent overflow.