Pilot a Rocket Coding Interview Question | Skilled.dev
Interview Question

Pilot a Rocket

Course launching August 2020

Follow me on YouTube for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

Your subscription could not be saved. Please try again.
Your subscription was successful! 🤓

You work for RocketX, a company that is going to send the first humans to colonize Mars. It is your job to write the algorithm that will connect to the space ship through a series of setellites to pilot it.

It's important to connect to it quickly, so we need to find the shortest path from our base on Earth through the series of satellites, eventually reaching the ship.

Given a graph data structure representing satellites, find the shortest path through the satellites to reach the target satellite that can communicate with the ship.

Write a function pilotRocket that takes in a satellites graph and returns an array of satellite IDs in order to reach the ship in the shortest path.

The starting node will always be base and the ending node will be ship. If the ship can't be reached, return null.

const satellites = {
  'base': ['sat0'],
  'sat0': ['sat1', 'sat3', 'sat4'],
  'sat1': ['sat2'],
  'sat2': ['sat3', 'sat4'],
  'sat3': ['sat4'],
  'sat4': ['sat5'],
  'sat5': ['ship'],
};
pilotRocket(satellites);
// ['base', 'sat0', 'sat4', 'sat5', 'ship']

Validate My Answer

  1. There are two ways to iterate graphs, but only one of the methods guarantees you'll use the shortest path.

  2. Make sure your search algorithm doesn't get caught in a graph cycle.

  3. Make sure your solution doesn't print in reverse order, and handle the case when there is no path to the final node.

  4. This can be solved in O(V + E) time where V is the number of vertices and E is the number of edges.