Which Recipes Can Be Made When Ingredients Can Themselves Be Recipes
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A kitchen has an unlimited stock of some basic supplies and a book of recipes. Each recipe has a unique name and a list of ingredients. An ingredient may be a basic supply, the name of another recipe in the book, or something the kitchen does not have. A dish made from one recipe can be used as an ingredient in other recipes: for example, a cake may need a sponge and a frosting, each of which has its own recipe.
Return the names of all recipes the kitchen can make, in ascending order.
### Function Signature
```python
def makeable_recipes(recipes: list[str], ingredients: list[list[str]], supplies: list[str]) -> list[str]:
```
`recipes[i]` is the name of the `i`-th recipe, and `ingredients[i]` lists the ingredients it needs. `supplies` lists the basic supplies, each available in unlimited quantity.
### Rules
- Quantities do not matter: once a recipe has been made, it can serve as an ingredient for any number of other recipes.
- Recipes are made one at a time. A recipe can be made when each of its ingredients is either a basic supply or a recipe that has already been made.
- An ingredient that is neither a basic supply nor a recipe name can never be obtained, so a recipe that needs it, directly or through other recipes, cannot be made.
- Consequently, recipes that need one another in a cycle can never be made.
- Return every recipe that can be made in some sequence, sorted in ascending lexicographic order. Return `[]` if no recipe can be made.
### Constraints
- `1 <= len(recipes) == len(ingredients) <= 1000`
- `1 <= len(ingredients[i]) <= 100`
- `0 <= len(supplies) <= 1000`
- Every name (recipe, ingredient or supply) consists of 1 to 10 lowercase English letters.
- Recipe names are distinct, supply names are distinct, and no name is both a recipe and a supply.
- The entries of each `ingredients[i]` are distinct, and `ingredients[i]` never contains `recipes[i]` itself.
### Examples
**Example 1**
```text
Input: recipes = ["sponge", "cake", "tart", "frosting"]
ingredients = [["flour", "eggs", "sugar"], ["sponge", "frosting"], ["flour", "butter", "cherries"], ["sugar", "butter"]]
supplies = ["butter", "eggs", "flour", "sugar"]
Output: ["cake", "frosting", "sponge"]
```
The sponge and the frosting need only basic supplies, and the cake needs the sponge and the frosting, so all three can be made. The tart needs cherries, which are neither a supply nor a recipe. The result is sorted, so it does not follow the input order.
**Example 2**
```text
Input: recipes = ["bread", "dough", "pancake", "starter"]
ingredients = [["dough"], ["flour", "starter"], ["flour", "milk"], ["flour", "bread"]]
supplies = ["flour", "milk"]
Output: ["pancake"]
```
The bread needs the dough, the dough needs the starter, and the starter needs the bread, so none of those three can ever be made first. The pancake needs only basic supplies.
Overview: Given recipes with their ingredient lists and an unlimited stock of basic supplies, return every recipe that can be made, in sorted order, where some ingredients are themselves other recipes. Tests modeling dependencies as a directed graph and handling missing ingredients and recipes that depend on each other in a cycle.
Read the full Amazon Software Engineer interview experience this question came from
A kitchen has an unlimited stock of some basic supplies and a book of recipes. Each recipe has a unique name and a list of ingredients. An ingredient may be a basic supply, the name of another recipe in the book, or something the kitchen does not have. A dish made from one recipe can be used as an ingredient in other recipes: for example, a cake may need a sponge and a frosting, each of which has its own recipe.
Implement `makeable_recipes(recipes, ingredients, supplies)`. `recipes[i]` is the name of the `i`-th recipe and `ingredients[i]` lists the ingredients it needs. `supplies` lists the basic supplies, each available in unlimited quantity. Return the names of all recipes the kitchen can make.
**Rules**
- Quantities do not matter: once a recipe has been made, it can serve as an ingredient for any number of other recipes.
- Recipes are made one at a time. A recipe can be made when each of its ingredients is either a basic supply or a recipe that has already been made.
- An ingredient that is neither a basic supply nor a recipe name can never be obtained, so a recipe that needs it, directly or through other recipes, cannot be made.
- Consequently, recipes that need one another in a cycle can never be made.
**Output**
Return a list of every recipe that can be made in some sequence, sorted in ascending lexicographic order. All names are lowercase English letters, so this is plain character-by-character order, and a name comes before any longer name that starts with it (for example `cake` before `cakes`). Return `[]` if no recipe can be made.
**Constraints**
- `1 <= len(recipes) == len(ingredients) <= 1000`
- `1 <= len(ingredients[i]) <= 100`
- `0 <= len(supplies) <= 1000`
- Every name (recipe, ingredient or supply) consists of 1 to 10 lowercase English letters.
- Recipe names are distinct, supply names are distinct, and no name is both a recipe and a supply.
- The entries of each `ingredients[i]` are distinct, and `ingredients[i]` never contains `recipes[i]` itself.
**Example 1**
```text
Input: recipes = ["sponge", "cake", "tart", "frosting"]
ingredients = [["flour", "eggs", "sugar"], ["sponge", "frosting"], ["flour", "butter", "cherries"], ["sugar", "butter"]]
supplies = ["butter", "eggs", "flour", "sugar"]
Output: ["cake", "frosting", "sponge"]
```
The sponge and the frosting need only basic supplies, and the cake needs the sponge and the frosting, so all three can be made. The tart needs cherries, which are neither a supply nor a recipe. The result is sorted, so it does not follow the input order.
**Example 2**
```text
Input: recipes = ["bread", "dough", "pancake", "starter"]
ingredients = [["dough"], ["flour", "starter"], ["flour", "milk"], ["flour", "bread"]]
supplies = ["flour", "milk"]
Output: ["pancake"]
```
The bread needs the dough, the dough needs the starter, and the starter needs the bread, so none of those three can ever be made first. The pancake needs only basic supplies.
Constraints
- 1 <= len(recipes) == len(ingredients) <= 1000
- 1 <= len(ingredients[i]) <= 100
- 0 <= len(supplies) <= 1000
- Every name (recipe, ingredient or supply) consists of 1 to 10 lowercase English letters.
- Recipe names are distinct, supply names are distinct, and no name is both a recipe and a supply.
- The entries of each ingredients[i] are distinct, and ingredients[i] never contains recipes[i] itself.
Examples
Input: (['sponge', 'cake', 'tart', 'frosting'], [['flour', 'eggs', 'sugar'], ['sponge', 'frosting'], ['flour', 'butter', 'cherries'], ['sugar', 'butter']], ['butter', 'eggs', 'flour', 'sugar'])
Expected Output: ['cake', 'frosting', 'sponge']
Explanation: Source Example 1: sponge and frosting need only supplies, cake needs both, tart needs unobtainable cherries; the result is sorted, not in input order.
Input: (['bread', 'dough', 'pancake', 'starter'], [['dough'], ['flour', 'starter'], ['flour', 'milk'], ['flour', 'bread']], ['flour', 'milk'])
Expected Output: ['pancake']
Explanation: Source Example 2: bread, dough and starter form a cycle and are never made; the independent pancake needs only supplies.
Hints
- Which recipes can certainly be made from the basic supplies alone? Once those exist, what else becomes possible?
- An ingredient that is neither a supply nor a recipe name can never be obtained. Think about every recipe that waits on it, directly or through other recipes.
- Recipes that need each other in a cycle can never be made first. The answer is sorted at the end, so the order in which you find makeable recipes does not matter.