Interview Question
Share Lesson

Pilot a Rocket

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 the base on Earth to the space ship through a series of satellites to send instructions to pilot the rocket. It's important to connect to it quickly, so we need to find the shortest path from the base to the ship.

Given a graph data structure representing satellites, find the shortest path through the satellites to reach the target. You can always assume there will only be one 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.

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

 

Breakdown

Loading...
Follow teacher
Share:

Table of Contents

Validate My Answer

  1. There are two ways to traverse 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.

  4. Make sure you handle the case when there is no path to the final node.

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

Loading...
Follow teacher
Share:

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {map<str,List[str]>} satellites
 * @return {List[str]}
 */
const pilotRocket = (satellites) => {
  // Your solution here
}

// HELPER
// You can use this Queue class if needed
class Queue {
  constructor() {
    this.queue = [];
  }
  // Assume this actually operates in O(1) time
  // as an optimized queue should
  enqueue(item) {
    this.queue.unshift(item);
  }
  dequeue() {
    return this.queue.pop();
  }
  size() {
    return this.queue.length;
  }
}
// Upgrade for full course access
// Upgrade for full course access

Pilot a Rocket

Given a graph data structure representing satellites, find the shortest path through the satellites to reach the target. You can always assume there will only be one 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.

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

 
/**
 * @param {map<str,List[str]>} satellites
 * @return {List[str]}
 */
const pilotRocket = (satellites) => {
  // Your solution here
}

// HELPER
// You can use this Queue class if needed
class Queue {
  constructor() {
    this.queue = [];
  }
  // Assume this actually operates in O(1) time
  // as an optimized queue should
  enqueue(item) {
    this.queue.unshift(item);
  }
  dequeue() {
    return this.queue.pop();
  }
  size() {
    return this.queue.length;
  }
}
// Upgrade for full course access
// Upgrade for full course access