Recipes You Can Prepare
Indeed● MediumFULLTIMEPHONE SCREENProblem statement
You are given recipe names recipes, their required ingredient lists ingredients, and initially available raw materials supplies. Return every recipe that can be prepared, in lexicographic order.
- For this exercise, assume
ingredients[i]lists every item needed forrecipes[i], and each required item must be available. - An ingredient may name another recipe. A recipe becomes available as an ingredient only after it can be prepared.
- For this exercise, assume available items have unlimited reusable quantities; preparing one recipe does not consume an item needed by another.
- Recipes with no required ingredients can be prepared immediately. A cycle alone does not make any item available.
- Unknown raw materials that are absent from supplies cannot be obtained.
Recipe names are unique and do not occur in supplies. Repeated supply names have the same meaning as a single occurrence.
Function
preparableRecipes(recipes: String[], ingredients: String[][], supplies: String[]) → String[]Examples
Example 1
recipes = ["bread","sandwich"]ingredients = [["flour","yeast"],["bread","ham"]]supplies = ["flour","yeast","ham"]return = ["bread","sandwich"]Bread is prepared from flour and yeast, then bread and ham prepare sandwich.
Example 2
recipes = ["soup","salad"]ingredients = [["water","salt"],["lettuce"]]supplies = ["water"]return = []Salt and lettuce are unavailable, so neither recipe can be prepared.
Example 3
recipes = ["a","b","c"]ingredients = [["b"],["a"],[]]supplies = []return = ["c"]The a/b cycle has no starting item; c has no ingredients and is immediately available.
Constraints
- For this exercise, assume
0 <= recipes.length <= 500andingredients.length == recipes.length. - The total number of ingredient entries is at most
5000. 0 <= supplies.length <= 5000.- Every name contains
1through30lowercase ASCII letters or digits. - Recipe names are unique, recipe names do not occur in supplies, and each ingredient list has distinct names.