Katkat
Back

Can a Car Meet a Truck?

ZooxSoftware Engineer · Onsite
HardSoftware EngineerOnsiteCoding & Algorithms

Last updated

This problem tests your ability to determine if two entities moving on a 2D grid can ever occupy the same coordinate at the same time, using interval arithmetic and pathfinding logic.

Problem Statement

You are given two objects, a 'Car' and a 'Truck', moving on a 2D infinite grid. Both start at specified coordinates (x_start, y_start) at time t = 0.

Each entity moves according to a sequence of commands. A command is represented as (direction, duration), where direction is one of {'U', 'D', 'L', 'R'} and duration is a positive integer. During the duration, the entity moves one unit in that direction at every integer time step.

Your task is to determine if there exists any integer time t >= 0 such that the Car and the Truck are at the same grid coordinate (x, y).

Function Signature

def can_meet(car_path, truck_path):

Input

  • car_path: A list of tuples (direction, duration) representing the Car's movement.
  • truck_path: A list of tuples (direction, duration) representing the Truck's movement.

Constraints

  • Total duration for both paths is at most 1,000,000 steps.
  • Grid coordinates can be negative.

Examples

Example 1:

  • car_path = [('R', 2)]
  • truck_path = [('R', 1), ('D', 1)]
  • Result: False (At t=1, Car is at (1,0), Truck is at (1,0). Wait, the problem asks for intersection. At t=1, they are both at (1,0). Return True.)

Example 2:

  • car_path = [('U', 5)]
  • truck_path = [('R', 5)]
  • Result: False (They only coincide at (0,0) at t=0.)

Edge Cases

  • Paths of different total lengths.
  • Entities starting at the same location (always True at t=0).
  • Paths that overlap multiple times.

Hints

Hint 1

Represent the position of each vehicle as a function of time `f(t) = (x(t), y(t))`.

Hint 2

Since the movement is continuous and velocity is constant per segment, each segment is a linear function of time within a specific interval.

Hint 3

Instead of simulating every time step, check for intersections between the linear segments of the Car and the Truck by solving the system of equations `x_car(t) = x_truck(t)` and `y_car(t) = y_truck(t)` for each overlapping time interval.

Follow-up questions

  • What if the entities have different speeds (e.g., Car moves 2 units per time step)?
  • How would you optimize the solution if both paths contained millions of segments?
  • If the entities had a 'collision radius' (e.g., they meet if distance <= 1), how would your approach change?