5
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ Look at the tickets date and time. (Ok, just joking) $\endgroup$
    – petervaz
    Commented Jan 28, 2013 at 15:26
  • $\begingroup$ You should consider giving feedback on the answers. $\endgroup$
    – Louis Kottmann
    Commented Jan 28, 2013 at 23:25

5 Answers 5

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
0
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ It's not a linear time algorithm. (Specially in space). $\endgroup$
    – user742
    Commented Jan 28, 2013 at 8:59
  • $\begingroup$ @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. $\endgroup$
    – Jan Hudec
    Commented Jan 28, 2013 at 9:09
  • $\begingroup$ Actually for oriented graph, you need to compare number of times the city appears as source to number of times it appears as destination. $\endgroup$
    – Jan Hudec
    Commented Jan 28, 2013 at 9:10
  • $\begingroup$ 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? $\endgroup$
    – Antoine Lassauzay
    Commented Jan 29, 2013 at 5:26
  • $\begingroup$ 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. $\endgroup$
    – Antoine Lassauzay
    Commented Jan 29, 2013 at 5:30
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ With a linear or quadratic algorithm? $\endgroup$
    – John Kemeny
    Commented Jan 28, 2013 at 18:39
  • $\begingroup$ @PålGD I'm saying you don't need an algorithm. $\endgroup$
    – Louis Kottmann
    Commented Jan 28, 2013 at 18:42
  • $\begingroup$ 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 ? $\endgroup$
    – Antoine Lassauzay
    Commented Jan 29, 2013 at 5:08
  • $\begingroup$ It depends what you consider an algorithm. Going through a collection once to find an element matching a boolean condition is trivial. $\endgroup$
    – Louis Kottmann
    Commented Jan 29, 2013 at 9:36
  • 1
    $\begingroup$ @Baboon: It is an algorithm, albeit a trivial one. $\endgroup$
    – vonbrand
    Commented Jan 29, 2013 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.