How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Optiver.

What role is this question designed for?

This question is commonly asked for Data Scientist candidates at Optiver during technical interviews.

Find missing numbers in sequences | Optiver Coding Question

Find missing numbers in sequences

Company: Optiver

Role: Data Scientist

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Take-home Project

You are given several number sequences (integers and/or rational numbers). Each sequence contains exactly one missing term written as `?`. For each sequence, determine the missing term so that the sequence follows a consistent pattern. ### Sequences 1. `1, 2, 3, 16/5, 25/8, 36/13, ?, 49/21` 2. `2, 2, 3, 4, 5, 8, 8, ?, 16` 3. `4, 5, 9, 13, 22, 31, ?, 53` 4. `3, 2, 4, 4, 12, 36, ?, 396` 5. `2, 1, 2, 5, 13, 73/2, ?` 6. `1, 2, 5, 11, 26, 59, ?, 137` ### Output Return the missing value for each sequence (in simplest fractional form when needed).

Quick Answer: This question evaluates sequence pattern recognition, numerical reasoning with integers and rational numbers, and the ability to infer recurrences or closed-form relations from series data.

Part 1: Number Logic - Fill the Missing Term

You are given a sequence with exactly one missing term, written as ?. The completed sequence is guaranteed to match exactly one of these pattern families: (1) arithmetic progression, (2) geometric progression with non-zero ratio not equal to 1, (3) Fibonacci-like sequence where every term from the 3rd onward equals the sum of the previous two, or (4) a quadratic sequence with non-zero constant second difference. Terms may be integers or rational numbers written as p/q. Return the missing term in reduced form.

Constraints

4 <= len(sequence) <= 30
Exactly one entry is '?'
The full sequence matches exactly one supported family
If the sequence is geometric, all known terms are non-zero and the ratio is rational

Examples

Input: ['3', '7', '11', '?', '19']

Expected Output: "15"

Explanation: This is an arithmetic progression with common difference 4.

Input: ['16', '8', '4', '?', '1']

Expected Output: "2"

Explanation: This is a geometric progression with ratio 1/2.

Input: ['?', '1', '1', '2', '3', '5']

Expected Output: "0"

Explanation: Fibonacci-like sequence: 0, 1, 1, 2, 3, 5. This is an edge case with the missing value at the first position.

Input: ['1', '4', '9', '?', '25']

Expected Output: "16"

Explanation: These are consecutive squares, so the sequence has constant non-zero second difference.

Input: ['1/2', '1', '3/2', '?', '5/2']

Expected Output: "2"

Explanation: Arithmetic progression with common difference 1/2.

Hints

Use exact rational arithmetic instead of floating point to avoid precision mistakes.
Try inferring the missing value under each allowed pattern, then verify it against every known position.

Part 2: Beat the Odds - Count Odd-Heavy Subarrays

Given an integer array, count how many contiguous subarrays contain strictly more odd numbers than even numbers. Negative numbers are allowed; only parity matters.

Constraints

0 <= len(nums) <= 200000
-10^9 <= nums[i] <= 10^9
The answer can be larger than 32-bit integer range
An odd number contributes +1 and an even number contributes -1 to a subarray balance

Examples

Input: [1, 2, 3]

Expected Output: 3

Explanation: Valid subarrays are [1], [1,2,3], and [3].

Input: [2, 4, 6]

Expected Output: 0

Explanation: Every subarray has at least as many evens as odds.

Input: []

Expected Output: 0

Explanation: Edge case: an empty array has no subarrays.

Input: [1, 1, 2, 1]

Expected Output: 7

Explanation: There are 7 subarrays with more odds than evens.

Input: [7]

Expected Output: 1

Explanation: Edge case: the only subarray contains one odd and zero evens.

Hints

Convert the problem into counting subarrays with positive sum after mapping odd -> +1 and even -> -1.
For each prefix sum, count how many previous prefix sums are strictly smaller. A Fenwick tree or balanced BST can help.

Part 3: Likelihood Test - Rank Targets in a Random Walk

A walker starts at a node in a directed graph. Every step, it chooses uniformly at random among the current node's outgoing edges. If a node has no outgoing edges, the walker stays there. Given a number of steps k and a list of target nodes, rank the targets from most likely to least likely to be the walker's location after exactly k steps. If two targets have the same probability, keep their original relative order.

Constraints

1 <= n <= 200
0 <= len(edges) <= 2000
0 <= start < n
0 <= k <= 200
Targets are distinct node labels in the range [0, n-1]

Examples

Input: (4, [(0, 1), (0, 2), (1, 2), (2, 2), (2, 3)], 0, 2, [1, 2, 3])

Expected Output: [2, 3, 1]

Explanation: After 2 steps, node 2 has probability 3/4, node 3 has 1/4, and node 1 has 0.

Input: (3, [(0, 1), (1, 2)], 1, 0, [0, 1, 2])

Expected Output: [1, 0, 2]

Explanation: Edge case: with 0 steps, the walker is certainly still at the start node 1.

Input: (3, [(0, 1)], 0, 3, [1, 2, 0])

Expected Output: [1, 2, 0]

Explanation: The walker moves to node 1 on the first step and then stays there because node 1 has no outgoing edges.

Input: (3, [(0, 1), (0, 2), (1, 0), (2, 0)], 0, 1, [2, 1, 0])

Expected Output: [2, 1, 0]

Explanation: Nodes 2 and 1 are tied at probability 1/2, so the original target order breaks the tie.

Hints

Use dynamic programming: keep the probability distribution over nodes after each step.
Treat a sink node as having an implicit self-loop with probability 1.

Quick Overview

This question evaluates sequence pattern recognition, numerical reasoning with integers and rational numbers, and the ability to infer recurrences or closed-form relations from series data.