Find the origin and the destination of a trip from a serie of tickets I was asked to design an algorithm that solves the following problem :


  Consider a travel from city A to city B, made of several trips by
  train through other cities in between. With an access to the
  unordered list of train tickets from which you can read the cities of
  departure and arrival of each trip, find A and B.


Unfortunately, I was unable to give an efficient algorithm when I needed to (in pseudo code), but once I got home, I came up with this answer (in JavaScript).

var tickets = [
    {from:'Paris', to:'Berlin'},
    {from:'London', to:'Paris'},
    {from:'Zurich', to:'Milan'},
    {from:'Berlin', to:'Zurich'}
    ];

function getTrip(tickets)
{
    var ticket = tickets.shift();
    var trip = {from:ticket.from, to:ticket.to};

    while(tickets.length &gt; 0) 
    {
        ticket = tickets.shift();

        if(ticket.from == trip.to)
        {
            trip.to = ticket.to;
        }
        else if(ticket.to == trip.from)
        {
            trip.from = ticket.from;
        }
        else
        {
            tickets.push(ticket);
        }
    }

    return trip;
}

var trip = getTrip(tickets);

console.log('The trip was from %s to %s', trip.from, trip.to);


While this might look like a very simple problem, I am still curious to see if there is a more efficient solution (for both time and space) or simply considerations I completely forgot. This may not need to be in JavaScript (especially if the language gives greater control over some aspects of the problem).
Using a hash table, record for each city mentioned how many times it was mentioned as a source and how many as destination. The source of the trip is the city that has appeared as a source an odd number of times, and similarly for the destination of the trip. That's linear time and space (with high probability).

Also, as Jan comments, the statistic that should be odd is the total number of times that the city has appeared. If a city appeared an odd number of times, then it is the source if it appeared as a source more than as a destination, and vice versa for destination.