Katkat
Back

Check if each recipe is a contiguous subsequence

SnowflakeSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to efficiently determine if one sequence exists as a contiguous segment within another using pattern matching techniques.

Problem Statement

You are given two lists of integers: recipe and menu. A recipe is considered a "contiguous subsequence" of the menu if all elements of recipe appear in the menu in the exact same order and without any interruptions from other elements.

Write a function is_contiguous(recipe, menu) that returns True if recipe is a contiguous subsequence of menu, and False otherwise.

Constraints

  • 1 <= len(recipe) <= 10^5
  • 1 <= len(menu) <= 10^6
  • Elements are integers between -10^9 and 10^9.

Examples

Example 1:

  • recipe = [1, 2, 3]
  • menu = [5, 1, 2, 3, 9]
  • Output: True

Example 2:

  • recipe = [1, 2, 3]
  • menu = [1, 3, 2, 3]
  • Output: False (The elements 1, 2, 3 appear but are not contiguous)

Function Signature

def is_contiguous(recipe: list[int], menu: list[int]) -> bool:
    pass

Considerations

  • Can you solve this in O(N + M) time, where N and M are the lengths of the two lists?
  • Consider edge cases like an empty recipe (which should technically be contained in any menu) or a recipe longer than the menu.

Hints

Hint 1

Consider using string matching algorithms like Knuth-Morris-Pratt (KMP) to avoid redundant comparisons.

Hint 2

The core of the KMP algorithm is the 'prefix function' or 'LPS array' (Longest Proper Prefix which is also Suffix).

Hint 3

If you treat the lists as arrays of integers, the KMP logic remains identical to how it functions with character strings.

Follow-up questions

  • What would the time complexity be if you used a naive nested loop approach, and why is that suboptimal?
  • How would your approach change if you were required to find if the recipe exists in the menu allowing for up to one 'mismatch' or 'skipped' element?
  • If the menu was extremely large (e.g., streaming data), how could you adapt the solution to process it without loading the entire menu into memory?