Detect sequence rule and repair anomaly
CoinbaseData Scientist · HR ScreenLast updated
This question evaluates a candidate's skill in sequence pattern recognition, algorithm design, complexity analysis, and robust integer arithmetic by requiring inference among arithmetic, alternating-difference, geometric, and Fibonacci-plus-constant models while tolerating at most one corrupted term under O(n) time and O(1) extra space constraints.
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.
Solution walkthrough is for members
Get the full walkthrough with reference code and complexity analysis, plus Kitty Coach at 300 messages a day. Hints, the code runner and community answers stay free.