Detect sequence rule and repair anomaly

Q: Detect sequence rule and repair anomaly

This is a Coding & Algorithms interview question from Coinbase for Data Scientist roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Implement next_value(seq: list[int]) that detects the rule of a numeric sequence and returns a tuple (model_name, parameters, anomaly_index_or_None, next_term). Exactly one of the models applies: (1) Arithmetic progression (AP): a_i = a_0 + i*d. (2) Alternating-difference AP: differences alternate between d1 and d2 (i.e., a_i − a_{i−1} = d1 for odd i, d2 for even i). (3) Geometric progression (GP) of positive integers with integer ratio r (r ≥ 2): a_i = a_0 * r^i. (4) Fibonacci-plus-constant: a_i = a_{i−1} + a_{i−2} + c for i ≥ 2, with integer c. At most one term in seq may be corrupted (replaced by an arbitrary integer). Your function must: (a) infer which model best fits seq allowing at most one corruption; (b) if a corruption exists, return its zero-based index; (c) return next_term implied by the chosen model; (d) run in O(n) time and O(1) extra space; (e) break ties by choosing the model with the fewest parameters, preferring AP over Alternating-AP over GP over Fibonacci+constant when equal. Provide the exact detection logic, proofs or convincing arguments for correctness on edge cases such as very short sequences (n=3), large integers without overflow, and sequences where multiple models nearly fit.

Detect sequence rule and repair anomaly

Comments (0)