How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a easy difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Hudson.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Hudson during technical interviews.

Count People Reaching the Boundary | Hudson Coding Question

Quick Overview

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.

Count People Reaching the Boundary

Company: Hudson

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Onsite

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?

Quick Answer: 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.

Part 1: Count People Reaching the Boundary in Discrete Time

You are given a 1-dimensional line with a right boundary at position L and a stationary watcher at position W. Each person starts at an integer position and wants to move to the right. Time is divided into T integer steps, numbered 0 to T-1. If a switch time t appears in switch_times, the watcher reverses direction at the start of step t, before anyone attempts to move. On each step, every person tries to move 1 unit to the right. A person who is visible to the watcher at the start of that step cannot move during that step. If the watcher faces right, every person strictly to the right of W is visible. If the watcher faces left, every person strictly to the left of W is visible. A person exactly at W is never blocked and may move. Return how many people are at position at least L after exactly T steps.

Constraints

0 <= len(positions) <= 2 * 10^5
0 <= W <= L <= 10^9
0 <= T <= 10^9
Each positions[i] is an integer
switch_times is strictly increasing and each value satisfies 0 < t < T
Positions are not necessarily sorted

Examples

Input: (10, 4, 6, [8, 9, 3, 4], 'R', [2, 5])

Expected Output: 2

Explanation: The watcher faces right on steps 0-1, left on steps 2-4, and right on step 5. Only the people starting at 8 and 9 get enough left-facing steps to reach 10.

Input: (6, 5, 2, [4, 5], 'R', [])

Expected Output: 2

Explanation: The person at 5 moves immediately on step 0 and reaches 6. The person at 4 reaches W on step 0, then uses the next step from W to reach 6.

Input: (10, 5, 7, [], 'L', [3])

Expected Output: 0

Explanation: There are no people.

Input: (5, 2, 0, [5, 1, 2], 'L', [])

Expected Output: 1

Explanation: With zero steps, only the person already at the boundary counts.

Hints

Because everyone only moves to the right, each person can only be in three phases: left of W, exactly at W, or right of W.
Precompute how many steps the watcher spends facing left or right up to any time, then use binary search to find when a person reaches W.

Part 2: Count People Reaching the Boundary in Continuous Time

You are given the same line, boundary L, watcher position W, initial watcher direction, and direction switch times, but movement is now continuous. Between switch times, the watcher keeps a fixed direction. Every person moves continuously to the right at speed 1 whenever they are not visible and at speed 0 whenever they are visible. If the watcher faces right, all positions x > W are visible. If the watcher faces left, all positions x < W are visible. A person exactly at W is not visible. Because time is continuous, any positive-distance motion on the right of W can only happen while the watcher faces left, and any positive-distance motion on the left side toward W can only happen while the watcher faces right. Return how many people are at position at least L by time T.

Constraints

0 <= len(positions) <= 2 * 10^5
0 <= W <= L <= 10^9
0 <= T <= 10^9
positions and switch_times may be integers or floating-point numbers
switch_times is strictly increasing and each value satisfies 0 < t < T
Positions are not necessarily sorted

Examples

Input: (10.0, 4.0, 7.0, [2.0, 4.0, 8.0], 'R', [1.5, 4.0, 6.0])

Expected Output: 1

Explanation: Only the person starting at 8 gets enough total left-facing time to travel from 8 to 10.

Input: (6.0, 5.0, 2.0, [4.0, 5.0, 5.5], 'R', [1.0])

Expected Output: 3

Explanation: The watcher faces right on [0,1) and left on [1,2). The left-side person reaches W exactly at t=1 and then finishes during the left-facing interval. The other two also finish by t=2.

Input: (10.0, 3.0, 4.0, [1.0, 3.0, 9.0], 'L', [])

Expected Output: 1

Explanation: With the watcher always facing left, only the person already to the right of W can keep moving.

Input: (5.0, 2.0, 0.0, [5.0, 1.0, 2.0], 'R', [])

Expected Output: 1

Explanation: No time passes, so only the person already at the boundary counts.

Hints

Between two consecutive switch times, the watcher's direction is constant, so only the total amount of usable time in each interval matters.
A person starting left of W must first accumulate enough right-facing time to reach W, then enough left-facing time after that moment to get from W to L.

Quick Overview