How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Snowflake.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Snowflake during technical interviews.

Check if each recipe is a contiguous subsequence

Q: Check if each recipe is a contiguous subsequence

This question evaluates proficiency in algorithmic sequence matching and contiguous subarray detection, encompassing array/string pattern matching and time/space complexity reasoning.

Company: Snowflake

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Technical Screen

You are given: - An **ordered** ingredient list `ingredients[0..n-1]`. - A list of **m** recipes. Each recipe `recipes[j]` is itself a list of ingredients and is intended to represent a sequence of **consecutive** ingredients. ### Task For each recipe, determine whether it can be formed by taking a **contiguous subarray** of `ingredients` (i.e., there exists an index `s` such that `ingredients[s .. s + len(recipe)-1]` equals the recipe exactly, element by element). Return an array `ans[0..m-1]` of booleans. ### Input - Array `ingredients` (length `n`) - List of arrays `recipes` (total `m` recipes) ### Output - Boolean array `ans`, where `ans[j] = true` if `recipes[j]` appears contiguously in `ingredients`, else `false`. ### Follow-ups 1. How would you solve it if you are allowed only **O(1)** extra space (beyond the input/output)? 2. How would you solve it if `ingredients` arrives as a **data stream** and is too large to store fully? ### Constraints (typical) - `1 <= n <= 2e5` - `1 <= m <= 2e5` - Total length of all recipes `<= 2e5` - Ingredients can be treated as strings or integers.

Quick Answer: This question evaluates proficiency in algorithmic sequence matching and contiguous subarray detection, encompassing array/string pattern matching and time/space complexity reasoning.

Part 1: Efficient Contiguous Recipe Lookup

Given an ordered list `ingredients` and a list of `recipes`, return a boolean array showing whether each recipe appears exactly as a contiguous subarray of `ingredients`. A recipe matches only if every element matches in order with no gaps. An empty recipe counts as found.

Constraints

0 <= len(ingredients) <= 200000
0 <= len(recipes) <= 200000
0 <= sum(len(recipe) for recipe in recipes) <= 200000
Items are hashable values such as integers or strings
An empty recipe should be treated as present

Examples

Input: ([1, 2, 3, 4, 5], [[2, 3], [4, 5], [3, 5], [1], []])

Expected Output: [True, True, False, True, True]

Explanation: [2, 3], [4, 5], [1], and [] appear contiguously; [3, 5] does not.

Input: (['egg', 'milk', 'flour', 'sugar'], [['milk', 'flour'], ['flour', 'milk'], ['sugar'], ['egg', 'milk', 'flour', 'sugar', 'vanilla']])

Expected Output: [True, False, True, False]

Explanation: Only exact contiguous matches count.

Input: ([], [[], [1], [1, 2]])

Expected Output: [True, False, False]

Explanation: With empty ingredients, only the empty recipe can match.

Input: ([7, 7, 7], [[7], [7, 7], [7, 7, 7], [7, 7, 7, 7]])

Expected Output: [True, True, True, False]

Explanation: Repeated values still require exact length and order.

Hints

Think about a data structure that compactly represents all substrings of one sequence.
If every recipe can be checked by just following transitions from a start state, the total query time can be linear in the total recipe length.

Part 2: Contiguous Recipe Lookup with O(1) Extra Space

Given an ordered list `ingredients` and a list of `recipes`, return a boolean array showing whether each recipe appears as a contiguous subarray of `ingredients`. You must use only O(1) extra space beyond the returned answer array and a few loop variables. You may not build tries, hash maps, prefix tables, or copies of the input. An empty recipe counts as found.

Constraints

0 <= len(ingredients) <= 2000
0 <= len(recipes) <= 200
0 <= len(recipe) <= 50 for each recipe
Elements are compared using exact equality
Use only O(1) auxiliary space beyond the output list

Examples

Input: ([1, 2, 3, 4, 5], [[2, 3], [3, 5], [1, 2, 3, 4, 5], [5]])

Expected Output: [True, False, True, True]

Explanation: Only [3, 5] fails because its elements are not consecutive in `ingredients`.

Input: (['a', 'b', 'a', 'b'], [['a', 'b'], ['b', 'a', 'b'], ['a', 'a'], []])

Expected Output: [True, True, False, True]

Explanation: The empty recipe always matches.

Input: ([], [[], [1]])

Expected Output: [True, False]

Explanation: An empty ingredient list can only contain the empty recipe.

Input: ([9], [[9], [8], [9, 9]])

Expected Output: [True, False, False]

Explanation: Single-element and overlong recipes are important boundary cases.

Hints

With constant extra space, compare each recipe directly against every possible starting position in `ingredients`.
Break early on the first mismatch so you do not compare more than necessary.

Part 3: Contiguous Recipe Lookup on a Data Stream

You are given all `recipes` up front, but `ingredients` arrives as a stream and may be too large to store. Process the stream left to right, using only one pass over it, and return a boolean array showing whether each recipe appears contiguously somewhere in the stream. For testing, the stream is passed as a Python iterable such as a list, but your algorithm should treat it as single-pass input. An empty recipe counts as found.

Constraints

0 <= len(recipes) <= 200000
0 <= sum(len(recipe) for recipe in recipes) <= 200000
The stream length can be very large and should not be stored fully
The stream should be consumed in one pass
Items are hashable values such as integers or strings

Examples

Input: ([1, 2, 3, 2, 3, 4], [[2, 3], [3, 4], [4, 5], []])

Expected Output: [True, True, False, True]

Explanation: The stream contains [2, 3] and [3, 4], but not [4, 5].

Input: (['egg', 'milk', 'flour', 'milk', 'flour', 'sugar'], [['milk', 'flour'], ['flour', 'sugar'], ['egg', 'sugar']])

Expected Output: [True, True, False]

Explanation: Recipes can match at different positions as the stream is consumed.

Input: ([], [[], [1], [1, 2]])

Expected Output: [True, False, False]

Explanation: With an empty stream, only the empty recipe matches.

Input: ([7, 7, 7, 7], [[7], [7, 7], [7, 7, 7], [7, 7, 7, 7], [7, 7, 7, 7, 7]])

Expected Output: [True, True, True, True, False]

Explanation: Every recipe up to length 4 appears; length 5 does not.

Input: ([1, 2, 1, 2], [[1, 2], [1, 2], [2, 1]])

Expected Output: [True, True, True]

Explanation: Duplicate recipes should each receive their own boolean answer.

Hints

Since the stream cannot be stored, preprocess the recipes instead of the stream.
A trie with failure links can keep track of every recipe prefix while you read one item at a time.

Quick Overview

This question evaluates proficiency in algorithmic sequence matching and contiguous subarray detection, encompassing array/string pattern matching and time/space complexity reasoning.