## Problem Given a sequence of integers, determine if it has a repeating pattern of period `p` (for any p from 1 to n/2). If yes, return the shortest repeating unit and the next `k` predicted elements. If no pattern exists, return an empty list. ```python def find_pattern( sequence: list[int], k: int ) -> tuple[list[int], list[int]]: """Returns (pattern_unit, next_k_elements). pattern_unit=[] if none found.""" ... ``` ``` Input: sequence=[1,2,3,1,2,3,1,2,3], k=4 Pattern found: [1,2,3] (period 3) Next 4: [1,2,3,1] Output: ([1,2,3], [1,2,3,1]) Input: sequence=[1,2,3,4], k=2 No repeating pattern. Output: ([], []) Input: sequence=[5,5,5,5], k=3 Pattern: [5] (period 1) Output: ([5], [5,5,5]) ``` ## Follow-ups 1. How do you verify a candidate period `p`? What is the time complexity of checking all periods? 2. What if the sequence is only approximately periodic (some elements differ by at most 1)? How do you define "close enough"? 3. Can you use the KMP failure function to detect periodicity efficiently? Describe how. 4. If the sequence is a time series of stock prices, what limitations does strict periodicity detection have, and what alternatives would you use?

InterviewDB Question

Pattern Finding: Identify Repeating Structural Patterns in Sequences and Predict Next Elements

phone

Question Details

Problem Given a sequence of integers, determine if it has a repeating pattern of period p (for any p from 1 to n/2). If yes, return the shortest repeating unit and the next k predicted elements. If no pattern exists, return an empty list. Follow-ups How do you verify a candidate period p? What is the time complexity of checking all periods? What if the sequence is only approximately periodic (some elements differ by at most 1)? How do you define "close enough"? Can you use the KMP failure functi…

Full Details

🔒

Unlock all Instacart questions

Full insider details, leaked discussions, and candidate experiences.

or every company, $100/year →

About This Question

This is a reported interview question from a instacart interview during the phone round.

It covers the following topics: Coding, Onsite, Phone .

Topics

Coding Onsite Phone

Pattern Finding: Identify Repeating Structural Patterns in Sequences and Predict Next Elements

Question Details

Full Details

About This Question

Topics

More Instacart Interview Questions