Count players reaching end with moving watchers
Company: Hudson
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Technical Screen
You are given a 1D line of **L** cells indexed **0..L-1**. The **end cell** is **L-1**.
There are:
- **W watchers** with initial integer positions `watchers[]`.
- **P players** with initial integer positions `players[]`.
- A time horizon **T** (non-negative integer, number of unit-time steps).
- An unsorted list `flipTimes[]` of integer timestamps. **At each timestamp `t` in `flipTimes`, all watchers reverse direction**.
Movement model (discrete time):
- Time steps are `t = 0, 1, ..., T-1`.
- Each watcher has a facing direction (`LEFT` or `RIGHT`). **All watchers start facing LEFT at time 0**.
- At the **start** of each step `t`, if `t` is in `flipTimes`, all watchers reverse direction.
- **Watching rule:** At step `t`, a watcher at position `x`:
- if facing `LEFT`, watches **all cells `< x`**;
- if facing `RIGHT`, watches **all cells `> x`**.
A player is considered **watched** if at least one watcher watches the player’s current cell.
- **Player move:** During step `t`, each player tries to move **one cell to the right** (from `p` to `min(p+1, L-1)`), **but if the player is watched at the start of the step, the player cannot move and stays in place**.
- **Watcher move:** After all players have (attempted) to move, each watcher moves one cell in its facing direction:
- `LEFT`: `x = max(x-1, 0)`
- `RIGHT`: `x = min(x+1, L-1)`
Task:
- After performing exactly **T** steps, return **how many players are at cell `L-1`**.
Notes / clarifications:
- Multiple players and watchers may occupy the same cell.
- `flipTimes[]` may contain duplicates and is not sorted.
Write a function that takes `(L, watchers, players, T, flipTimes)` and returns the count.
Suggested constraints (for implementation):
- `1 <= L <= 2e5`
- `0 <= W, P <= 2e5`
- `0 <= T <= 2e5`
- `0 <= flipTimes[i] <= T-1`
Quick Answer: This question evaluates skills in discrete-event simulation, stateful time-step modeling, and range coverage by moving agents, as well as algorithmic efficiency for processing flip events and large input sizes.