Minimize travel time with optional meeting point

Q: Minimize travel time with optional meeting point

This question evaluates a candidate's understanding of graph shortest-path computation and meeting-point optimization, testing skills in handling weighted edges, aggregating path costs, and reasoning about simultaneous movements on a network.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given a connected graph representing travel between locations.

Each node is a location.
Each edge has a non-negative travel time (if your interviewer prefers “steps”, treat each edge as weight 1).
Person A starts at node startA .
Person B starts at node startB .
Both need to reach the same destination node dest .

They are allowed to meet at any node m (possibly startA, startB, or dest), and after they meet, they travel together from m to dest.

Assume:

A and B can travel simultaneously before meeting.
They can only continue together after both have arrived at the meeting node.

Task

Compute the minimum possible arrival time for both people to reach dest under this strategy.

Output

Return the minimum arrival time (and optionally the meeting node m that achieves it).

Constraints (reasonable interview defaults)

n nodes, m edges
Edge weights are non-negative
Graph can be directed or undirected (state your assumption and adapt)

Minimize travel time with optional meeting point

Quick Overview

Task

Output

Constraints (reasonable interview defaults)

Comments (0)