Katkat
Back

Detect Repeated Patterns in a String Sequence

MicrosoftSoftware Engineer · Technical Screen
HardSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests string manipulation, hashing, and the ability to detect repeating sub-sequences of a fixed length k across a stream.

Problem: Repeated Pattern Detection

You are given a sequence of strings S (an array of strings) and an integer k. A "pattern" is defined as a contiguous sub-array of length m. Write a function to determine if there exists at least one contiguous sub-array of length m that repeats at least k times consecutively.

Function Signature

def has_consecutive_repeat(sequence: List[str], m: int, k: int) -> bool:

Requirements

  • A "consecutive repeat" means the pattern appears in the sequence as [pattern, pattern, ..., pattern] (repeated k times).
  • The patterns do not need to be non-overlapping in the global sense, but the occurrences of the pattern must be adjacent.

Examples

Example 1: Input: sequence = ["a", "b", "c", "a", "b", "c", "a", "b", "c"], m = 3, k = 3 Output: True Explanation: The block ["a", "b", "c"] repeats 3 times consecutively.

Example 2: Input: sequence = ["x", "y", "x", "y", "x", "y"], m = 2, k = 2 Output: True Explanation: The block ["x", "y"] repeats 2 times consecutively starting at index 0 and index 2.

Constraints

  • 1 <= len(sequence) len(sequence): Should return False.
  • No repeating patterns found: Should return False.

Hints

Hint 1

Consider sliding a window of size 'm' to extract potential patterns, but note that checking string equality for every window can be slow.

Hint 2

Using a rolling hash or tuple representation of the sub-array of strings can help in identifying identical blocks efficiently.

Hint 3

Instead of hashing everything, keep track of the current consecutive streak of the same pattern as you iterate through the sequence.

Follow-up questions

  • How would you optimize the solution if 'm' is very large and the total number of strings is high?
  • What is the time and space complexity of your approach, and can you achieve linear time complexity O(N)?
  • How would you modify this algorithm to handle cases where the pattern size 'm' is not fixed, but you need to find the longest possible repeated pattern?