Katkat
Back

Trail Campsite Clearance: Online Pin and Range-Empty Queries

RobloxSoftware Engineer · Online Assessment
MediumSoftware EngineerOnline AssessmentCoding & Algorithms

Last updated

Process a stream of events that drop hazard pins at integer mile markers or ask whether a campsite centered at a marker with a given radius would be hazard-free, returning the answers as a string. Tests sparse-coordinate range counting with binary search and a Fenwick tree.

Rangers maintain a very long trail with integer mile markers (negative markers are allowed: they lie west of the visitor center). Initially there are no hazards. You receive events in order:

  • ("pin", x): a hazard is pinned at marker x. No marker is pinned twice.
  • ("ask", x, r): could a campsite be set up covering every marker from x - r to x + r inclusive? Answer "Y" if no hazard pinned so far lies in that range, otherwise "N". Asking never changes anything.

Return all answers concatenated in event order (empty string if there are no asks).

def campsite_report(events: list[tuple]) -> str:

Example 1

events = [("pin", 10), ("ask", 6, 3), ("ask", 6, 4),
          ("pin", 0),  ("ask", 3, 3), ("ask", 5, 4)]
output = "YNNY"
  • [3, 9] has no hazard, so Y. [2, 10] contains 10, so N.
  • After pinning 0: [0, 6] contains 0, so N. [1, 9] is clear, so Y.

Example 2

events = [("ask", -4, 0), ("pin", -4), ("ask", -4, 0),
          ("ask", -3, 0), ("ask", -2, 1)]
output = "YNYY"

With r = 0 only the marker itself is checked.

Constraints

  • 1 <= len(events) <= 2 * 10^5
  • -10^9 <= x <= 10^9, 0 <= r <= 10^9
  • Aim for O(E log E) total.

Hints

Hint 1

An ask is equivalent to: how many pins lie in [x - r, x + r]? Is it zero?

Hint 2

Coordinates are huge but there are at most E distinct pin positions. Compress them.

Hint 3

With compressed positions, a Fenwick tree gives prefix counts of pins inserted so far; bisect maps a query's endpoints into compressed indices.

Hint 4

Alternatively: keep the pins in a sorted structure and check whether the first pin >= x - r is <= x + r.

Follow-up questions

  • Hazards can now be removed. What changes in each approach?
  • Instead of yes/no, return the largest radius r for which a campsite centered at x is clear.
  • Events arrive one at a time over a network and must be answered immediately. Which approach still works?
  • Campsites, once approved, also become obstacles for later campsites. How would you model that?