Katkat
Back

Detect runs and answer suffix queries

AnthropicSoftware Engineer · Technical Screen
MediumSoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

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.

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.