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 medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Uber.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Uber during technical interviews.

Last Truck to Leave a One-Dimensional Lane

Quick Overview

This algorithms interview question evaluates reasoning about continuous motion, collisions, and exact rational time in a one-dimensional simulation. It is commonly asked to assess whether an engineer can distinguish physical behavior from identity semantics while handling large inputs and precise boundary conditions.

Company: Uber

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Take-home Project

# Last Truck to Leave a One-Dimensional Lane Implement `last_exit_time(lane_length, positions, velocities)`. Distinct trucks start at integer positions strictly between `0` and `lane_length`. Truck `i` moves continuously at constant nonzero integer velocity `velocities[i]`: positive is right, negative is left. A truck leaves as soon as it crosses either boundary. When two trucks meet, they instantaneously exchange velocities. Trucks have zero length, and the input excludes simultaneous collisions involving three or more trucks. Return the time when the final truck leaves as a reduced fraction `(numerator, denominator)` with a positive denominator. ## Constraints - `1 <= lane_length <= 10^9` - `1 <= len(positions) == len(velocities) <= 200,000` - Initial positions are distinct. - `1 <= abs(velocities[i]) <= 10^9` - Every truck initially moves toward one of the two boundaries. ## Example behavior A truck at position `3` moving left at speed `2` would reach the left boundary after `3/2` time units if no label-changing collision affected its identity. ## Candidate clarifications Confirm collision physics, whether truck identity matters to the requested final time, boundary semantics, and the required exact representation.

Quick Answer: This algorithms interview question evaluates reasoning about continuous motion, collisions, and exact rational time in a one-dimensional simulation. It is commonly asked to assess whether an engineer can distinguish physical behavior from identity semantics while handling large inputs and precise boundary conditions.

A one-dimensional lane spans coordinates 0 to lane_length. Distinct trucks start at integer positions strictly between 0 and lane_length. Truck i moves continuously at constant nonzero integer velocity velocities[i]: positive means toward the right boundary at lane_length, negative means toward the left boundary at 0. A truck leaves the lane the moment it reaches either boundary. Trucks have zero length, and when two trucks meet they instantaneously exchange velocities; the input never contains a simultaneous meeting of three or more trucks. Implement last_exit_time(lane_length, positions, velocities) and return the time at which the final truck leaves the lane as an exact reduced fraction (numerator, denominator): a two-element sequence with gcd(numerator, denominator) = 1 and denominator > 0. An integer time t is returned as (t, 1). This canonical form makes the correct answer unique for every input. Example 1: lane_length = 10, positions = [3], velocities = [-2]. The only truck reaches the left boundary after 3/2 time units, so the answer is (3, 2). Example 2: lane_length = 9, positions = [2, 5], velocities = [3, -2]. The trucks meet at time 3/5 at coordinate 19/5 and exchange velocities: the truck that started at 2 now moves at -2 and reaches the left boundary at time 5/2, while the truck that started at 5 moves at +3 and reaches the right boundary at time 7/3. The final departure happens at 5/2, so the answer is (5, 2). Arithmetic note: values and intermediate results exceed 32-bit range. Comparing two candidate exit times exactly requires cross-multiplication whose products reach about 10^18, so use long in Java and long long in C++; in JavaScript perform comparisons with BigInt. Floating-point comparison cannot separate the closest exit times within the stated bounds.

Constraints

1 <= lane_length <= 10^9
1 <= len(positions) == len(velocities) <= 200,000
Initial positions are distinct integers strictly between 0 and lane_length.
velocities[i] is a nonzero integer with 1 <= abs(velocities[i]) <= 10^9; positive moves right, negative moves left.
Every truck initially moves toward one of the two boundaries.
The input excludes simultaneous collisions involving three or more trucks.
Exit-time comparisons need 64-bit integers: cross products reach about 10^18 (long in Java, long long in C++, BigInt comparisons in JavaScript).

Examples

Input: (10, [3], [-2])

Expected Output: (3, 2)

Explanation: Source example: the sole truck reaches the left boundary after 3/2 time units.

Input: (10, [4], [2])

Expected Output: (3, 1)

Explanation: Single right-mover with an integer exit time: (10 - 4) / 2 = 3, returned as (3, 1).

Hints

Simulating every collision individually can take quadratic time. Look for what stays the same about the system as a whole when two trucks exchange velocities.
If you ignore which truck is which, two trucks exchanging velocities at a meeting point look exactly like two trucks driving straight through each other.
Keep every exit time as an exact fraction and compare candidates by cross-multiplication in 64-bit integers; floating point cannot separate the closest pairs within the stated bounds.

Quick Overview