Detect sequence rule and repair anomaly
Company: Coinbase
Role: Data Scientist
Category: Coding & Algorithms
Difficulty: medium
Interview Round: HR Screen
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.
Quick Answer: 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.
Infer AP, alternating-difference AP, integer GP, or Fibonacci-plus-constant allowing at most one corrupted term. Return model, parameters, anomaly index, and next term.
Constraints
- Inputs are Python literals matching the function signature.
- Return a deterministic exact-match value.
Examples
Input: ([2,4,6,8],)
Expected Output: {'model': 'AP', 'parameters': {'a0': 2, 'd': 2}, 'anomaly_index': None, 'next_term': 10}
Explanation: Arithmetic progression.
Input: ([2,4,7,8],)
Expected Output: {'model': 'AP', 'parameters': {'a0': 2, 'd': 2}, 'anomaly_index': 2, 'next_term': 10}
Explanation: One AP anomaly.
Hints
- Use deterministic tie-breaking for prompts with multiple valid outputs.
- For design-style APIs, simulate operations with explicit inputs.