Recipe Sequence Matcher

Problem Description You have a main list of ingredients called ingredients. You also have a list of recipes. Each recipe is just a smaller list of ingredients. For eve

Recipe Sequence Matcher

Problem Description You have a main list of ingredients called ingredients. You also have a list of recipes. Each recipe is just a smaller list of ingredients. For every recipe, you need to check if it exists inside the main ingredients list. The recipe must appear as a solid block (contiguous sequence). You cannot skip ingredients or change their order. The interview usually has three parts: 1.

Basic Solution: Use preprocessing to make searches fast. 2.

Follow-up 1: Save memory (use only O(1) extra space). 3.

Follow-up 2: Handle a massive stream of data.

Example Input

python ingredients = ["bun", "lettuce", "tomato", "patty", "cheese", "onion"] recipes = [["lettuce", "tomato", "patty"], # True (It is right there in the middle) ["tomato", "cheese"], # False ("patty" is between them) ["patty", "cheese"], # True (They are next to each other)]

--- ## Part 1: Basic Solution (Hash Approach) ### Task Write a function match_recipes that takes the full list and the recipes. It should return a list of True or False values. ### Rules * You must keep the exact order of ingredients. * The match must be contiguous (no gaps). * The solution should handle many recipe queries quickly. ### Testing

python ingredients = ["a", "b", "c", "d", "e"] recipes = [["b", "c"], # True ["c", "e"], # False ["a"], # True ["d", "e", "f"], # False] assert match_recipes(ingredients, recipes) == [True, False, True, False]

Solution

Approach We can use a "Rolling Hash" strategy. 1. Convert every ingredient into a number (ID). 2. Look at every possible group of ingredients in the main list. 3. Calculate a hash code for each group and store it in a map (HashMap). 4. To check a recipe, calculate its hash code and see if that code exists in our map. ### Code Implementation

python from collections import defaultdict class RecipeMatcher: _MOD1 = 1_000_000_007 _MOD2 = 1_000_000_009 _BASE1 = 911_382_323 _BASE2 = 972_663_749 def __init__(self, ingredients: list[str]): self._token_id: dict[str, int] = {} self._next_id = 1 self._hashes_by_len: dict[int, set[tuple[int, int]]] = defaultdict(set) for token in ingredients: self._get_token_id(token) n = len(ingredients) for i in range(n): h1 = 0 h2 = 0 for j in range(i, n): token_value = self._get_token_id(ingredients[j]) h1 = (h1 * self._BASE1 + token_value) % self._MOD1 h2 = (h2 * self._BASE2 + token_value) % self._MOD2 self._hashes_by_len[j - i + 1].add((h1, h2)) def _get_token_id(self, token: str) -> int: if token not in self._token_id: self._token_id[token] = self._next_id self._next_id += 1 return self._token_id[token] def can_make(self, recipe: list[str]) -> bool: if not recipe:

**return** True h1 = 0 h2 = 0 for token in recipe: token_value = self._token_id.get(token) if token_value is None: # If an ingredient is missing from main list, recipe fails.

**return** False h1 = (h1 * self._BASE1 + token_value) % self._MOD1 h2 = (h2 * self._BASE2 + token_value) % self._MOD2 return (h1, h2) in self._hashes_by_len[len(recipe)] def match_recipes(ingredients: list[str], recipes: list[list[str]]) -> list[bool]: matcher = RecipeMatcher(ingredients)

**return** [matcher.can_make(recipe) for recipe in recipes]

Complexity Analysis | Step | Time | Space | | --- | --- | --- | | Preprocess main list | O(n^2) | O(n^2) | | Check one recipe | O(m) | O(1) extra | Here, n is the length of ingredients, and m is the length of a recipe. --- ## Part 2: Low Memory Constraint ### New Requirement Now, assume you are very low on memory. You cannot use O(n^2) space for HashMaps. You must solve the problem using only O(1) extra space. ### How to Solve We can use a simple "Two-Pointer" or sliding window method. 1. Take a recipe. 2. Try to match it starting at index 0 of the ingredient list. 3. If it doesn't match, try starting at index 1, then index 2, and so on. 4. Do this for every recipe. ### Code Implementation

python def contains_recipe_o1_space(ingredients: list[str], recipe: list[str]) -> bool: n = len(ingredients) m = len(recipe) if m == 0:

**return** True if m > n:

**return** False start = 0 while start <= n - m: i = start j = 0 while j < m and ingredients[i] == recipe[j]: i += 1 j += 1 if j == m:

**return** True start += 1 return False def match_recipes_o1_space( ingredients: list[str], recipes: list[list[str]] ) -> list[bool]:

**return** [contains_recipe_o1_space(ingredients, recipe) for recipe in recipes]

Complexity Analysis | Operation | Time | Space | | --- | --- | --- | | Check one recipe | O(n * m) worst-case | O(1) | | Check all recipes | O(sum(n * m_i)) | O(1) extra | This method saves memory but is slower than Part 1. --- ## Part 3: Streaming Data ### The Challenge Now imagine the ingredient list is too big to store in memory. The ingredients arrive one by one as a "stream". You still need to identify which recipes appear. ### Strategy We use the

Aho-Corasick algorithm. This builds a special search tree (Trie). 1.

Build a Trie: Put all recipes into a prefix tree. 2.

Fail Links: Add special links that tell us where to jump if a partial match fails. 3.

Process Stream: Read ingredients one by one. Move through the tree. If we reach the end of a recipe in the tree, we mark it as found. ### Code Implementation

python from collections import deque class StreamRecipeMatcher: def __init__(self, recipes: list[list[str]]): self._recipes = recipes self._children = [dict()] # node -> {token: next_node} self._fail = [0] self._out = [[]] # node -> recipe ids ending here self._build_trie() self._build_fail_links() def _new_node(self) -> int: self._children.append({}) self._fail.append(0) self._out.append([])

**return** len(self._children) - 1 def _build_trie(self) -> None: for recipe_id, recipe in enumerate(self._recipes): node = 0 for token in recipe: if token not in self._children[node]: self._children[node][token] = self._new_node() node = self._children[node][token] self._out[node].append(recipe_id) def _build_fail_links(self) -> None: q = deque() for _, nxt in self._children[0].items(): self._fail[nxt] = 0 q.append(nxt) while q: node = q.popleft() for token, nxt in self._children[node].items(): f = self._fail[node] while f and token not in self._children[f]: f = self._fail[f] self._fail[nxt] = self._children[f].get(token, 0) self._out[nxt].extend(self._out[self._fail[nxt]]) q.append(nxt) def match_stream(self, ingredient_stream) -> list[bool]: matched = [False] * len(self._recipes) remaining = len(self._recipes) state = 0 # Empty recipes match immediately, even if the stream has no tokens. for recipe_id in self._out[0]: if not matched[recipe_id]: matched[recipe_id] = True remaining -= 1 if remaining == 0:

**return** matched for token in ingredient_stream: while state and token not in self._children[state]: state = self._fail[state] state = self._children[state].get(token, 0) for recipe_id in self._out[state]: if not matched[recipe_id]: matched[recipe_id] = True remaining -= 1 if remaining == 0: break return matched

Complexity Analysis | Step | Time | Space | | --- | --- | --- | | Build structure | O(total recipe tokens) | O(total recipe tokens) | | Process stream | O(stream length) | O(1) relative to stream | This is the best approach when you cannot hold all ingredients in memory at once.