Find All Possible Recipes from Given Supplies

Find All Possible Recipes from Given Supplies

What is this problem about?

In the Find All Possible Recipes from Given Supplies coding problem, you are a chef with a list of initial supplies. You want to make several recipes, but each recipe requires a specific set of ingredients. An ingredient can be either a basic supply or another recipe you've already made. You need to return a list of all recipes you can eventually complete.

Why is this asked in interviews?

Uber, Microsoft, and Google use this to test your understanding of dependency management. This is a classic "Dependency Graph" problem. It evaluations your proficiency with the Topological Sort interview pattern (Kahn's Algorithm). It tests whether you can represent recipes and ingredients as nodes and edges in a directed acyclic graph (DAG) and find an ordering that allows completion.

Algorithmic pattern used

The problem is solved using Kahn's Algorithm (Topological Sort).

1. Treat each recipe as a node.
2. Create a directed edge from each ingredient to the recipe that requires it.
3. Keep track of the "in-degree" (number of missing ingredients) for each recipe.
4. Use a Queue to store "available" items (initial supplies and recipes with in-degree 0).
5. While the queue is not empty:
   • Pop an item. If it's a recipe, add it to the final result.
   • For every recipe that uses this item, decrement its in-degree.
   • If a recipe's in-degree becomes 0, add it to the queue.

Example explanation

Supplies: ["yeast", "flour"]. Recipes: ["bread", "sandwich"]. Ingredients: bread: ["yeast", "flour"], sandwich: ["bread", "ham"].

1. bread needs 2 ingredients. Both are in supplies. In-degree becomes 0.
2. sandwich needs 2 ingredients. bread is one, ham is the other.
3. Queue starts with yeast, flour.
4. Process yeast and flour $o$ bread's in-degree becomes 0. Add bread to queue.
5. Process bread $o$ sandwich's in-degree becomes 1 (still needs ham).
6. ham is not available. sandwich is never finished. Result: ["bread"].

Common mistakes candidates make

• Brute force recursion: Trying to solve each recipe independently, which leads to $O(N^2)$ or exponential time if dependencies are deep.
• Ignoring cycles: Not realizing that if Recipe A needs B and B needs A, neither can be made.
• Inefficient lookups: Using lists instead of Hash Sets for supply checks.

Interview preparation tip

Whenever you see "to do A, you must first do B," think Topological Sort. This pattern is applicable to everything from build systems (like Make or Gradle) to task scheduling and cooking recipes.