Katkat
Back

Count People Reaching the Boundary

Hudson River TradingMachine Learning Engineer · Onsite
EasyMachine Learning EngineerOnsiteCoding & Algorithms

Last updated

This question evaluates algorithmic simulation and event-driven modeling skills, specifically handling discrete versus continuous time, visibility constraints relative to a stationary watcher that changes facing direction, and boundary conditions for state transitions.

You are given a 1-dimensional line segment with a right boundary at position L. There are N people with initial positions p1, p2, ..., pN, and there is a stationary watcher at position W.

Each person wants to move to the right. Time is first considered in discrete unit steps for a total of T steps.

The watcher has an initial facing direction, either left or right. The watcher does not move, but it reverses direction at specified times t1, t2, ..., tC.

During each time step:

  • Every person attempts to move 1 unit to the right.
  • If a person is currently visible to the watcher, that person cannot move during that step.
  • If the watcher is facing right, then any person strictly to the right of W is visible.
  • If the watcher is facing left, then any person strictly to the left of W is visible.
  • If a person is exactly at position W, that person is allowed to move.

A person who reaches L is considered to have arrived at the destination.

Return how many people have reached position L after T time steps.

Follow-up: How would you handle the continuous-time version of the problem, where movement is continuous instead of step-based, and the watcher still changes direction only at the given switch times?