CareerCup

If there's no assumption about the number of times you visited each place then it may not be possible to reconstruct your journey.

For instance, suppose your journey was as follows:
a --> b --> c --> a --> d --> f --> a

Tickets: (a,b), (b,c), (c,a), (a,d), (d,f), (f,a)

You know your end point is a, how do you know which one of the following journeys was yours?
1. a --> b --> c --> a --> d --> e --> a
2. a --> d --> e --> a --> b --> c --> a

Topological sort.

Observation from the info provided in question:
1. If I do not remember the order in which I visited these places, than off course i dont remember the starting location.
2. But I know my current location - end of my journey.
3. End place of one journey is starting place for another journey.

So on the basis of these observation here is my algorithm:

String[] places = new [N+1]; // N-1 links required to connect N places
Step 1: Store all tickets in a HashMap with end location as key and ticket as value.
		It will take O(N) time and O(N) space. Where N = number of tickets		

Step 2: String endLocation= current_location;
        location = N+1;
		for( ticket 1 to N) {
           Ticket ticket = map.getTicket(endLocation)// from HashMap.		
 		   places[location--] = endLocation;
		   endLocation = ticket.getStartPlace();
		 }
		 places[location--] = ticket.getStartPlace();
Step 3: return places; // it is an array of places in visited sequence.

We can construct possible paths if and only if:

* there is at most one vertex with in-degree != out-degree
* if such a vertex exists, then in-degree = out-degree - 1

If the above holds and no vertex has out-degree > 1, then we can construct the path.

Otherwise, to find the exact path from all possible paths, then for any vertex v of out-degree > 1 there must be at most one path from v that contains a cycle. If any such vertex violates this principle, then we cannot determine which of the possible paths is the correct one.

Assuming that the all the travels was made by airplanes, I think it's possible build the following solution:
-> Build a graph G: where each city visited is a vertex and there a edge between each pair of cities that are in a travel ticket. Obviously G is a directed graph.
-> If the graph don't have cycles then is possible reconstruct the trip by a topological sort procedure.
-> Otherwise, it's impossible reconstruct the certain path.

for(i=0;i<len;i++)
		journey.insert(make_pair(dist[i],start[i]));

	for(i=0;i<len;i++)
	{
		map<string,string>::iterator p;
		p=journey.find(cur);
		roadMap="->" + (*p).second + roadMap;
		cur=(*p).second;
	}
	cout<<roadMap<<endl;

First create hash map having destination as a key, pass current location (trip destination), hashmap and reference to path vector.
The total complexity is O(N^2) where N is number of tickets and square time is spent while creating a hashmap, while the method itself has O(N + 1) complexity:

bool reconstructPath(std::string &currentLoc,
                     std::unordered_map<std::string, std::string> &tickets,
                     std::vector<std::string> &path) {

    path.resize(tickets.size() + 1);
    path[0] = currentLoc;
    for(int i = 1; i < path.size(); ++i) {
        auto it = tickets.find(path[i - 1]);
        if(it == tickets.end()) {
            return false;
        } else {
            path[i] = it->second;
        }
    }
    return true;
}

Constructing the graph starting from the final location. Then the problem is of finding the vertex cover.
Here we can also consider the possibility that one city is visited twice. But in this case the answer may not be unique.

void reconstructRoute(Ticket[] tickets, Place curLocation){
	HashMap<Place, ArrayList<Ticket>> map = new HashMap<Place, ArrayList<Ticket>>();
	for(Ticket t : tickets){
		Place begin = t.from;
		Place end = t.to;
		ArrayList<Ticket> arr;
		if(map.hasKey(begin)){
			arr = map.get(begin);
		}
		else {
			arr = new ArrayList<Ticket>();
		}
		arr.add(t);
		map.put(begin, arr);
		if(map.hasKey(end)){
			arr = map.get(end);
		}
		else{
			arr = new ArrayList<Ticket>();
		}
		arr.add(t);
		map.put(end, arr);
	}
	ArrayList<Place> route = new ArrayList<Place>();
	Place c = curLocation;
	for(int i = 0; i<tickets.length; i++){
		Ticket t = map.get(c);
		route.add(c);
		c = t.from;
	}
	route.add(c);
	for(int i = route.size()-1; i>=0; i--){
		System.out.println(route.get(i));
	}
}

Ticket from one city to the other is an edge.

Given a bunch of edges, the question asks you to tell if there exists a path such that you visit each edge exactly once.
In other words, a Eulerian Path.

Below is the necessary and sufficient condition for a Eulerian path in directed graphs. (Source: Wikipedia)
A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.

This however is a necessary condition but not sufficient.
Existence of a Eulerian path can actually be deduced from common sense. If you haven't left every city you have been to except for the one you are currently in, you wouldn't end up where you are.

But we are looking for one and only one Eulerian path to exist, which is possible only if every vertex has an indegree and outdegree of at most 2.

You have to do topological sorting for Euler circuit duhhhhhhhhhhhhhh

Assuming you don't know where you are:

1. If in-degree of every node is equal to its out-degree
	=> start-node is the same as end-node
	=> no way to identify the start and end nodes
	=> no way to reconstruct the route
2. Otherwise, 
	* start node A is one with in-degree(A) = out-degree(A) + 1,
	* end node B is one with in-degree(B) = out-degree(B) - 1
  	* we can find the shortest path from A to B
	* let's examine if the nodes on the path have extra out-links except those participating in the shortest path
  2.1 If every node on the path has at most one extra link
	=> our route should follow this link before the link participating in the shortest path
	=> we can still reconstruct the route
  2.2. Otherwise, (there is a node with > 1 extra out-link)
	=> there is no way to determine which link to follow first
	=> no way to reconstruct the route

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class AirplaneTktProblem {
Map<String, Tkt> tripMap = new HashMap<String, Tkt>();

public static void main(String[] args) {
ArrayList<Tkt> tktList = new ArrayList<Tkt>();
AirplaneTktProblem atp = new AirplaneTktProblem();

}

// make a Arraylist of tkt which is a departure and destination pair

// input it
public void inputTrip(ArrayList<Tkt> tktList) {
for (Tkt t : tktList) {
tripMap.put(t.to, t);
}
}

// traverse the first tkt and traverse the end of the trip
public Tkt traverseToTheFirstTkt(ArrayList<Tkt> tktList) {
Tkt firstTkt = tktList.get(1);

while (tripMap.get(firstTkt.from) != null) {
firstTkt = tripMap.get(firstTkt.from);
}
return firstTkt;
}

// traverse the begining of the trip using the last tkt
public void BuildTheTrip(ArrayList<Tkt> tktList) {
inputTrip(tktList);
Tkt Firsttkt = traverseToTheFirstTkt(tktList);
tktList.clear();
tktList.add(Firsttkt);
while (tripMap.get(Firsttkt.from) != null) {
tktList.add(tripMap.get(Firsttkt.from));
}
}

class Tkt {
private final String from;
private final String to;

public Tkt(String departure, String arrival) {
super();
this.from = departure;
this.to = arrival;
}

}
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class AirplaneTktProblem {
    Map<String, Tkt> tripMap = new HashMap<String, Tkt>();

    public static void main(String[] args) {
	ArrayList<Tkt> tktList = new ArrayList<Tkt>();
	AirplaneTktProblem atp = new AirplaneTktProblem();

    }

    // make a Arraylist of tkt which is a departure and destination pair

    // input it
    public void inputTrip(ArrayList<Tkt> tktList) {
	for (Tkt t : tktList) {
	    tripMap.put(t.to, t);
	}
    }

    // traverse the first tkt and traverse the end of the trip
    public Tkt traverseToTheFirstTkt(ArrayList<Tkt> tktList) {
	Tkt firstTkt = tktList.get(1);

	while (tripMap.get(firstTkt.from) != null) {
	    firstTkt = tripMap.get(firstTkt.from);
	}
	return firstTkt;
    }

    // traverse the begining of the trip using the last tkt
    public void BuildTheTrip(ArrayList<Tkt> tktList) {
	inputTrip(tktList);
	Tkt Firsttkt = traverseToTheFirstTkt(tktList);
	tktList.clear();
	tktList.add(Firsttkt);
	while (tripMap.get(Firsttkt.from) != null) {
	    tktList.add(tripMap.get(Firsttkt.from));
	}
    }

    class Tkt {
	private final String from;
	private final String to;

	public Tkt(String departure, String arrival) {
	    super();
	    this.from = departure;
	    this.to = arrival;
	}

    }
}

public class AirplaneTktProblem {
    Map<String, Tkt> tripMap = new HashMap<String, Tkt>();

    public static void main(String[] args) {
	ArrayList<Tkt> tktList = new ArrayList<Tkt>();
	AirplaneTktProblem atp = new AirplaneTktProblem();

    }

    // make a Arraylist of tkt which is a departure and destination pair

    // input it
    public void inputTrip(ArrayList<Tkt> tktList) {
	for (Tkt t : tktList) {
	    tripMap.put(t.to, t);
	}
    }

    // traverse the first tkt and traverse the end of the trip
    public Tkt traverseToTheFirstTkt(ArrayList<Tkt> tktList) {
	Tkt firstTkt = tktList.get(1);

	while (tripMap.get(firstTkt.from) != null) {
	    firstTkt = tripMap.get(firstTkt.from);
	}
	return firstTkt;
    }

    // traverse the begining of the trip using the last tkt
    public void BuildTheTrip(ArrayList<Tkt> tktList) {
	inputTrip(tktList);
	Tkt Firsttkt = traverseToTheFirstTkt(tktList);
	tktList.clear();
	tktList.add(Firsttkt);
	while (tripMap.get(Firsttkt.from) != null) {
	    tktList.add(tripMap.get(Firsttkt.from));
	}
    }

    class Tkt {
	private final String from;
	private final String to;

	public Tkt(String departure, String arrival) {
	    super();
	    this.from = departure;
	    this.to = arrival;
	}

    }
}

The code stands on two premises:
1) There is only one starting point, i.e. it's not a forest
2) The route is not circulated

private ArrayList<String> getRoute(Ticket[] tickets) {
		HashMap<String, String> map = new HashMap<String, String>();
		
		for (Ticket ticket : tickets) {
			if (!map.containsKey(ticket.departure)) {
				map.put(ticket.departure, ticket.destination);
			}
		}
		
		String start = "Circulated journey, can't find the starting point";
		for (String key : map.keySet()) {
			if (!map.containsValue(key)) start = key;
		}
		
		ArrayList<String> route = new ArrayList<String>();
		route.add(start);
		while (map.containsKey(start)) {
			route.add(map.get(start));
			start = map.get(start);
		}
		
		return route;
	}

	private class Ticket {
		String departure;
		String destination;
		
		Ticket(String departure, String destination) {
			this.departure = departure;
			this.destination = destination;
		}
	}

yes... start with the place i am currently...match it with the ticket...and then i get my preceeding location...so on

I remember this question was once asked in a "Long Contest" on codechef.com. Here is how I solved it.

You need an Associative Array (most suitably a HashMap) to solve this problem. Suppose each ticket is of the form "A->B" (means the ticket from 'A' to destination 'B').
Example input:
F->G
B->C
E->F
C->D
D->E
A->B
Output:
A->B->C->D->E->F->G

1) Make an associative array (or HashMap) which maps strings to strings. For 
   example the ticket "A->B" will be stored in associative array as
   map["A"] = "B".

2) Find the starting station (the station which appears only as a key in the 
   map and not as a value).

   Station s = starting station;
   //while there is a destination corresponding to station s
   while(map[s] != empty) {
   	print s;
   	s = map[s];
   }
3) That's it. You did it :)

Construct directed graph with places as nodes and directed edge between two place v1,v2 if v1 was start loaction in some ticket and v2 was destination in the same ticket.Now use topological sorting algorithm.

Another approach, If beyond source and destination info there are date-time info in tickets:
-> Sort the tickets registers by increasing date-time
-> Build the trip by sorted tickets.

typedef struct {
	string source;
	string dest;
	string date_time; // well formed format
}Ticket;

bool cmp(Ticket t1, Ticket t2) {
	if (t1.date_time < t2.date_time)
		return true;
	return false;
}
/* Input: T, tickets set
* Output: trip, sequence of cities in the trip
*/
void build_trip(vector<Ticket> &T, vector<string> &trip) {
	sort(T.begin, T.end());
	trip.push_back(T[0].source);

	for (int i = 0; i < T.size(); i++) {
		trip.push_back(T[i].dest);
	}
}

If ask me... then:
The question is: "Could you reconstruct your journey?"
So the answer is: If there are no cycles -> yes, otherwise it could be reconstructed but without guarantee that order is the same.

A sorting problem