Outer space travel through wormholes
Filed under Samsung
Free read 1 of 3Understand how distance is calculated (usually Manhattan or Euclidean distance multiplied by a speed factor) and confirm wormhole connectivity.
The question
Calculate the shortest travel time from a source coordinate (sx, sy) to a destination coordinate (dx, dy) in a 2D space. You are given N bidirectional wormholes, where each wormhole connects two points and has a specific traversal time that may be shorter than normal Euclidean distance travel.
Constraints
- 0 <= N <= 100
- Coordinates are integers within [-10000, 10000]
- No STL or external libraries allowed; implement data structures from scratch if needed.
Examples
- Input
- Source: (0,0), Dest: (10,10), Wormholes: [((0,0), (5,5), 2)]
- Output
- 10
- Why
- Travel from (0,0) to (5,5) using the wormhole (cost 2), then from (5,5) to (10,10) normally (cost 8), total 10.
Approach
Understand how distance is calculated (usually Manhattan or Euclidean distance multiplied by a speed factor) and confirm wormhole connectivity.
Generate all permutations of wormhole traversals, which is factorial and intractable for N=100.
Model the start, destination, and all wormhole endpoints as nodes in a graph. Edges exist between all pairs of nodes with weights equal to the standard travel time, plus specific weighted edges for the wormholes. Run Dijkstra's algorithm.
Source and destination are the same; overlapping wormholes; no wormholes used being optimal.
Tips
- What they are testing: Tests your ability to model a geometry problem as a graph and run shortest path algorithms without standard library containers.
- Common mistake: Failing to consider direct travel between every pair of wormhole endpoints and start/destination without using any wormholes.
Related Samsung questions
Collected from public candidate posts and coding forums. Updated Nov 2026.