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 Technical Screen rounds at Anthropic.

What role is this question designed for?

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

Detect runs and answer suffix queries | Anthropic Coding Question

Detect runs and answer suffix queries

Company: Anthropic

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an array of comparable elements a[0..m-1] and an integer N: 1) Write a function that returns the maximum length of any run of consecutive equal elements in a. 2) Follow-up: return true if there exists a run whose length is at least N. Provide time and space complexities. 3) Follow-up: extend the design to support many online suffix-only queries: for each query index i, determine whether the suffix a[i..m-1] contains a run of length at least N. Describe preprocessing, data structures (e.g., prefix/suffix run lengths, segment tree, sparse table), and query/update complexities, and discuss trade-offs.

Quick Answer: This question evaluates proficiency in array processing, run-length detection, algorithmic complexity analysis, and the use of range/suffix data structures within the Coding & Algorithms domain.

Part 1: Maximum Length of a Consecutive Equal Run

Given a list of integers `nums`, a run is a sequence of one or more equal values that appear consecutively. Return the maximum length of any run in the list. If the list is empty, return `0`. Although the original interview prompt referred to comparable elements, this coding version uses integers. Only equality matters.

Constraints

`0 <= len(nums) <= 2 * 10^5`
`-10^9 <= nums[i] <= 10^9`
Only equality comparisons are needed

Examples

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

Expected Output: 3

Explanation: The longest run is `[2, 2, 2]`, which has length 3.

Input: ([5],)

Expected Output: 1

Explanation: A single element forms a run of length 1.

Input: ([],)

Expected Output: 0

Explanation: An empty list has no runs.

Input: ([4, 4, 4, 4],)

Expected Output: 4

Explanation: All elements are equal, so the whole list is one run.

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

Expected Output: 1

Explanation: Every run has length 1 because no adjacent elements are equal.

Solution

def solution(nums):
    if not nums:
        return 0

    best = 1
    current = 1

    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            current += 1
        else:
            if current > best:
                best = current
            current = 1

    if current > best:
        best = current

    return best

Time complexity: O(m), where m = len(nums). Space complexity: O(1).

Hints

Scan from left to right while tracking the current run length and the best run seen so far.
When the value changes, reset the current run to 1. Do not forget to account for the final run.

Part 2: Does Any Run Reach Length N?

Given a list of integers `nums` and an integer `n`, return `True` if there exists at least one run of consecutive equal values whose length is at least `n`. Otherwise return `False`. A run is a sequence of equal values appearing next to each other. For example, in `[3, 3, 3, 1, 2, 2]`, the runs have lengths 3, 1, and 2.

Constraints

`0 <= len(nums) <= 2 * 10^5`
`1 <= n <= 2 * 10^5`
`-10^9 <= nums[i] <= 10^9`

Examples

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

Expected Output: True

Explanation: There is a run `[2, 2, 2]` of length 3.

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

Expected Output: False

Explanation: The longest run has length 2, which is less than 3.

Input: ([], 1)

Expected Output: False

Explanation: An empty list contains no runs of positive length.

Input: ([7], 1)

Expected Output: True

Explanation: A single element is a run of length 1.

Input: ([9, 9, 9], 4)

Expected Output: False

Explanation: The array length is 3, so no run can reach 4.

Solution

def solution(nums, n):
    if n <= 0:
        return True
    if not nums:
        return False
    if n == 1:
        return True

    current = 1
    for i in range(1, len(nums)):
        if nums[i] == nums[i - 1]:
            current += 1
            if current >= n:
                return True
        else:
            current = 1

    return False

Time complexity: O(m) worst case, where m = len(nums). Space complexity: O(1).

Hints

Use the same idea as Part 1, but you can stop early as soon as the current run reaches `n`.
Handle the small boundary case `n == 1` separately.

Part 3: Suffix Queries for Runs of Length at Least N

You are given a fixed list of integers `nums`, a fixed threshold `n`, and many query indices `queries`. For each query index `i`, determine whether the suffix `nums[i:]` contains a run of consecutive equal values of length at least `n`. A run is measured inside the suffix. For example, with `nums = [5, 5, 5, 5]` and `n = 3`, query `i = 1` should return `True` because the suffix `[5, 5, 5]` contains a run of length 3. Because there can be many queries, you should preprocess once and answer each query quickly. In this fixed-array, fixed-`n`, suffix-only setting, a simple suffix-based preprocessing is optimal: compute the run length starting at each index, then build a suffix boolean array. This gives `O(m)` preprocessing and `O(1)` per query. More general structures like segment trees or sparse tables are useful when queries are more general, and a segment tree is the better choice if updates must be supported, but they are more complex than necessary here.

Constraints

`0 <= len(nums) <= 2 * 10^5`
`1 <= n <= 2 * 10^5`
`0 <= len(queries) <= 2 * 10^5`
If `nums` is non-empty, each query index is typically in the range `0 <= queries[i] < len(nums)`
`-10^9 <= nums[i] <= 10^9`

Examples

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

Expected Output: [True, True, True, False, False, False]

Explanation: Only suffixes starting at indices 0, 1, and 2 still contain a run of length at least 3.

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

Expected Output: [True, True, False]

Explanation: The suffix at index 1 is `[5, 5, 5]`, which still has a run of length 3.

Input: ([], 2, [])

Expected Output: []

Explanation: No queries on an empty array produce an empty answer list.

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

Expected Output: [False, False, False]

Explanation: No suffix contains any run of length 3.

Input: ([8], 1, [0])

Expected Output: [True]

Explanation: A single-element suffix contains a run of length 1.

Solution

def solution(nums, n, queries):
    if n <= 0:
        return [True] * len(queries)

    m = len(nums)
    if m == 0:
        return [False] * len(queries)

    start_len = [0] * m
    start_len[m - 1] = 1

    for i in range(m - 2, -1, -1):
        if nums[i] == nums[i + 1]:
            start_len[i] = start_len[i + 1] + 1
        else:
            start_len[i] = 1

    suffix_has = [False] * m
    suffix_has[m - 1] = start_len[m - 1] >= n

    for i in range(m - 2, -1, -1):
        suffix_has[i] = (start_len[i] >= n) or suffix_has[i + 1]

    answer = []
    for q in queries:
        if 0 <= q < m:
            answer.append(suffix_has[q])
        else:
            answer.append(False)
    return answer

Time complexity: O(m + q) total, with O(m) preprocessing and O(1) per query. Space complexity: O(m).

Hints

Compute `start_len[i]`: the length of the equal-valued run starting at index `i`. This is easiest to build from right to left.
Then compute `suffix_has[i]`: whether any run of length at least `n` starts at or after `i`. Each query becomes a constant-time lookup.

Quick Overview

This question evaluates proficiency in array processing, run-length detection, algorithmic complexity analysis, and the use of range/suffix data structures within the Coding & Algorithms domain.