Solve Watcher Simulation And Integer Conversion
Company: Hudson
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are asked to solve two independent coding tasks.
### Task 1: Count players that reach the finish
There is a one-dimensional track with integer positions from `0` to `L`. The finish line is at position `L`.
- There are `N` players. `players[i]` is the initial position of player `i`.
- Every player always wants to move to the right, one unit per second.
- A watcher stands at position `watcherPos` and initially looks to the right.
- At each timestamp in `turnTimes`, the watcher reverses direction. The list `turnTimes` may be unsorted.
- During any one-second interval, a player that is currently being watched cannot move. A player is watched if:
- the watcher is looking right and the player's current position is greater than or equal to `watcherPos`, or
- the watcher is looking left and the player's current position is less than or equal to `watcherPos`.
- All players that are not watched move one unit to the right during that second.
- Multiple players may occupy the same position, and they do not block each other.
- Once a player reaches position `L`, they are considered finished and remain finished.
Given `L`, `players`, `watcherPos`, `turnTimes`, and an ending time `T`, return how many players have reached the finish line by time `T`.
Define the exact event order as follows: for each integer time `t` from `0` to `T - 1`, first apply all watcher direction changes scheduled at time `t`, then decide which players are watched during interval `[t, t + 1)`, then move all unwatched unfinished players one step to the right.
### Task 2: Implement integer-to-string conversion
Implement a function similar to `itoa`:
```text
string intToDecimalString(int x)
```
Given a 32-bit signed integer `x`, return its base-10 decimal string representation.
Requirements:
- Do not use built-in integer-to-string conversion functions.
- If `x == 0`, return `"0"`.
- If `x` is negative, the returned string must start with `'-'`.
- Correctly handle the full 32-bit signed integer range, including `-2147483648`.
Quick Answer: This question evaluates event-driven simulation and discrete-time state modeling for tracking multiple agents under dynamic visibility constraints, together with low-level numeric string conversion and edge-case handling for 32-bit signed integers.
Part 1: Count Players That Reach the Finish
You are given a one-dimensional track with integer positions from 0 to L, where L is the finish line. There are several players, and players[i] is the initial position of player i. Every player wants to move one unit to the right each second. A watcher stands at watcherPos and starts by looking to the right. For each integer time t from 0 to T - 1, first apply all direction reversals scheduled at time t, then determine who is watched during the interval [t, t + 1), then move every unwatched unfinished player one step to the right. A player is watched if the watcher is looking right and the player's current position is at least watcherPos, or if the watcher is looking left and the player's current position is at most watcherPos. Players do not block each other, and finished players stay finished. The list turnTimes may be unsorted and may contain duplicate times. Return how many players have reached position L by time T.
Constraints
- 1 <= L <= 10^9
- 0 <= len(players) <= 2 * 10^5
- 0 <= players[i] <= L
- 0 <= watcherPos <= L
- 0 <= len(turnTimes) <= 2 * 10^5
- 0 <= turnTimes[i] <= 10^9
- 0 <= T <= 10^9
Examples
Input: (10, [2, 7, 10, 5], 5, [3, 0, 3], 6)
Expected Output: 2
Explanation: Turns at time 3 cancel out, so only time 0 matters. The watcher faces left for all 6 seconds. Player 7 reaches 10, player 10 is already finished, and the others do not finish.
Input: (5, [0, 3, 4, 5], 5, [1, 4], 5)
Expected Output: 3
Explanation: The watcher faces right for 2 seconds total and is standing at the finish. Players at 3 and 4 can use those right-facing seconds to reach 5, and the player already at 5 also counts.
Input: (4, [4, 1, 0], 2, [0, 1, 2], 0)
Expected Output: 1
Explanation: No time passes, so only the player already at the finish counts.
Input: (8, [6, 7, 2], 4, [1, 4, 1], 6)
Expected Output: 2
Explanation: The two turns at time 1 cancel, so the only effective turn is at time 4. The watcher faces left for the last 2 seconds, which is enough for players starting at 6 and 7 to finish.
Input: (7, [], 3, [2, 5], 10)
Expected Output: 0
Explanation: There are no players.
Hints
- Because players only move right and never interact, a player's fate depends only on whether it starts left of the watcher, at the watcher, or right of the watcher.
- You do not need to simulate every second up to T. First reduce duplicate turn times by parity, sort the effective turn times, and count how many seconds the watcher faces right versus left.
Part 2: Integer to Decimal String
Implement a function intToDecimalString-like routine. Given a 32-bit signed integer x, return its base-10 decimal string representation without using built-in integer-to-string conversion functions. If x is 0, return "0". If x is negative, the result must start with '-'. Your function must correctly handle the full 32-bit signed integer range, including -2147483648.
Constraints
- -2147483648 <= x <= 2147483647
- Do not use built-in integer-to-string conversion functions such as str()
Examples
Input: 0
Expected Output: "0"
Explanation: Zero is a special case and should return exactly "0".
Input: 12345
Expected Output: "12345"
Explanation: A normal positive integer.
Input: -907
Expected Output: "-907"
Explanation: Negative numbers need a leading minus sign.
Input: -2147483648
Expected Output: "-2147483648"
Explanation: This is the minimum 32-bit signed integer and must still be handled correctly.
Input: 2147483647
Expected Output: "2147483647"
Explanation: This is the maximum 32-bit signed integer.
Hints
- Extract digits from right to left using modulo 10 and integer division by 10.
- Handle the sign separately, then reverse the collected digits at the end.