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 medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Anthropic.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Anthropic during technical interviews.

Convert State Stream to Events | Anthropic Coding Question

Convert State Stream to Events

Company: Anthropic

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given an array `states` where `states[i]` is the categorical output of a monitoring function at timestamp `i`. Consecutive equal values belong to the same event. Write a function that converts this stream into a list of events of the form `(value, start_index, end_index)`, where `start_index` and `end_index` are inclusive. Example: - Input: `['A', 'A', 'B', 'B', 'B', 'A']` - Output: `[('A', 0, 1), ('B', 2, 4), ('A', 5, 5)]` Follow-up: given an integer `k`, only runs with length at least `k` should be considered valid events. Any consecutive run shorter than `k` should be excluded from the output. Implement the function and analyze its time and space complexity.

Quick Answer: This question evaluates a candidate's ability to process sequential categorical data by identifying and summarizing consecutive runs, reason about time and space complexity, and apply length-based filtering of events.

Part 1: Convert State Stream into Events

You are given a list `states` where `states[i]` is the categorical output of a monitoring function at timestamp `i`. Consecutive equal values belong to the same event. Convert the stream into a list of events of the form `(value, start_index, end_index)`, where `start_index` and `end_index` are inclusive and indices are 0-based. For example, the stream `['A', 'A', 'B', 'B', 'B', 'A']` should become `[('A', 0, 1), ('B', 2, 4), ('A', 5, 5)]`.

Constraints

0 <= len(states) <= 100000
Each element in `states` supports equality comparison
Indices are 0-based
Runs are maximal: two adjacent events must always have different values

Examples

Input: (['A', 'A', 'B', 'B', 'B', 'A'],)

Expected Output: [('A', 0, 1), ('B', 2, 4), ('A', 5, 5)]

Explanation: Three runs appear: A from 0 to 1, B from 2 to 4, and A from 5 to 5.

Input: ([],)

Expected Output: []

Explanation: An empty stream has no events.

Input: (['X'],)

Expected Output: [('X', 0, 0)]

Explanation: A single element forms one event of length 1.

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

Expected Output: [(1, 0, 0), (2, 1, 2), (3, 3, 5), (2, 6, 6)]

Explanation: Each maximal run is converted into one tuple.

Input: (['Z', 'Z', 'Z'],)

Expected Output: [('Z', 0, 2)]

Explanation: All elements belong to one continuous run.

Hints

Scan from left to right and keep track of where the current run started.
Whenever the value changes, finish the previous run and start a new one.

Part 2: Convert State Stream into Events with Minimum Run Length

You are given a list `states` where `states[i]` is the categorical output of a monitoring function at timestamp `i`. Consecutive equal values form a run. Given an integer `k`, return only those events whose run length is at least `k`. Each valid event should be represented as `(value, start_index, end_index)`, using inclusive 0-based indices. Important: short runs are simply discarded. They do not merge neighboring runs, even if the neighboring runs have the same value. Example: `states = ['A', 'A', 'B', 'B', 'B', 'A']`, `k = 2` should return `[('A', 0, 1), ('B', 2, 4)]`.

Constraints

0 <= len(states) <= 100000
1 <= k <= 100000
Each element in `states` supports equality comparison
Runs are determined from the original stream before filtering

Examples

Input: (['A', 'A', 'B', 'B', 'B', 'A'], 2)

Expected Output: [('A', 0, 1), ('B', 2, 4)]

Explanation: The final A run has length 1, so it is excluded.

Input: (['A', 'A', 'B', 'A', 'A'], 2)

Expected Output: [('A', 0, 1), ('A', 3, 4)]

Explanation: The middle B run is too short and is removed, but the two A runs are not merged because they were separated in the original stream.

Input: ([], 1)

Expected Output: []

Explanation: An empty stream produces no events.

Input: (['X'], 1)

Expected Output: [('X', 0, 0)]

Explanation: A single-element run is valid when k = 1.

Input: (['A', 'B', 'B', 'C', 'C', 'C', 'D'], 3)

Expected Output: [('C', 3, 5)]

Explanation: Only the C run has length at least 3.

Hints

First identify each consecutive run exactly as in Part 1.
Before appending a run, compute its length as `end_index - start_index + 1` and compare it with `k`.

Quick Overview

This question evaluates a candidate's ability to process sequential categorical data by identifying and summarizing consecutive runs, reason about time and space complexity, and apply length-based filtering of events.