Recipe manager with ingredient search

Question: Recipe manager with ingredient search

Companies: Anthropic, Airbnb

Difficulty: Medium

Problem statement

Build an in-memory recipe book. Each recipe has a name, an ordered list of ingredients and an ordered list of steps. The work comes in two parts; finish part 1 before you start part 2.

Part 1: create, read, update, delete

Implement a RecipeManager class:

• add_recipe(name, ingredients, steps) -> str: store a new recipe and return its id. Ids are "recipe1", "recipe2", ... in creation order, and an id is never reused, even after its recipe is deleted. Return "" if the name is blank or another stored recipe already has the same name. Names are compared case-insensitively, ignoring leading and trailing spaces.
• get_recipe(recipe_id) -> Recipe | None: return the recipe (id, name, ingredients, steps) with lists in their original order and spelling, or None if the id does not exist.
• update_recipe(recipe_id, name, ingredients, steps) -> bool: replace all three fields. Return False and change nothing if the id does not exist or the new name belongs to a different recipe. A recipe may keep its own name or change its capitalization.
• delete_recipe(recipe_id) -> bool: remove the recipe; False if it does not exist.

Part 2: search

• search_by_ingredient(ingredient) -> list[str]: ids of recipes that use the ingredient (case-insensitive exact match), oldest first.
• search_by_name(query) -> list[str]: ids of recipes whose name contains query, case-insensitive, oldest first.
• find_cookable(pantry) -> list[str]: ids of recipes whose every ingredient is in pantry, oldest first. A recipe with no ingredients is always cookable.

Searches will be far more frequent than writes. State the time complexity of each method.

Example

m = RecipeManager()
m.add_recipe("Fried rice", ["rice", "egg", "scallion"], ["cook rice", "stir-fry"])  # "recipe1"
m.add_recipe("Boiled egg", ["egg"], ["boil 9 minutes"])                           # "recipe2"
m.add_recipe("FRIED RICE", ["rice"], [])                                          # "" (name taken)
m.search_by_ingredient("Egg")                                                     # ["recipe1", "recipe2"]
m.find_cookable(["egg", "rice"])                                                  # ["recipe2"]
m.delete_recipe("recipe1")                                                        # True
m.add_recipe("Fried rice", ["rice", "egg"], ["stir-fry"])                         # "recipe3"
m.find_cookable(["egg", "rice"])                                                  # ["recipe2", "recipe3"]

Constraints

• Up to 10^5 recipes, up to 50 ingredients and 100 steps per recipe.
• Names and ingredients are non-empty strings of at most 100 characters.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

This is a staged object-design question: build a small in-memory store in
part 1, then add search and filtering on top of it without breaking the
earlier rules. The grade is mostly about getting the edge cases right
(case-insensitive names, ids that are never reused, updates that rename)
and picking indexes that make the later parts cheap.

State.

• _recipes: dict[id -> Recipe]. Python dicts keep insertion order, and ids
  are handed out in increasing order, so iterating this dict already gives
  "oldest first" with no sorting.
• _by_name: dict[normalized name -> id]. Makes the uniqueness check O(1).
  Normalize with strip().lower() in exactly one helper so add, update and
  lookups can never disagree.
• _next: int. The id counter only ever goes up. Deleting recipe2 does not
  free the number 2.

Brute force for search. search_by_ingredient can scan every recipe and
every ingredient: O(total ingredients) per query. Say this first; it is the
right answer if the store is small or searches are rare.

Inverted index. When searches outnumber writes, keep
_by_ingredient: dict[ingredient -> set of ids], updated on add, update and
delete. A lookup becomes O(k log k) for k matches (the sort keeps results
in id order).

"What can I cook?" find_cookable(pantry) returns recipes whose every
ingredient is in the pantry. Checking each recipe against a pantry set
costs O(total ingredients). With the index you can do better: for each
pantry item, walk its posting set and count hits per recipe. A recipe is
cookable when its hit count equals its number of distinct ingredients
(cached in _need). Only recipes that share an ingredient with the pantry
are touched. Recipes with no ingredients are trivially cookable, which is
why the final pass checks _need for every id.

Update = unindex old, index new. Updating is the place most bugs hide.
Check the new name against _by_name but allow the recipe to keep (or
re-case) its own name. Only after every check passes, remove the old index
entries and add the new ones, so a rejected update changes nothing.

Invariants.

• Every id in _recipes appears in _by_name under its normalized name,
  and in _by_ingredient under each of its distinct normalized ingredients.
  No index refers to a deleted id.
• Empty posting sets are removed, so the index does not grow with churn.
• Stored ingredient and step lists keep the caller's order and spelling.
  Only the indexes use normalized text. get_recipe returns copies, so
  callers cannot change stored state behind the indexes.

Code

from collections import defaultdict
from dataclasses import dataclass
from typing import Optional


def _norm(s: str) -> str:
    return s.strip().lower()


@dataclass
class Recipe:
    recipe_id: str
    name: str
    ingredients: list[str]
    steps: list[str]


class RecipeManager:
    def __init__(self) -> None:
        self._next = 1
        self._recipes: dict[str, Recipe] = {}          # id -> recipe (insertion order = id order)
        self._by_name: dict[str, str] = {}             # normalized name -> id
        self._by_ingredient: dict[str, set[str]] = defaultdict(set)  # ingredient -> ids
        self._need: dict[str, int] = {}                # id -> number of distinct ingredients

    # ---- helpers -------------------------------------------------------
    @staticmethod
    def _key(recipe_id: str) -> int:
        return int(recipe_id[len("recipe"):])

    def _index(self, r: Recipe) -> None:
        self._by_name[_norm(r.name)] = r.recipe_id
        distinct = {_norm(i) for i in r.ingredients}
        self._need[r.recipe_id] = len(distinct)
        for ing in distinct:
            self._by_ingredient[ing].add(r.recipe_id)

    def _unindex(self, r: Recipe) -> None:
        del self._by_name[_norm(r.name)]
        del self._need[r.recipe_id]
        for ing in {_norm(i) for i in r.ingredients}:
            ids = self._by_ingredient[ing]
            ids.discard(r.recipe_id)
            if not ids:
                del self._by_ingredient[ing]

    # ---- part 1: CRUD --------------------------------------------------
    def add_recipe(self, name: str, ingredients: list[str], steps: list[str]) -> str:
        if not name.strip() or _norm(name) in self._by_name:
            return ""
        rid = f"recipe{self._next}"
        self._next += 1                                 # ids are never reused
        r = Recipe(rid, name, list(ingredients), list(steps))
        self._recipes[rid] = r
        self._index(r)
        return rid

    def get_recipe(self, recipe_id: str) -> Optional[Recipe]:
        r = self._recipes.get(recipe_id)
        if r is None:
            return None
        return Recipe(r.recipe_id, r.name, list(r.ingredients), list(r.steps))  # defensive copy

    def update_recipe(self, recipe_id: str, name: str,
                      ingredients: list[str], steps: list[str]) -> bool:
        r = self._recipes.get(recipe_id)
        if r is None or not name.strip():
            return False
        owner = self._by_name.get(_norm(name))
        if owner is not None and owner != recipe_id:    # name taken by another recipe
            return False
        self._unindex(r)
        r.name, r.ingredients, r.steps = name, list(ingredients), list(steps)
        self._index(r)
        return True

    def delete_recipe(self, recipe_id: str) -> bool:
        r = self._recipes.pop(recipe_id, None)
        if r is None:
            return False
        self._unindex(r)
        return True

    # ---- part 2: search ------------------------------------------------
    def search_by_ingredient(self, ingredient: str) -> list[str]:
        ids = self._by_ingredient.get(_norm(ingredient), set())
        return sorted(ids, key=self._key)

    def search_by_name(self, query: str) -> list[str]:
        q = _norm(query)
        return [rid for rid, r in self._recipes.items() if q in r.name.lower()]

    def find_cookable(self, pantry: list[str]) -> list[str]:
        """Recipes whose every ingredient is in the pantry."""
        hits: dict[str, int] = defaultdict(int)
        for ing in {_norm(p) for p in pantry}:
            for rid in self._by_ingredient.get(ing, ()):
                hits[rid] += 1
        return [rid for rid in self._recipes if hits.get(rid, 0) == self._need[rid]]

Complexity

Let n be the number of recipes, g the number of ingredients in one
recipe, s its number of steps, and k the number of results.

Space is O(total ingredients + total steps) for the recipes, plus the same
order again for the ingredient index.

Test cases

• add_recipe("Pancakes", ["Flour", "egg", "milk"], ["mix", "fry"]) returns
  "recipe1".
• add_recipe("pancakes ", ["x"], []) returns "" (same name after trim and
  lowercase).
• add_recipe("Omelette", ["egg", "salt"], ...) returns "recipe2";
  add_recipe("Toast", [], ["toast bread"]) returns "recipe3".
• get_recipe("recipe1").ingredients == ["Flour", "egg", "milk"] (original
  order and casing kept). get_recipe("recipe9") is None.
• search_by_ingredient("EGG") returns ["recipe1", "recipe2"].
• find_cookable(["egg", "salt"]) returns ["recipe2", "recipe3"] (Toast
  needs nothing).
• update_recipe("recipe2", "PANCAKES", ...) returns False (name owned by
  recipe1) and leaves recipe2 unchanged.
• update_recipe("recipe2", "omelette", ["egg", "cheese"], ["cook"]) returns
  True (re-casing its own name is allowed); afterwards
  search_by_ingredient("salt") is [].
• delete_recipe("recipe1") is True, a second delete is False, and
  update_recipe("recipe1", ...) is False.
• After that delete, add_recipe("Pancakes", ["flour"], []) succeeds and
  returns "recipe4", not "recipe1".
• search_by_name("CAKE") returns ["recipe4"]; find_cookable([]) returns
  ["recipe3"].
• A blank name (" ") is rejected with "".

Follow-ups

1. Name search by prefix at scale. Replace the linear scan with a sorted
   list of normalized names and bisect for a prefix range
   (O(log n + k)), or a trie. Substring search needs n-gram indexes; ask
   which one the product needs before building it.
2. Structured ingredients and scaling. Ingredients become
   (name, quantity, unit). Index on the name only; add
   scale(recipe_id, servings) that multiplies quantities and normalizes
   units (3 tsp to 1 tbsp). Keep quantities as Fraction to avoid float
   drift.
3. Missing at most m ingredients. "What can I almost cook?" uses the
   same hit counts: return recipes with need - hits <= m, ranked by fewest
   missing and then by id. The count trick generalizes with no new index.
4. Version history and undo. Store each update as an immutable version
   (recipe_id -> list[Recipe]); get_recipe(id, version) reads history
   and revert writes a new version equal to an old one. Deletes become
   soft deletes so history survives.
5. Concurrency and persistence. Guard mutations with one lock (the name
   check and insert must be atomic, or two writers can both claim a name).
   In a database the same guarantee is a unique index on the normalized
   name, and the ingredient index becomes a join table.

Interviewer expectations

Mid-level (L4)

• Working CRUD with case-insensitive unique names and sequential ids that
  are never reused.
• Handles missing ids and duplicate names by returning the specified
  sentinel, not by raising.
• Reaches a correct ingredient search, even if it starts as a scan.

Senior (L5)

• Adds the inverted index and keeps it consistent through update and
  delete, including rejected updates that must change nothing.
• Allows a recipe to keep or re-case its own name on update.
• States per-operation complexity and when the scan is the better choice.

Staff (L6+)

• Designs state so later parts slot in: the hit-count approach for
  cookable and near-cookable queries, defensive copies, one normalization
  helper.
• Talks through atomicity of the name check under concurrency and how the
  model maps to a database (unique index, join table, soft deletes).
• Keeps the code small and readable under time pressure, with a few
  targeted tests.