Last Time an Object Leaves a Table When Colliding Objects Swap Velocities
Company: IBM
Role: Business Intelligence Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
A table is the segment from position 0 (its left edge) to position `table_length` (its right edge). Object `i` starts at `position[i]` and moves at the constant velocity `velocity[i]`; a positive velocity moves it to the right and a negative velocity moves it to the left. All objects start moving at time 0. When two objects meet they collide and exchange velocities, and an object is removed from the table as soon as it reaches either edge. Return the time at which the last object leaves the table, rounded up to an integer.
The report states the collision and removal rules and the rounding, but not whether starting positions can repeat or what happens when three or more objects meet at once; this version makes the positions distinct and fixes the multi-object case in Rules below.
### Function Signature
```python
def last_exit_time(position: list[int], velocity: list[int], table_length: int) -> int:
```
### Rules
- Objects are points. Between collisions, an object at position `p` with velocity `v` is at `p + v * t` after `t` more time units.
- Two objects collide whenever they are at the same point at the same moment, whether they are moving toward each other or one is catching up with another moving in the same direction. Each continues from that point with the other's velocity.
- If three or more objects are at the same point at the same moment, they leave it with the velocities they arrived with, redistributed so that their left-to-right order does not change: list the objects from left to right as they were just before the meeting, and the `k`-th object in that list leaves with the `k`-th smallest of those velocities. For two objects this is the same as exchanging velocities.
- An object is removed at the exact moment it reaches position 0 or position `table_length`; that moment is its exit time. A removed object takes no further part in collisions.
- Return the smallest integer that is greater than or equal to the largest exit time.
### Constraints
- `1 <= n <= 2 * 10^5`, where `n = len(position) = len(velocity)`
- `2 <= table_length <= 10^9`
- Every `position[i]` is an integer with `0 < position[i] < table_length`, and all positions are distinct.
- Every `velocity[i]` is an integer with `-10^9 <= velocity[i] <= 10^9` and `velocity[i] != 0`.
- The answer is at most `10^9`, so it fits in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: position = [2, 4, 5], velocity = [2, -2, 4], table_length = 9
Output: 4
```
The objects starting at 2 and 4 meet at position 3 at time 0.5 and exchange velocities. The first then moves left from 3 at speed 2 and leaves at time 2; the second moves right from 3 at speed 2 and leaves at time 3.5. The object starting at 5 moves right at speed 4, never meets another object, and leaves at time 1. The last exit is at time 3.5, so the answer is 4.
**Example 2**
```text
Input: position = [2, 5], velocity = [3, 1], table_length = 10
Output: 5
```
The object starting at 2 catches up with the object starting at 5 at position 6.5 at time 1.5, and they exchange velocities. The front object now moves right at speed 3 and leaves at time `1.5 + 3.5 / 3`, about 2.67; the rear object now moves right at speed 1 and leaves at time `1.5 + 3.5 = 5`. The last exit time is exactly 5, so the answer is 5.
**Example 3**
```text
Input: position = [1], velocity = [-1000000000], table_length = 2
Output: 1
```
The only object reaches position 0 at time `1 / 10^9`, which rounds up to 1.
Overview: Given the starting positions and nonzero velocities of up to 200,000 objects on a table of fixed length, where objects that meet exchange velocities and each object is removed when it reaches an edge, return the time at which the last object leaves, rounded up. It tests reasoning about collision dynamics and finding an approach fast enough for large inputs.
Read the full IBM Business Intelligence Engineer interview experience this question came from
A table is the segment from position `0` (its left edge) to position `table_length` (its right edge). There are `n` objects on it. Object `i` starts at the integer position `position[i]` and moves at the constant integer velocity `velocity[i]`: a positive velocity moves it to the right and a negative velocity moves it to the left. All objects start moving at time `0`.
The objects follow these rules:
- Objects are points. Between collisions, an object at position `p` with velocity `v` is at `p + v * t` after `t` more time units.
- Two objects collide whenever they are at the same point at the same moment, whether they are moving toward each other or one is catching up with another moving in the same direction. Each continues from that point with the other's velocity.
- If three or more objects are at the same point at the same moment, they leave it with the velocities they arrived with, redistributed so that their left-to-right order does not change: list the objects from left to right as they were just before the meeting, and the `k`-th object in that list leaves with the `k`-th smallest of those velocities. For two objects this is the same as exchanging velocities.
- An object is removed from the table at the exact moment it reaches position `0` or position `table_length`; that moment is its exit time. A removed object takes no further part in collisions.
Implement `last_exit_time(position, velocity, table_length)`, which returns the time at which the last object leaves the table, rounded up to an integer: the smallest integer that is greater than or equal to the largest exit time.
### Example 1
```text
Input: position = [2, 4, 5], velocity = [2, -2, 4], table_length = 9
Output: 4
```
The objects starting at 2 and 4 meet at position 3 at time 0.5 and exchange velocities. The first then moves left from 3 at speed 2 and leaves at time 2; the second moves right from 3 at speed 2 and leaves at time 3.5. The object starting at 5 moves right at speed 4, never meets another object, and leaves at time 1. The last exit is at time 3.5, so the answer is 4.
### Example 2
```text
Input: position = [2, 5], velocity = [3, 1], table_length = 10
Output: 5
```
The object starting at 2 catches up with the object starting at 5 at position 6.5 at time 1.5, and they exchange velocities. The front object now moves right at speed 3 and leaves at time `1.5 + 3.5 / 3`, about 2.67; the rear object now moves right at speed 1 and leaves at time `1.5 + 3.5 = 5`. The last exit time is exactly 5, so the answer is 5.
### Constraints
- `1 <= n <= 2 * 10^5`, where `n = len(position) = len(velocity)`
- `2 <= table_length <= 10^9`
- Every `position[i]` is an integer with `0 < position[i] < table_length`, and all positions are distinct.
- Every `velocity[i]` is an integer with `-10^9 <= velocity[i] <= 10^9` and `velocity[i] != 0`.
- The answer is at most `10^9`, so it fits in a 32-bit signed integer.
No input value and no answer exceeds `2^31 - 1`.
Constraints
- 1 <= n <= 2 * 10^5, where n = len(position) = len(velocity)
- 2 <= table_length <= 10^9
- Every position[i] is an integer with 0 < position[i] < table_length, and all positions are distinct.
- Every velocity[i] is an integer with -10^9 <= velocity[i] <= 10^9 and velocity[i] != 0.
- The answer is at most 10^9, so it fits in a 32-bit signed integer.
Examples
Input: ([2, 4, 5], [2, -2, 4], 9)
Expected Output: 4
Explanation: Source example 1: a head-on collision at position 3 at time 0.5; the last exit is at 3.5 through the right edge, which rounds up to 4.
Input: ([2, 5], [3, 1], 10)
Expected Output: 5
Explanation: Source example 2: a catch-up collision at position 6.5 at time 1.5; the last exit is exactly 5, so there is no rounding up.
Hints
- Only the moment the table becomes empty matters, not which particular object leaves last.
- Look at what a meeting changes on the table as a whole: compare the positions and velocities present just before and just after it.
- An exit time that is already an integer is not rounded up any further.