Detect runs and answer suffix queries

Q: Detect runs and answer suffix queries

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Given an array of comparable elements a[0..m-1] and an integer N:

Write a function that returns the maximum length of any run of consecutive equal elements in a.
Follow-up: return true if there exists a run whose length is at least N. Provide time and space complexities.
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.

Detect runs and answer suffix queries

Overview

Comments (0)