Find All Possible Recipes from Given Supplies

MediumGraphstopological sort

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

You have n recipes. Recipe recipes[i] can be made if you have every item in ingredients[i]. An ingredient may be a basic supply or another recipe, and a recipe you can make becomes available as an ingredient for other recipes. You start with an unlimited quantity of every item in supplies. Return the names of all recipes you can eventually make, listed in the **same order they appear in recipes**. An ingredient is available only if it is a supply or a recipe you can make. So recipes that depend on each other in a cycle, directly or through other recipes, can never be made.

Examples

Input: recipes = ["bread"], ingredients = [["yeast","flour"]], supplies = ["yeast","flour","corn"]
Output: ["bread"]
Both ingredients of bread are supplies.
Input: recipes = ["bread","sandwich"], ingredients = [["yeast","flour"],["bread","meat"]], supplies = ["yeast","flour","meat"]
Output: ["bread","sandwich"]
Bread is made from supplies, and then sandwich uses bread plus meat.

Constraints

  • `1 <= recipes.length == ingredients.length <= 100`
  • `1 <= ingredients[i].length <= 100`
  • `0 <= supplies.length <= 100`
  • All names are 1 to 10 lowercase letters; recipe names are distinct and never appear in `supplies`
  • No ingredient list contains duplicates

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More topological sort problems