Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

5 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
show 1 more comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
1  
@Baboon: It is an algorithm, albeit a trivial one. –  vonbrand Jan 29 '13 at 12:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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