CareerCup

Pop the flight boarding passes one at a time. Create a hash table of String to Integer. We're going to map the city to the net in and out. For departure, decrease value of net in and out, for arrival, increase value of net in and out. At the end, scan through the hash table to find +1, which is the destination, and -1, which is the departure.

not javascript, but O(n) runtime complexity and O(n) memory:

class TripData{
    String origin;
    String destination;

    public TripData(String origin, String destination){
        this.origin = origin;
        this.destination = destination;
    }
}

public static TripData getTripData(TripData[] tickets){
    if(tickets == null){
        throw new NullPointerException();
    }
    if(tickets.length == 0){
        return null;
    }

    //build implicit graph of the tickets
    HashMap<String, TripData> originToTripData = new HashMap<String, TripData>();
    HashMap<String, TripData> destinationToTripData = new HashMap<String, TripData>();
    for(TripData tripSegment : tickets){
        originToTripData.put(tripSegment.origin, tripSegment);
        destinationToTripData.put(tripSegment.destination, tripSegment);
    }

    //do dfs search from any point in the destination map to find the real origin
    TripData startPoint = tickets[0];
    String origin = null;
    while(startPoint != null){
        origin = startPoint.origin;
        startPoint = destinationToTripData.get(startPoint.origin);
    }
        
    //do dfs search from any point in the origin map to find the real destination
    startPoint = tickets[0];
    String destination = null;
    while(startPoint != null){
        destination = startPoint.destination;
        startPoint = originToTripData.get(startPoint.destination);
    }

    return new TripData(origin, destination);
}

My approach is:
- iterate through the stack
- store the cities in a hashmap. if the src city has not been stored yet, store it with a value of 1, otherwise it means that the src has become a destination and subtract by 5. (or any number > 1). if the end city has not been stored yet, store it was a value of 0, otherwise it would mean that end city is not the final destination.
- one its done, go through the hasmap and the city with a value of 0 is the destination, and the city with a value > 0 is the src.

def path(passes):
	cities = {}
	src = 0
	des = 0

	for tickets in passes:
		src = tickets[0]
		end = tickets[1]

		if src not in cities: cities[src] = 1
		else: cities[src] = cities[src] - 5
		if end not in cities: cities[end] = 0
		else: cities[end] = cities[end] - 5

	for cities, val in cities.items():
		print(cities, val)
		if val is 0: des = cities
		if val > 0: src = cities

	print(src,des)

def path(passes):
	cities = {}
	src = 0
	des = 0

	for tickets in passes:
		src = tickets[0]
		end = tickets[1]

		if src not in cities: cities[src] = 1
		else: cities[src] = cities[src] - 5
		if end not in cities: cities[end] = 0
		else: cities[end] = cities[end] - 5

	for cities, val in cities.items():
		print(cities, val)
		if val is 0: des = cities
		if val > 0: src = cities

	print(src,des)

Looking at the boarding passes (A, B) (B, C)(C, D)(D, F), we can see only the departure and destination cities appear once. And the other cities appear twice.
So, we can build a HashMap to store the city name as key and departure/destination(boolean) as value.
Iterate all boarding passes, for each city, if it isn't contained in the hashmap, store it, otherwise, remove it.
Only the departure and destination cities leave in the hashmap after visiting all boarding passes. We are done.
It is O(n) time.

1. Hashing with remaining 2 non collided elements will start,end , which can be differentiated with augmented data or further search. If 0 non collided elements -> circular.
2. Adjacency matrix with a row/column with all zeroes, if it not exists circular.
3. Graph traversal in incoming and outgoing direction to terminate when you have a node with 1 directed edge. Keep a visited flag to disambiguate circular path.

No one goes on a business trip and never comes home.

Thus every destination and arrival is given twice. Making this unsolvable. Boom.

We create a HashMap of arrival against a linked list which is partial path. We take a linked List from HashMap, gets its head h, find the LinkedList against h append the current linked list agains this linked list
{{

var Stack = require('./Stack');
var LL = require('./LinkedList');
var stack = new Stack();

var boardingPassArr = [
{depart:'SFO',arrival:'NY'},
{depart:'NDLS',arrival:'MUM'},
{depart:'DUBAI',arrival:'BER'},
{depart:'PERTH',arrival:'TOKYO'},
{depart:'MUM',arrival:'HYD'},
{depart:'HYD',arrival:'LDN'},
{depart:'CCU',arrival:'SFO'},
{depart:'LDN',arrival:'CCU'},
{depart:'TOKYO',arrival:'DUBAI'},
{depart:'BER',arrival:'NDLS'},
]

//O(n)
for(var i = 0; i<boardingPassArr.length;i++){
stack.push(boardingPassArr[i]);
}

var llHashMap = {};

//O(n)
//we will map the linkedList against the last arrival
while(true){
var poppedVal = stack.pop();
if(!poppedVal)break;

var tempLL = new LL();
tempLL.add(poppedVal.depart);
tempLL.add(poppedVal.arrival);
llHashMap[poppedVal.arrival] = tempLL;
}
//O(n^2)
//we loop through the object, pick the linkedList, get the head , find the linkedList for which this head
// is the tail, then append it to the end of this
while(true){
if(Object.keys(llHashMap).length<=1)break;
for(var arrivals in llHashMap){
var ll = llHashMap[arrivals];
if(ll){
var departure = ll.getHead().name;
if(llHashMap[departure]){ //if the head of this ll is a tail somewhere
var tailedLL = llHashMap[departure];
var llHead = ll.getHead();
tailedLL.add(llHead);
llHashMap[arrivals] = tailedLL;
delete llHashMap[departure];
}
}

}
}



function LinkedList(){
this._head = null;
}
LinkedList.prototype = {

constructor:LinkedList,
add:function(node){
if(typeof node !='object'){
node = {
name:node,
nextNode:null
};
}

if(this._head==null){
this._head = node;
}else{
var currNode = this._head;
while(currNode.nextNode!=null){

currNode =currNode.nextNode;
}
currNode.nextNode = node;
}

},
getHead:function(){
return this._head||{};
},
removeNodesFromHead:function(){
var currNode = this._head;
if(currNode){
this._head = currNode.nextNode;
}

return currNode;
}

}


function Stack(){
this._array = [];
this._size = 0;
this.maxSize = 100;
}

Stack.prototype = {

constructor:Stack,

push: function(val){
if(this.isFull()){
console.log("Stack is Full");
}else if(val){
this._array[this._size] = val;
this._size++;
}
},
pop: function(){
var poppedVal;
if(this.isEmpty()){
console.log("This stack is empty now ");
}else{
this._size --;
poppedVal = this._array[this._size];
// delete this._array[this._size-1];
this._array.splice(this._size);

}
return poppedVal;
},
isFull:function(){
return this.maxSize==this._size;
},
isEmpty:function(){
return this._size==0;
},
getStack:function(){
return this._array;
}
}
}}

function orderPasses(passList) {
  var orderedList = [];
  var count = passList.length * 2;
  var list;
  var len;
  if (Array.isArray(passList) && passList.length) {
    list = passList.slice();
    orderedList.push(list.shift());
    len = list.length + 1;
    while (orderedList.length < len && count) {
      for (var i = 0; i <= len; i++) {
        if (orderedList[0][0] === list[i][1]) {
          orderedList.unshift(list[i]);
          break;
        }
        if (orderedList[orderedList.length - 1][1] === list[i][0]) {
          orderedList.push(list[i]);
          break;
        }
      }
      count--;
    }
  }
  // to return the full itinerary
  //return orderedList.map(function(i) { return i.join(' to '); }).join('\n');

  // or for just the start and end cities
  return orderedList[0][0] + ", " + orderedList[len - 1][1];
}

var tickets = [{ departure: 'Los Angeles', arrival: 'San Francisco'},{ departure: 'San Francisco', arrival: 'New York' },{ departure: 'Moscow', arrival: 'Mali' },{ departure: 'Barcelona', arrival: 'Moscow' },{ departure: 'New York', arrival: 'Barcelona' }];
var departures = [];
var arrivals = [];

var firstDeparture = '';
var finalDestination = '';


for (var i=tickets.length; i--;) {
	var ticket = tickets[i];
	var departure = ticket.departure;
	var arrival = ticket.arrival;
	departures.push(departure);
	arrivals.push(arrival);
}

for (var i=tickets.length; i--;) {
	if (arrivals.indexOf(tickets[i].departure) < 0) {
		firstDeparture = tickets[i].departure;
	}

	if (departures.indexOf(tickets[i].arrival) < 0) {
		finalDestination = tickets[i].arrival;
	}
}

var tickets = [{ departure: 'Los Angeles', arrival: 'San Francisco'},{ departure: 'San Francisco', arrival: 'New York' },{ departure: 'Moscow', arrival: 'Mali' },{ departure: 'Barcelona', arrival: 'Moscow' },{ departure: 'New York', arrival: 'Barcelona' }];
var departures = [];
var arrivals = [];

var firstDeparture = '';
var finalDestination = '';


for (var i=tickets.length; i--;) {
	var ticket = tickets[i];
	var departure = ticket.departure;
	var arrival = ticket.arrival;
	departures.push(departure);
	arrivals.push(arrival);
}

for (var i=tickets.length; i--;) {
	if (arrivals.indexOf(tickets[i].departure) < 0) {
		firstDeparture = tickets[i].departure;
	}

	if (departures.indexOf(tickets[i].arrival) < 0) {
		finalDestination = tickets[i].arrival;
	}

}

This works in JavaScript:

var map = {};
map.tkt1 = {
source : "A",
dest : "B"
};

map.tkt2 = {
source : "B",
dest : "C"
};

map.tkt3 = {
source : "C",
dest : "D"
};

map.tkt4 = {
source : "D",
dest : "F"
};

var findSourceDestination = function (map){
	var hashMap = {};
	for (var tkt in map){
      var s = map[tkt].source;
      var d = map[tkt].dest;
  	if (!(s in hashMap))
    	hashMap[s] = -1;
    else
    	hashMap[s] = hashMap[s] - 1;
    if (!(d in hashMap))
    	hashMap[d] = 1;
    else
    	hashMap[d] = hashMap[d] + 1;
    
  }
  console.log(hashMap);
};

findSourceDestination(map);

Put <source,destination> in hashmap. Scan hashmap keys and if it does not exists in values, it's the source. Scan hashmp values and if it does not exist in the source it is the destination. To optimize at each stage while reading the pair, you can check for duplicates (search source in map values and search destination in map keys and replace the associative values with the new one). Finally you will have one pair left as source->destination.

function findStartEnd(tickets) {

    var departures = tickets.map(function(ticket) {
      return ticket.depart;
    });
    var arrivals = tickets.map(function(ticket) {
      return ticket.arrive;
    });

    function findExtraCity(a, b) {

      return a.filter(function(city) {
        return b.indexOf(city) === -1;
      })[0];
    }

    var start = findExtraCity(departures, arrivals);
    var end = findExtraCity(arrivals, departures);

    return start + ', ' + end;
}

findStartEnd( [{ depart: 'New York', arrive: 'Miami' }, { depart: 'Chicago', arrive: 'New York' }, { depart: 'Miami', arrive: 'Minneapolis' }, { depart: 'Seattle', arrive: 'Los Angeles' }, { depart: 'Minneapolis', arrive: 'Seattle' }]);

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
var ticket = tickets[i];
departures.push(ticket.departure);
arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
if(arrivals.indexOf(departures[i]) < 0) {
console.log("First Departure City is " +departures[i]);
}
if(departures.indexOf(arrivals[i]) < 0) {
console.log("First Departure City is " +arrivals[i]);
}
}
}

BizTrip();

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
	var ticket = tickets[i];
	departures.push(ticket.departure);
	arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
	if(arrivals.indexOf(departures[i]) < 0) {
		console.log("First Departure City is " +departures[i]);
	}
	if(departures.indexOf(arrivals[i]) < 0) {
		console.log("First Departure City is " +arrivals[i]);
	}
}
}

BizTrip();

function BizTrip() {
var tickets = [{departure:'SFO', arrival:'LAX'}, {departure:'JAX', arrival:'ATL'}, {departure:'LAX', arrival:'JAX'}];
var departures = [], arrivals = [];
for(var i=0; i<tickets.length; i++)
{
	var ticket = tickets[i];
	departures.push(ticket.departure);
	arrivals.push(ticket.arrival);
}
for(var i=0; i<departures.length; i++){
	if(arrivals.indexOf(departures[i]) < 0) {
		console.log("First Departure City is " +departures[i]);
	}
	if(departures.indexOf(arrivals[i]) < 0) {
		console.log("First Departure City is " +arrivals[i]);
	}
}
}

BizTrip();

Build a graph and do topological sort.

That's a graph problem where a boarding pass (edge) connectes two cities (nodes).

The question is unclear: if we want any way to reach our destination, we can do any kind of traversal, such as a DFS.

If we're looking for the shortest path (most likely), then the best is to do 2 breath first search traversals at the same time, from departure and destination: as soon as they cross, we have our shortest path.

window.onload = function() {
  var boardingPasses = [
    {depart: 'LA', arrive: 'NY'},
    {depart: 'SEA', arrive: 'PHX'},
    {depart: 'PHX', arrive: 'LA'},
    {depart: 'LON', arrive: 'SEA'}
  ];
  var arrivals = [];
  var departures = []
  var departureCity;
  var finalDestination;
  
  boardingPasses.forEach(bp => {
    arrivals.push(bp.arrive);
    departures.push(bp.depart);
  });
  
  console.log('Departure city: ' + findUnique(departures, arrivals ));
  console.log('Final Destination: ' + findUnique(arrivals, departures));
};

function findUnique(a, b) {
  return a.filter(f => !b.includes(f));
}

const flightStack = [
  ['B', 'C'],
  ['E', 'F'],
  ['C', 'D'],
  ['D', 'E'],
  ['A', 'B'],
];

const findRoute = stack => {
  const xs = flightStack
    .reduce((acc, [x, _]) => {
      acc.add(x);
      return acc;
  }, new Set());
  
  const [[_, dest]] = stack.filter(([_, x]) => {
    const exists = xs.has(x);
    if(exists)
      xs.delete(x)
    return !exists
  });
  return [xs.values().next().value, dest];
}

findRoute(flightStack)

Javascript solution.

Basically:
- The origin city cannot possibly be a destination city.
- The destination city cannot possibly be a origin city.

Therefore:

const flights = [
  ['B', 'C'],
  ['E', 'F'],
  ['C', 'D'],
  ['D', 'E'],
  ['A', 'B'],
];

const findRoute = flights => {
	let sources = [];
  let destinations = [];
  
	flights.map((flight, index) => {
  	sources.push(flight[0]);
    destinations.push(flight[1]);
  });
  
  let sourceFlight = sources.filter(source => !destinations.includes(source))[0];
  let destinationFlight = destinations.filter(destination => !sources.includes(destination))[0];
      
  console.log(sourceFlight, destinationFlight);
};

findRoute(flights);

function test(tickets) {
	const cities = {};
	for(let ticket of tickets) {
		let x = cities[ticket.source];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.source] = x-1;
		x = cities[ticket.dest];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.dest] = x+1;
    }
	let source, dest
	for(let city in cities) {
		if (cities[city] < 0) source = city;
		if (cities[city] > 0) dest = city;
    }
	return {source, dest};
}


test([
{source:'a',dest:'b'},
{source:'c',dest:'d'},
{source:'b',dest:'c'},
{source:'d',dest:'a'}
])

function test(tickets) {
	const cities = {};
	for(let ticket of tickets) {
		let x = cities[ticket.source];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.source] = x-1;
		x = cities[ticket.dest];
		if (typeof x == 'undefined') x = 0;
		cities[ticket.dest] = x+1;
    }
	let source, dest
	for(let city in cities) {
		if (cities[city] < 0) source = city;
		if (cities[city] > 0) dest = city;
    }
	return {source, dest};
}

test([
{source:'a',dest:'b'},
{source:'c',dest:'d'},
{source:'b',dest:'c'},
{source:'d',dest:'a'}
])

function Ticket(dep, dest) {
    this.dep = dep;
    this.dest = dest;
}

var t1 = new Ticket('AND', 'BOM');
var t2 = new Ticket('BOM', 'DEL');
var t3 = new Ticket('DEL', 'CCU');
var t4 = new Ticket('CCU', 'BHO');
var t5 = new Ticket('BHO', 'MAS');
var t6 = new Ticket('MAS', 'BHO');
var t7 = new Ticket('BHO', 'BLR');

var pileOfTickets = [t1, t2, t3, t4, t5, t6, t7];

function getTripEndpoints(arr) {
    var endPoints = {},
        rdep, rdest;

    pileOfTickets.forEach(function (ticket) {
        var dep = ticket.dep,
            dest = ticket.dest;
        if (endPoints[dep]) {
            delete endPoints[dep];
        } else {
            endPoints[dep] = dep;
            rdep = dep;
        }
        if (endPoints[dest]) {
            delete endPoints[dest];
        } else {
            endPoints[dest] = dest;
            rdest = dest;
        }
    });
    return [rdep, rdest];
}

getTripEndpoints(pileOfTickets);

function Ticket(dep, dest) {
    this.dep = dep;
    this.dest = dest;
}

var t1 = new Ticket('AND', 'BOM');
var t2 = new Ticket('BOM', 'DEL');
var t3 = new Ticket('DEL', 'CCU');
var t4 = new Ticket('CCU', 'BHO');
var t5 = new Ticket('BHO', 'MAS');
var t6 = new Ticket('MAS', 'BHO');
var t7 = new Ticket('BHO', 'BLR');

var pileOfTickets = [t1, t2, t3, t4, t5, t6, t7];

function getTripEndpoints(arr) {
    var endPoints = {},
        rdep, rdest;

    pileOfTickets.forEach(function (ticket) {
        var dep = ticket.dep,
            dest = ticket.dest;
        if (endPoints[dep]) {
            delete endPoints[dep];
        } else {
            endPoints[dep] = dep;
            rdep = dep;
        }
        if (endPoints[dest]) {
            delete endPoints[dest];
        } else {
            endPoints[dest] = dest;
            rdest = dest;
        }
    });
    return [rdep, rdest];
}

getTripEndpoints(pileOfTickets);