Quick Overview

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.

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

  1. Use deterministic tie-breaking for prompts with multiple valid outputs.
  2. For design-style APIs, simulate operations with explicit inputs.

Loading coding console...