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

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.

Loading coding console...

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