sortFlights.js

/*
* The problem:
* Imagine you are on a long business trip with many connecting
* flights. You have a handful of tickets - each with an origin city
* and a destination - but the tickets are not in order. This algorithm
* sorts the tickets chronologically, starting with your home city and
* ending with your final destination. See bottom for an example. 
*/

/*
* @desc Sort connecting flights in O(n) time
* @param {Array} tickets
* @returns {Array}
* @throws Error
*/
function sortTickets(tickets) {
  'use strict';

  var sortedTickets = [],
      fromCitiesMap = {},
      toCitiesMap = {};

  if (!Array.isArray(tickets)) {
    throw new Error('Tickets must be an array');
  }

  tickets.forEach(function(ticket) {
    fromCitiesMap[ticket.from] = ticket;
    toCitiesMap[ticket.to] = true;
  });

  var origin;

  for (var i=0, l=tickets.length; i<l; i++) {
    if (!toCitiesMap.hasOwnProperty(tickets[i].from)) {
      origin = tickets[i];
      break;
    }
  }

  if (!origin) {
    throw new Error('Could not determine start city because there ' +
      'appears to be circular condition in your route. Are you ' +
      'flying back and forth between the same cities?');
  }

  sortedTickets.push(origin);
  while ((origin = fromCitiesMap[origin.to])) {
    sortedTickets.push(origin);
  }

  return sortedTickets;
}


var tickets = [
  {from: 'Chicago', to: 'Atlanta'},
  {from: 'Seattle', to: 'Chicago'},
  {from: 'Boston', to: 'Dublin'},
  {from: 'Atlanta', to: 'Boston'}
];

var sortedTickets = sortTickets(tickets);

// A few basic tests
console.assert(sortedTickets[0].from === 'Seattle', 'The starting city should be Seattle');
console.assert(sortedTickets[sortedTickets.length - 1].to === 'Dublin', 'The final destination should be Dublin.');