# 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 > 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).

-
Look at the tickets date and time. (Ok, just joking) –  petervaz Jan 28 '13 at 15:26
You should consider giving feedback on the answers. –  Baboon Jan 28 '13 at 23:25

Several answers have already been given, but I still think this is somewhat cuter.

Construct a bidirectional map $m: \mathcal{C} \to \mathcal{C}$ from cities to cities. This map means that if $m(x) = y$, then there is a path of tickets such that you start in $x$, take an arbitrarily long path (using only your tickets), and end up in $y$. The map encodes connected component with entry and exit points.

Now, the algorithm is as follows: On ticket $(u,v)$,

• if $m(v)$ exists, let $m(u) = m(v)$ and delete $m(v)$,
• if $m^{-1}(u)$ exists, say $m^{-1}(u) = w$, let $m(w) = v$, and
• else add $m(u) = v$.

What you end up with, should be one entry in $m$, $m(s) = t$, where $s$ is starting city and $t$ is destination.

This is under the assumption that the tickets you have form a path.

-

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.

-
It's not a linear time algorithm. (Specially in space). –  user742 Jan 28 '13 at 8:59
@SaeedAmiri: Why is it not linear time or space (on average, when using hash tables)? Size of task is number of tickets, each ticked is only processed once, there can't be more sources/destinations than tickets, so the number of entries is also at most linear. –  Jan Hudec Jan 28 '13 at 9:09
Actually for oriented graph, you need to compare number of times the city appears as source to number of times it appears as destination. –  Jan Hudec Jan 28 '13 at 9:10
If A!=B (which is what I reasoned with), A could be the city that appeared 0 time as destination, and B the one that appeared 0 time as a departure, right? –  Antoine Lassauzay Jan 29 '13 at 5:26
Anyhow, the interviewer who asked me this question said there was a better approach for the time for time when I proposed a similar solution, because it involved two loops : one to create the map, and one to find A and B in the map. I am not sure how to formally measure if your solution is superior to the solutions given by Pal GD or me. –  Antoine Lassauzay Jan 29 '13 at 5:30

Yuval's answer is on right track, but being oriented graph, you need to compare number of times a city appears as arrival with number of times it appears as departure.

Overall departure is the city that appears more times as departure than as arrival (usually once as departure and never as arrival) and overall arrival is the city that appears more times as arrival than as departure (again usually once as arrival and never as departure).

-

The train tickets form a directed walk. The departure place will have one more leaving arc than entering arcs, and the destination one more entering arc than leaving ones.

-

You don't have to reorder everything:

A is the ticket that has no matching departure
B is the ticket that has no matching destination

When you're looking for efficiency, abuse the specifics of the system.

-
With a linear or quadratic algorithm? –  Pål GD Jan 28 '13 at 18:39
@PålGD I'm saying you don't need an algorithm. –  Baboon Jan 28 '13 at 18:42
Thanks for your answer. This was my first idea conceptually but I don't understand how could you find A and B without an algorithm ? –  Antoine Lassauzay Jan 29 '13 at 5:08
It depends what you consider an algorithm. Going through a collection once to find an element matching a boolean condition is trivial. –  Baboon Jan 29 '13 at 9:36
@Baboon: It is an algorithm, albeit a trivial one. –  vonbrand Jan 29 '13 at 12:42