Recipes That Can Be Made from Unlimited Supplies
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Other
### Problem
You are given recipe names, the ingredients needed for each recipe and the names initially available as supplies. Supplies are unlimited. A recipe can be made only when every one of its ingredients is available, and a recipe you can make can itself serve as an ingredient for other recipes. Dependencies may include cycles. Return all recipes that can be made from the initial supplies, in any order.
```cpp
class Solution {
public:
vector<string> findAllRecipes(vector<string>& recipes, vector<vector<string>>& ingredients, vector<string>& supplies);
};
```
### Examples
**Example 1:**
```text
recipes = ["tea","meal"], ingredients = [["water","leaf"],["tea","rice"]], supplies = ["water","leaf","rice"]
Output: ["tea","meal"]
Explanation: Making tea enables meal; both are feasible.
```
**Example 2:**
```text
recipes = ["a","b"], ingredients = [["b"],["a"]], supplies = ["salt"]
Output: []
Explanation: Neither side of the dependency cycle has an initial way to become available.
```
### Constraints
- `1 <= recipes.length == ingredients.length <= 100`.
- Each ingredient list and supplies have lengths in `[1,100]`.
- Names have 1 to 10 lowercase English letters.
- Recipe names and supply names are jointly unique; each ingredient list has no duplicates.
### Clarifying Questions
Supplies are not consumed. A missing nonrecipe ingredient cannot become available later. Returned order is unrestricted.
```hint Inspect the structure
What happens when repeated passes can no longer add any recipe?
```
### What a Strong Answer Covers
- Require every ingredient of a returned recipe to be obtainable from the initial supplies.
- Include all constructible recipes without treating an unsupported dependency cycle as already available.
- Preserve unrestricted output order and handle ingredients that are neither supplied nor producible.
### Follow-up Questions
How could you avoid repeatedly inspecting recipes whose ingredient availability has not changed?
Overview: Recipes That Can Be Made from Unlimited Supplies. Each recipe has a name and a list of required ingredient names. A recipe becomes available when every ingredient is either an initial supply or another available recipe. Initial supplies are unlimited, and recipes may depend on one another, including cycles. Return all recipes that can be made, in any order.
