stressed out man with hands on his face

Code Tests – Airplane Itinerary Problem

Introduction

This post is about a code test that I recently encountered and struggled to solve during the interview. The problem isn’t actually that difficult but when under the pressure of a paired coding test, I sometimes freeze up. What I typically do when I struggle to solve something in an interview is go back to the problem later and figure out the solution so I have it in the back of my head for future interviews. I find that by doing this, I end up learning and growing as a Software Engineer. I encourage you to read the problem statement and try and solve it yourself before reading on to see how I solved it. I chose to implement it in JavaScript.

The Problem Statement

Write code that sorts a few plain ticket pairs in the form of source to destination into their logical trip sequence. (assume no duplicates exist)

example input flights = {SFO -> SEA, BOS -> SFO, IAD -> DEN, SEA -> IAD}

answer [BOS, SFO, SEA, IAD, DEN]

Logical Solution

I have found it helpful to observe how I solve a coding test problem first in my head before writing the code to solve it. The way I solved this problem, in my head, is by comparing each leg of the journey to see if a destination is found at the start of a leg but never occurs at the ending of a leg. If such a destination exists, it is the location (and leg) that the journey starts from. Then, I look at where the flight lands on the starting leg and look through the other legs to see the next one that starts where the previous leg ends until there are no more legs left in the journey. From this you get the right order of legs for the itinerary.

Programming Solution

As I said before, I have chosen to implement this solution in JavaScript. The logical steps I have implemented in my code are as follows:

1 – Find the starting leg of the Itinerary

2 – Using the end destination of the starting leg find the next leg in the itinerary where the start destination matches the end destination of the starting leg. Continue to evaluate each following leg in the same manner.

3 – When each leg has been evaluated and mapped to the previous leg in the itinerary I printed the output as a string of destinations representing the order of Airports that will be landed at throughout the journey.

Here is my code for each step:

I used the following code to initialize the JavaScript file and kick off the execution of the functions that I’ve written to solve this problem.

//TEST DATA
let input = [
    {start: 'SFO', end: 'SEA'},
    {start: 'BOS', end: 'SFO'},
    {start: 'IAD', end: 'DEN'},
    {start: 'SEA', end: 'IAD'}
];

/**
 * Initiates the evaluation of the trip order and prints the resulting output
 * on the console.
 */
(function printTrip(originalTrip){
    console.log(createTripList(originalTrip));
})(input);

The following function is used to orchestrate the execution of each function that I wrote to solve each part of the problem statement.

/**
 * This is the main function which orchestrates the rest of the 
 * solution.  First it determines which leg is the start of the trip.
 * Then it reorders the legs from start to finish and finally it iterates
 *  that list and returns a string representation.
 * 
 * @param {*} originalTrip - the input data to be evaluated
 * @returns {String} - The stops of the trip ordered from start to finish
 */
function createTripList(originalTrip){

    //Determines which airport is the start of the trip
    const startingAirport = findTripStart({...buildStartEndArrays(originalTrip)});

    //Reorders the legs from starting airport to the final destination airport
    const orderedLegs = evaluateLegs(originalTrip, startingAirport);

    //Builds a string of the stops based on the ordered tripStops
    return buildTripStopsString(orderedLegs);
}

Step 1 – Find the starting leg in the flight itinerary

I broke this up into three functions, the first is called buildStartEndArrays() which initializes two arrays that I use to keep track of all the locations that a leg of the itinerary starts from and and ends at. The arrays are called “origins” and “destinations”. I then return the initialized arrays to another function called findTripStart() which takes advantage of the JavaScript Array.some() function to look for a location that exists in the start locations but does not exist in the end locations. I used some() because it tests to see if at least one value meets the criteria specified and if it finds that value it stops iterating and returns. Using the inDestinations() function and taking advantage of the Array.find() function I check to see if the legStart for the current leg exists in the array of destinations. If it is found that leg is returned and the findTripStart() function moves onto the next leg until the start location for a leg is not found in the destination array. Once I find this location I return it and use it as the starting destination for the flight itinerary. You can see these both being called in the previous code listed in this post.

/**
 * This is a utility function to build two arrays used in the search.
 * 
 * @param {Array} origins - The list that will store the starting airport codes for each leg in the trip.
 * @param {Array} destinations - The list that will store the ending airport codes for each leg in the trip.
 * @returns {Object} - An object containing the two arrays of airport codes
 */
function buildStartEndArrays(tripObject, origins = [], destinations = []){
    tripObject.forEach(aLeg => {
        origins.push(aLeg.start);
        destinations.push(aLeg.end);
    }) 
    return {origins, destinations}
}
/**
 * This searches the origin and destination arrays to determine which airport is the first
 * airport in the trip.
 * 
 * @param {Object} origins - Destructed object that contains a list of start airport codes and another list of end airport codes.
 */
function findTripStart({origins, destinations}){
    let start;
    origins.some(aLegStart =>{
        //If it is not found in the destinations than it is the trip start
        if(!inDestinations(aLegStart, destinations)){
            start = aLegStart;
            return true;
        }
    });

    return start;
}
/**
 * Searches the destinations array for the trip legs start airport code 
 * 
 * @param {String} aLegStart - Airport code for the start of the leg
 * @param {Array} destinations - Array of destination airport codes
 */
function inDestinations(aLegStart, destinations){
    return destinations.find(aLegEnd => {
        return aLegStart === aLegEnd;
    })
}

Step 2 – Order the legs of the itinerary from start to finish

Now that we know which leg of the itinerary is the staring leg we can begin the process of mapping the end of this leg to the start of the next leg and so on until all the legs of the itinerary have been completed. I accomplished this by using a nested function called evaluateLegs() that is initialized with the start leg, the original array of itinerary legs, and an empty array where we will place the itinerary legs in the order that they occur. Within this function I do the following:

A – I find the current leg of the journey in the original un-ordered array of itinerary legs.

B – When the current leg is found, I push that leg to the array with the right order of itinerary legs.

C – I then remove that leg from the array that contains the original un-ordered list of itinerary legs.

D – I then call the evaluateLegs() function again passing; the array of original un-ordered journey legs, the end location of the current leg (which has been removed from the original array of un-orderd itinerary legs), and the array with the right order of itinerary legs that we are building up. The same steps are followed until all legs have been evaluated and placed in order in the array with the right order of itinerary legs.

/**
 * This function evaluates each leg of the trip looking for the links
 * between the start and end of each leg and matches them to identify
 * the order of the trip by trip leg.
 * 
 * @param {String} tripObject - The original input data of trip legs
 * @param {String} legStart - An airport name for the starting location
 * @param {Array} trip - the list of legs in the trip
 * @returns {Array} the array of ordered legs
 */
function evaluateLegs(tripObject, legStart, trip = []){
    trip.push(legStart);
    tripObject.forEach((aLeg, i) => {
        if(aLeg.start === legStart){
            tripObject.splice(i, 1);
            evaluateLegs(tripObject, aLeg.end, trip);
        }
    })
    return trip;
}

Step 3 – Print the final answer in the console

Once evaluateLegs() has exhausted the original array of un-ordered itinerary legs (i.e. it’s empty because all the objects have been sliced out of the array) I then use our newly completed array that contains all the legs of the journey in the right order to create a string of the order of locations that the itinerary will go through from start to finish. I do this using the buildTripStopsString() function which returns the final string and is printed to the console in the original createTripList() function that orchestrates the execution of this solution.

/**
 * Iterates the array of ordered trip stops and builds a string
 * representation.
 * 
 * @param {Array} tripStopsArray - An ordered Array of trip stops from start to finish
 * @return {String} - A string representation of the tripStopsArray
 */
function buildTripStopsString(tripStopsArray){
    let printedTrip = '';
    tripStopsArray.forEach((aStop, index) => {
        if(index !== tripStopsArray.length-1){
            printedTrip += aStop + ", ";
        }else{
            printedTrip += aStop;
        }
    })
    return printedTrip;
}

Result

Here is a screenshot of the output of my solution showing each destination for each leg of the itinerary in the order in which the flights will take place. Notice that this matches the answer that we were given as a part of the problem statement.

Conclusion

This is the first of many posts on code tests and the way I’ve worked my way through them. When I went back to this problem after struggling with it in the online paired programming test it took me about 45 min to come to the initial solution. I then spent about another 20 min refactoring my code to what you see in this post. I have posted this solution to GitHub. You can find it in the orderFlights.js file at the following link (https://github.com/bradnjones/codeTests) If you want to run my code, pull it from GitHub, be sure to have Node.js installed and then type node orderFlights.js from the command line and you should see the same results as the above screenshot.

I love Jesus Christ, my wife and my children. I also really enjoy using technology to help solve peoples problems. This blog will contain my thoughts primarily on these topics. All posts are my own.
Leave a Reply

Your email address will not be published. Required fields are marked *