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

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

  1. Only the moment the table becomes empty matters, not which particular object leaves last.
  2. Look at what a meeting changes on the table as a whole: compare the positions and velocities present just before and just after it.
  3. An exit time that is already an integer is not rounded up any further.

Loading coding console...

Show the approach

Approach

Collisions only change which object follows which motion. At a two-object collision the two objects swap velocities at a shared point; at a meeting of three or more objects the arriving velocities are redistributed among objects that are all at the same point. In both cases the collection of (position, velocity) pairs on the table right after the meeting is exactly what it would be if every object had passed straight through the others. Removal agrees too: an object is removed exactly when it is at position 0 or table_length, and because the occupied positions always match those of the pass-through motions, that happens exactly when a pass-through motion reaches that edge (two objects meeting exactly at an edge are both removed, matching two motions ending there). So the table becomes empty at the largest exit time of n independent, non-interacting objects. An object moving right needs (table_length - position[i]) / velocity[i] time units; an object moving left needs position[i] / (-velocity[i]). Rounding up is monotone, so the answer is the maximum over objects of the rounded-up time, computed exactly with integers as (d - 1) // s + 1 for distance d >= 1 and speed s >= 1, with no floating-point error. Edge cases: a single object; exit times that are already integers (no extra rounding); several objects leaving at the same moment; speeds up to 10^9 that make an exit time tiny (answer 1); speed 1 across a table near 10^9 long (answer near the bound). Every distance and speed fits in 32 bits; the Java and C++ references use 64-bit intermediates for safety.

Time complexity:
O(n)
Space complexity:
O(1)