Find All Possible Recipes from Given Supplies Interview Question for Google

You have 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.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

n == recipes.length == ingredients.length
1 <= n <= 100
1 <= ingredients[i].length, supplies.length <= 100
1 <= recipes[i].length, ingredients[i][j].length, supplies[k].length <= 10
recipes[i], ingredients[i][j], and supplies[k] consist only of lowercase English letters.
All the values of recipes and supplies combined are unique.
Each ingredients[i] does not contain any duplicate values.

## Problem: Recipes and Ingredients

We are given a set of recipes, their ingredients, and a list of available supplies. The goal is to determine which recipes can be created given the available supplies and the ability to create other recipes that can then be used as ingredients. This problem can be solved using a graph-like approach and a form of topological sorting.

## Naive Solution (Brute Force)

The most straightforward approach would be to iterate through the recipes repeatedly. In each iteration, check if all ingredients for a recipe are available either directly from supplies or can be created. If a recipe can be created, add it to the supplies. Repeat this process until no new recipes can be created.

```python
def can_make_recipes_naive(recipes, ingredients, supplies):
    can_create = set(supplies)
    created_recipes = []
    changed = True

    while changed:
        changed = False
        for i in range(len(recipes)):
            recipe = recipes[i]
            if recipe in created_recipes:
                continue

            needed_ingredients = set(ingredients[i])
            if needed_ingredients.issubset(can_create):
                can_create.add(recipe)
                created_recipes.append(recipe)
                changed = True

    return created_recipes

# Example Usage
recipes = ["bread", "sandwich"]
ingredients = [["yeast", "flour"], ["bread", "meat"]]
supplies = ["yeast", "flour", "meat"]

print(can_make_recipes_naive(recipes, ingredients, supplies))

Optimal Solution (Topological Sort)

The optimal approach involves a topological sort-like strategy. We can model the recipes and ingredients as a directed graph. Recipes are nodes, and a dependency from an ingredient to a recipe forms an edge. We'll use a queue to keep track of recipes that can be created. Instead of repeated checks, we maintain a count of unmet dependencies for each recipe. When a dependency is met, we decrement the count and enqueue the recipe when the count reaches zero.

from collections import deque

def can_make_recipes_optimal(recipes, ingredients, supplies):
    in_degree = {}
    graph = {}
    for recipe in recipes:
        in_degree[recipe] = 0
        graph[recipe] = []

    supply_set = set(supplies)

    for i in range(len(recipes)):
        for ingredient in ingredients[i]:
            if ingredient not in supply_set:
                in_degree[recipes[i]] += 1
                if ingredient in graph:
                    graph[ingredient].append(recipes[i])
                else:
                    graph[ingredient] = [recipes[i]]

    queue = deque([recipe for recipe in recipes if in_degree[recipe] == 0])
    result = []

    while queue:
        recipe = queue.popleft()
        result.append(recipe)

        for dependent_recipe in graph.get(recipe, []):
            in_degree[dependent_recipe] -= 1
            if in_degree[dependent_recipe] == 0:
                queue.append(dependent_recipe)

    return result

# Example Usage
recipes = ["bread", "sandwich"]
ingredients = [["yeast", "flour"], ["bread", "meat"]]
supplies = ["yeast", "flour", "meat"]

print(can_make_recipes_optimal(recipes, ingredients, supplies))

Big(O) Run-time Analysis

Naive Solution

Time Complexity: O(n * m * k), where n is the number of recipes, m is the number of iterations needed to create all recipes, and k is the maximum number of ingredients for a recipe. This is because, in the worst case, we may have to iterate through all recipes multiple times, and for each recipe, we check all its ingredients.

Optimal Solution

Time Complexity: O(n + i), where n is the number of recipes and i is the total number of ingredients across all recipes. We iterate through each recipe and its ingredients once to build the graph and calculate in-degrees. The topological sort then processes each recipe and ingredient dependency once.

Big(O) Space Usage Analysis

Naive Solution

Space Complexity: O(n), where n is the number of recipes, to store the can_create set and the created_recipes list.

Optimal Solution

Space Complexity: O(n + i), where n is the number of recipes and i is the number of unique ingredients. This is due to the space required to store the in_degree dictionary and the adjacency list (graph).

Edge Cases

Circular Dependencies: If recipes depend on each other in a cycle (e.g., A needs B, and B needs A), the naive approach might loop indefinitely. The optimal approach, using topological sort, will detect this since not all nodes will be visited, and the algorithm terminates correctly.
Empty Input: If the recipes list is empty, the algorithm should return an empty list.
No Supplies: If the supplies list is empty, and no recipe can be made from nothing, the algorithm should return an empty list.
Duplicate Ingredients: The problem states that each ingredients[i] does not contain any duplicate values, but the algorithm must still handle possible duplicate ingredients from the supplies list.

Example with Diagram

Let's consider the example:

`recipes = [