Most-Visited Position Across Sprints

Reported in interviews at Citadel

Problem statement

A runner trains by sprinting between markers placed at integer positions 1..n. The runner follows a list of markers in order; each consecutive pair defines one sprint, a straight run between those two markers (for example, from position 4 to position 1). Every integer position on that closed interval, endpoints included, is visited once by that sprint, regardless of direction.

Given n and the ordered list of markers sprints, compute how many times each position 1..n is visited in total, and return the maximum visit count over all positions.

Complete:

def getMostVisited(n: int, sprints: list[int]) -> int:

Constraints:

  • $1 \le n \le 10^9$ (treat the position range as large -- you cannot afford to touch every position of every interval).
  • $2 \le \text{len(sprints)} \le 10^5$, each marker in 1..n.

Examples:

  • sprints = [1, 3, 5, 3], n = 5 -> intervals [1,3], [3,5], [3,5] give per-position totals 1, 1, 3, 2, 2; the answer is 3 (position 3).
  • sprints = [2, 4, 1, 3], n = 5 -> intervals [2,4], [1,4], [1,3] give per-position totals 2, 3, 3, 2, 0; the answer is 3 (positions 2 and 3).
Show hint

Is there a way to record a whole range of +1 updates without touching every position inside it?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems