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

Quick Overview

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

Loading coding console...

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