CareerCup

public List<String> reconstruct(String [][] itinerary){
		HashMap <String,String> graph = new HashMap<> ();
		HashSet <String> relation = new HashSet<> ();
		for (String [] it : itinerary) {
			graph.put(it[0], it[1]) ;
		    relation.add(it[1]) ;
		}
		
		String start = "" ;
		for (String [] it : itinerary) {
			if (!relation.contains(it[0])) {
				start = it[0] ;
			}
		}		
 		if ("".equals(start)) {
 			return new ArrayList<String> ();
 		}
 		List<String> rst = new ArrayList<> ();
 		rst.add(start) ;
 		while (graph.containsKey(start)) {
 			start = graph.get(start) ;
 			rst.add(start) ;
 		}		
		return rst ;
	}

public class AirlineTicket {

	public static void main(String[] args) {
		Map<String, String> art = new HashMap<String, String>();
		
		art.put("MUC","LHR");
		art.put("CDG", "MUC");
		art.put("SFO", "SJC");
		art.put("LHR", "SFO");
		
		String startpoint = "";

		for(Entry<String, String> en:art.entrySet()){
			
			if(!art.containsValue(en.getKey())){
				startpoint = en.getKey();
				break;
			}
		}
		
		System.out.print(startpoint);
		for(int i=0; i < art.size(); i++){
			System.out.print( " " + art.get(startpoint));
			startpoint = art.get(startpoint);
		}
		
	}

}

Create a directed graph and apply Topological Sorting.

We can reformulate the problem as following:
Given number of edges, find the path that uses all of them, which is Euler path.
So we should check If there is an Euler path, if so just find it. Simple dfs can do the job.

TreeSet<String> getSet(String[][] array){
		TreeSet<String> result = new TreeSet<String>(new Comp());
		for(int r = 0; r < array.length; r++){
			for(int c = 0; c <array[0].length; c++){
				result.add(array[r][c]);
			}
		}
		return result;
	}
	
	class Comp implements Comparator<String>{
		public int compare(String a, String b){
			return a.compareTo(b); 
		}
	}

Store in a map, prepare output in a vector.
For the first run, insert both "From" and "To" node in the vector.
If "From" node is present in the vector, insert "To" after "From" in the vector.
if "To" node is present in the vector, insert "From" after "To" in the vector.
If neither "From", nor "To" is present, hold it for the next iteration.
Repeat until map is not empty.

#include <iostream>
#include <map>
#include <vector>

using namespace std;

void printVector(vector<string> itinerary)
{
    for(vector<string>::iterator it = itinerary.begin(); it != itinerary.end(); ++it)
    {
        cout << (*it) << ",";
    }
}

int main()
{
    map <string, string> from_to;
    from_to.insert (make_pair("MUC", "LHR"));
    from_to.insert (make_pair("CDG", "MUC"));
    from_to.insert (make_pair("SFO", "SJC"));
    from_to.insert (make_pair("LHR", "SFO"));

    vector <string> itinerary;
    vector<string>::iterator found_index_first, found_index_second;
    int first_run = 1;

    for(map<string, string>::iterator it = from_to.begin();
        from_to.empty() == false; )
    {
        if (it == from_to.end() && from_to.empty() == false)
            it = from_to.begin();
        if ((found_index_first = find (itinerary.begin(), itinerary.end(), it->first)) == itinerary.end())
        {
            if ((found_index_second = find (itinerary.begin(), itinerary.end(), it->second)) == itinerary.end())
            {
                if (first_run == 1)
                {
                    first_run = 0;
                    itinerary.push_back(it->first);
                    itinerary.push_back(it->second);
                    cout << "Erasing " << it->first << " and " << it->second << endl;
                    from_to.erase(it);
                    it++;
                }
                else
                {
                    it++;
                    continue;
                }
            }
            else
            {
                itinerary.insert(found_index_second, it->first);
                from_to.erase(it);
                it++;
            }
        }
        else
        {
            itinerary.insert(found_index_first + 1, it->second);
            from_to.erase(it);
            it++;
        }
    }

    printVector(itinerary);
    return 0;
}

Operates in O(n) time, more specifically, only makes 2N passes of the data as opposed to 3N for finding the head or tail of the itinerary first. Uses approximately 2N memory.

public static List<String> getItinerary(String[][] tickets){
    //data maps
    HashMap<String, String> sourceToDestMap = new HashMap<String, String>();
    HashMap<String, String> destToSourceMap  new HashMap<String, String>();
    //map-ify the data
    for(int i = 1; i < tickets.length; i++){
        String[] ticket = tickets[i];
        sourceToDestMap.put(ticket[0], ticket[1]);
        destToSourceMap.put(ticket[1], ticket[0]);
    }
    //build the results
    LinkedList<String> itinerary = new LinkedList<String>();
    itinerary.add(tickets[0][0]);
    itinerary.add(tickets[0][1]);
    while(sourceToDestMap.size() > 0){
         //if there is a destination after the current destination, add it to the itinerary end
        String temp = sourceToDestMap.remove(itinerary.getLast());
        if(temp != null){
            itinerary.add(temp);
            destToSourceMap.remove(temp);
        }
        //if there is a source before this one, add it to the itinerary beginning
        temp = destToSourceMap.remove(itinerary.getFirst());
        if(temp != null){
            itinerary.addFirst(temp);
            sourceToDestMap.remove(temp);
        }
    }
    return itinerary;
}

// O(n), n - number of tickets. Toposort approach.

#include <iostream>
#include <string>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>

using namespace std;

void topoSort(const string& node, const unordered_map<string, string>& nodes, vector<string>& itenarary, unordered_set<string>& visited) {
    if (visited.find(node) != visited.end())
        return;
    
    visited.insert(node);
    
    auto it = nodes.find(node);
    if (it != nodes.end())
        topoSort(it->second, nodes, itenarary, visited);

    itenarary.push_back(node);
}

vector<string> buildItenarary(vector<pair<string, string>> tickets) {
    unordered_map<string, string> nodes;
    
    for (int i = 0; i != tickets.size(); ++i) {
        nodes.insert(tickets[i]);
    }
    
    vector<string> itenarary;
    unordered_set<string> visited;
    for (auto it = nodes.begin(), it_e = nodes.end(); it != it_e; ++it) {
        topoSort(it->first, nodes, itenarary, visited);
    }
    reverse(itenarary.begin(), itenarary.end());
    return itenarary;
}

int main() {
    vector<pair<string, string>> tickets;
    tickets.push_back(make_pair("MUC", "LHR"));
    tickets.push_back(make_pair("CDG", "MUC"));
    tickets.push_back(make_pair("SFO", "SJC"));
    tickets.push_back(make_pair("LHR", "SFO"));
    
    vector<string> itenarary = buildItenarary(tickets);
    for (int i = 0; i != itenarary.size(); ++i)
        cout << itenarary[i] << " ";
}

function rearrange(arr) {
var map = {}, rarr = [], k = '';
arr.forEach(function(a) {
map[a[0]] = map[map[a[1]] = a[0]]||'';
});
for(var i in map) for(var j in map)
if(map[j]==k && rarr.push(k=j)) break;
return rarr;
}

console.log(rearrange([['MUC', 'LHR'], ['CDG', 'MUC'], ['SFO', 'SJC'], ['LHR', 'SFO']]))

function rearrange(arr) {
   var map = {}, rarr = [], k = '';
   arr.forEach(function(a) { 
       map[a[0]] = map[map[a[1]] = a[0]]||''; 
   });
   for(var i in map) for(var j in map)
       if(map[j]==k && rarr.push(k=j)) break;
   return rarr;
}

console.log(rearrange([['MUC', 'LHR'], ['CDG', 'MUC'], ['SFO', 'SJC'], ['LHR', 'SFO']]))

}

function rearrange(arr) {
   var map = {}, rarr = [], k = '';
   arr.forEach(function(a) { 
       map[a[0]] = map[map[a[1]] = a[0]]||''; 
   });
   for(var i in map) for(var j in map)
       if(map[j]==k && rarr.push(k=j)) break;
   return rarr;
}

console.log(rearrange([['MUC', 'LHR'], ['CDG', 'MUC'], ['SFO', 'SJC'], ['LHR', 'SFO']]))

public class TicketMerger {
public List<Ticket> ticketList = new ArrayList<Ticket>();

public TicketMerger() {
this.ticketList.add(new Ticket("MUC", "LHR"));
this.ticketList.add(new Ticket("CDG", "MUC"));
this.ticketList.add(new Ticket("SFO", "SJC"));
this.ticketList.add(new Ticket("LHR", "SFO"));
}

public static List<String> merge(List<Ticket> list) {

List<String> result = new ArrayList<String>();
HashMap<String, Node> map = new LinkedHashMap<String, Node>();
list.stream().forEach(t -> {
Node prev = (map.containsKey(t.from)) ? map.get(t.from) : new Node(t.from, null, null);
Node next = (map.containsKey(t.to)) ? map.get(t.to) : new Node(t.to, null, null);

prev.next = next;
next.prev = prev;

map.put(t.from, prev);
map.put(t.to, next);
}
);

Node head = map.values().stream().findFirst().orElseGet(null);
while (head.prev != null) {
head = head.prev;
}

while(head != null) {
result.add(head.key);
head = head.next;
}

return result;
}

}

class Ticket{
public String from;
public String to;

public Ticket(String from, String to) {
this.from = from;
this.to = to;
}
}

class Node{
public Node prev;
public Node next;
public String key;

public Node(String key, Node prev, Node next) {
this.key = key;
this.prev = prev;
this.next = next;
}
}

public class TicketMerger {
public List<Ticket> ticketList = new ArrayList<Ticket>();

public TicketMerger() {
this.ticketList.add(new Ticket("MUC", "LHR"));
this.ticketList.add(new Ticket("CDG", "MUC"));
this.ticketList.add(new Ticket("SFO", "SJC"));
this.ticketList.add(new Ticket("LHR", "SFO"));
}

public static List<String> merge(List<Ticket> list) {

List<String> result = new ArrayList<String>();
HashMap<String, Node> map = new LinkedHashMap<String, Node>();
list.stream().forEach(t -> {
Node prev = (map.containsKey(t.from)) ? map.get(t.from) : new Node(t.from, null, null);
Node next = (map.containsKey(t.to)) ? map.get(t.to) : new Node(t.to, null, null);

prev.next = next;
next.prev = prev;

map.put(t.from, prev);
map.put(t.to, next);
}
);

Node head = map.values().stream().findFirst().orElseGet(null);
while (head.prev != null) {
head = head.prev;
}

while(head != null) {
result.add(head.key);
head = head.next;
}

return result;
}

}

class Ticket{
public String from;
public String to;

public Ticket(String from, String to) {
this.from = from;
this.to = to;
}
}

class Node{
public Node prev;
public Node next;
public String key;

public Node(String key, Node prev, Node next) {
this.key = key;
this.prev = prev;
this.next = next;
}
}

JavaScript:

var tickets = [ ['MUC', 'LHR'], ['CDG', 'MUC'], ['SFO', 'SJC'], ['LHR', 'SFO'] ];
var obj = {};

for (var i in tickets){
	obj [ tickets[i][0] ] = tickets[i][1];

	if (self.first)
		if ( first == tickets[i][1] )
			first = tickets[i][0]
	else
		first = tickets[i][0];
}

indexObj = first;
console.log (indexObj);
for (var i in obj){
	console.log ( obj [ indexObj ] );
	indexObj = obj [ indexObj ];
}

output: CDG MUC LHR SFO SJC

Here is the idea of the solution:
1. Create a hash map of key and value (startCity and destCity).
2. In order to know the initial start city, create a set of all destination cities, which means that the start city will be the one which is not in the destination cities set.
3. In order to get the final itinerary path, start looking into the Hashmap by the start city and then add it to your output string, and then make the key of the startCity, the current startCity and loop until the end.

Here is the code:
{{

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class ItineraryBuilder {

static class Ticket {
String from;
String to;
Ticket parent;
Ticket child;

public Ticket(String from, String to) {
this.from = from;
this.to = to;
}
}


public static String getCompleteItinerary(List<Ticket> input) {
Map<String, String> tickets = new HashMap<String, String>();
Set<String> destinations = new HashSet<String>();

// Create a map of (Source, Destination)s and destinations set...
for (Ticket ticket : input) {
tickets.put(ticket.from, ticket.to);

destinations.add(ticket.to);
}

// Get the start node (the node which does not exist in destinations) ...
String startCity = null;

for (Ticket ticket : input) {
if (! destinations.contains(ticket.from)) {
startCity = ticket.from;
break;
}
}

if (startCity == null) {
throw new RuntimeException("No valid start city is there ...");
}

// Get the string path from the tickets map starting with the start city ...
String output = "[";

while (tickets.get(startCity) != null) {

output += startCity + ", ";

startCity = tickets.get(startCity);
}

output += startCity + "]";

return output;
}

public static void main(String[] args) {
Ticket t1 = new Ticket("MUC", "LHR");
Ticket t2 = new Ticket("GDC", "MUC");
Ticket t3 = new Ticket("SFO", "SJC");
Ticket t4 = new Ticket("LHR", "SFO");

List<Ticket> list = new ArrayList<Ticket>();

list.add(t1);
list.add(t2);
list.add(t3);
list.add(t4);

System.out.println(getCompleteItinerary(list));
}
}
}}

import java.util.LinkedHashMap;
import java.util.Map;


public class AirTicketPathReconstruct {
public static void main(String[] args) {
Map<String,String> path = new LinkedHashMap<String,String>();
path.put("MUC","LHR");
path.put("CDG", "MUC");
path.put("SFO", "SJC");
path.put("LHR", "SFO");
reconstructPath(path);
}

private static void reconstructPath(Map<String, String> path) {
Map<String,String> newpath = new LinkedHashMap<String,String>();
String nextSrc=null;
for(Map.Entry<String, String> entry: path.entrySet()){
String src = entry.getKey();
String dest =entry.getValue();
if(!path.values().contains(src)){
newpath.put(src, dest);
nextSrc = dest;
}
}
String nextdest = path.get(nextSrc);
while(nextdest!=null){
newpath.put(nextSrc, nextdest);
nextSrc = nextdest;
nextdest = path.get(nextSrc);
}

System.out.println("\n Old path : " + path);

System.out.print("\n Reconstructed Path : " + newpath);
}
}

The problem statement says given bunch of tickets. This needs to be clarified if all given tickets represent a path or there could be tickets which are unrelated or there could be group of tickets for different path.
Lets assume simple case where all tickets are guaranteed to create a path from start to the end,
We can either use Directed Graph approach as Nitin pointed out, but for this problem that would be complex. Alternatively we can use simple approach.
e.g. Going from A to E via B, C, D (A, B) (B, C), (C, D), (D, E)
1. Iterate through each ticket
2. Add source and Destination into the Set. Also keep additional metadata to indicate if added entry is source or destination.
3. However If source of Destination is already in the set remove it.
4. Add Entry into the Map with Key Value as Source and Destination
5. At the end you will have two nodes in the set, start and end point.

Well, now you are loaded with start and end of the tour, just get started.
6. Start from Source left in the Set.
7. Look in the Map for destination which is B
Repeat Step 6-7 till you reach to E.

Note: There is possibility of the Loop within the tour say
e.g. Going from A to E via B, C (A, B) (B, C), (C, B), (B, E)
You will need to handle this case and solution will become more complex. Above problem is just loop of length 1 but it can actually be very large.

This should do it in Python:

# Assuming data is a list of lists
data = [
    ['MUC', 'LHR'],
    ['CDG', 'MUC'],
    ['SFO', 'SJC'],
    ['LHR', 'SFO']
]

def flatten(data):
    destinations = [d[1] for d in data]
    beginning = [x[0] for x in data if x[0] not in destinations][0]
    itinerary = {x[0]: x[1] for x in data}
    cities = set(city for flight in data for city in flight)
    output = [beginning, ]

    while len(output) != len(cities):
        last = output[-1]
        output.append(itinerary[last])

    return output

{{
var tickets = [
['MUC', 'LHR'],
['CDG', 'MUC'],
['SFO', 'SJC'],
['LHR', 'SFO'],
];

//enter first ticket
var itinerary = tickets.pop();

//repeat until all tickets are match
//(could become an endless loop)
while(tickets.length > 0) {

var ticket = tickets.pop();

var tFrom = ticket[0];
var tTo = ticket[1];

var c1 = itinerary[0];
var c2 = itinerary[itinerary.length-1];

//connected From of itinerary with To of ticket
if(c1 === tTo) {
itinerary.unshift(tFrom);
continue;
}

//connected To of itinerary with From of ticket
if(c2 === tFrom) {
itinerary.push(tTo);
continue;
}

//couldn't find matches, put back into list of tickets
tickets.unshift(ticket);
}

console.log('itinerary', itinerary);
}}

JavaScript:

{{
var tickets = [
['MUC', 'LHR'],
['CDG', 'MUC'],
['SFO', 'SJC'],
['LHR', 'SFO'],
];

//enter first ticket
var itinerary = tickets.pop();

//repeat until all tickets are match
//(could become an endless loop)
while(tickets.length > 0) {

var ticket = tickets.pop();

var tFrom = ticket[0];
var tTo = ticket[1];

var c1 = itinerary[0];
var c2 = itinerary[itinerary.length-1];

//connected From of itinerary with To of ticket
if(c1 === tTo) {
itinerary.unshift(tFrom);
continue;
}

//connected To of itinerary with From of ticket
if(c2 === tFrom) {
itinerary.push(tTo);
continue;
}

//couldn't find matches, put back into list of tickets
tickets.unshift(ticket);
}

console.log('itinerary', itinerary);
}}

var tickets = [
    ['MUC', 'LHR'],
    ['CDG', 'MUC'],
    ['SFO', 'SJC'],
    ['LHR', 'SFO'],
];

//enter first ticket
var itinerary = tickets.pop();

//repeat until all tickets are match
//(could become an endless loop)
while(tickets.length > 0) {

    var ticket = tickets.pop();

    var tFrom = ticket[0];
    var tTo = ticket[1];

    var c1 = itinerary[0];
    var c2 = itinerary[itinerary.length-1];

    //connected From of itinerary with To of ticket
    if(c1 === tTo) {
        itinerary.unshift(tFrom);
        continue;
    }

    //connected To of itinerary with From of ticket
    if(c2 === tFrom) {
        itinerary.push(tTo);
        continue;
    }
    
    //couldn't find matches, put back into list of tickets
    tickets.unshift(ticket);
}

console.log('itinerary', itinerary);

Simple O(n^2) solution.
On a closure observation, this is a sub-quadratic solution

public Node contructIternary(List<Node> tickets){
		if(tickets == null || tickets.isEmpty()){
			return null;
		}

		Node startNode = tickets.get(0);
		Node endNode = tickets.get(0);

		tickets = tickets.subList(1, tickets.size());

		while(!tickets.isEmpty()){

			for(Iterator<Node> ticketsItr = tickets.iterator(); ticketsItr.hasNext()){
				Node ticket = tickets.next();
				if(startNode.start.equals(ticket.end)){
					startNode.prev = ticket;
					startNode = ticket;
					ticketsItr.remove();
				}else if(endNode.equals(ticket.start)){
					endNode.next = ticket;
					endNode = ticket;
					ticketsItr.remove();
				}
			}
		}
		return startNode;
	}

struct Apt {
    struct Apt *In;
    struct Apt *Out;
    string  AptName;
};

typedef struct Apt Apt_t;
typedef map<string, size_t> AptMap_t;
typedef map<string, size_t>::iterator AptMapIter;

static AptMap_t AptMap;

void
CreateAptLink(string Origin, string Dest)
{
    Apt_t *orig = NULL, *dest = NULL;
    if (AptMap.count(Origin) > 0) {
        orig = reinterpret_cast<Apt_t*>(AptMap[Origin]);
    }
    else {
        orig = new Apt_t;
        orig->In = orig->Out = NULL;
        AptMap.insert(pair<string, size_t>(Origin, reinterpret_cast<size_t>(orig)));
    }
    if (AptMap.count(Dest) > 0) {
        dest = reinterpret_cast<Apt_t*>(AptMap[Dest]);
    }
    else {
        dest = new Apt_t;
        dest->In = dest->Out = NULL;
        AptMap.insert(pair<string, size_t>(Dest, reinterpret_cast<size_t>(dest)));
    }
    
    orig->Out = dest;
    orig->AptName = Origin;
    dest->AptName = Dest;
    dest->In = orig;
}

void 
PrintFinalIt(Apt_t *pSrc)
{
    Apt_t *pCurr = pSrc;
    while (pCurr) {
        cout << pCurr->AptName << "-->";
        pCurr = pCurr->Out;
    }
}

int main()
{
    CreateAptLink("CDG", "MUL");
    CreateAptLink("MUL", "LHR");
    CreateAptLink("LHR", "SFO");
    CreateAptLink("SFO", "SJC");
    
    AptMapIter iter = AptMap.begin();
    for (; iter != AptMap.end(); iter++) {
        if ((reinterpret_cast<Apt_t *>(iter->second))->In == NULL) {
            //cout << "Source is: " << iter->first << endl;
            PrintFinalIt((reinterpret_cast<Apt_t *>(iter->second)));
            break;
        }
    }
    
    return(0);
}

The problem can be resolved by doing an Euler traversal in the tickets graph. This ensures that a ticket is only considered once, but an airport can be considered multiple times. The starting point will be that airport which the difference between flights leaving and flights arriving equal to 1.
This solution accepts cycles.

#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <string>
#include <iterator>
#include <unordered_map>

using namespace std;

void euler_path(unordered_map<string, list<string>>& adj, string start, vector<string>& stk)
{
  while(!adj[start].empty())
  {
    string next = adj[start].front();
    //In an euler path computation we don't want to re-visit an edge. So we delete it
    adj[start].pop_front();
    euler_path(adj, next, stk);
  }

  //Almost like topological sort in a DAG, we put the processed vertex in a stack
  stk.push_back(start);
}

vector<string> order_tickets(const vector<tuple<string, string>>& tickets)
{
  unordered_map<string, int> src;
  unordered_map<string, list<string>> adj;
  if(tickets.size() < 1)
    return vector<string>();

  //For each airport compute the difference between how many flights
  // have it as a source and how many flights have it as a destination
  // Also construct the adjacency list.
  for(auto tick: tickets)
  {
    auto s = get<0>(tick);
    auto d = get<1>(tick);
    adj[s].push_back(d);
    ++src[s];
    --src[d];
  }

  //Find the starting point.
  string start = get<0>(tickets[0]);
  for(auto s: src)
  {
    //We assume that there is a single starting point
    if(get<1>(s) > 0)
    {
      start = get<0>(s);
      break;
    }
  }

  //Find the euler path from the start
  vector<string> stk;
  stk.reserve(tickets.size() + 1);
  euler_path(adj, start, stk);

  //Stack has the path in reverse
  reverse(stk.begin(), stk.end());
  return stk;
}

int main()
{
  vector<tuple<string, string>> tickets{{"LHR", "SFO"}, {"MUC", "LHR"}, {"CDG", "MUC"}, {"MUC", "OTP"}, {"VIE", "MUC"}, {"OTP", "IAS"}, {"IAS", "VIE"}, {"SFO", "SJC"}};
  vector<string> expected{"CDG", "MUC", "OTP", "IAS", "VIE", "MUC", "LHR", "SFO", "SJC"};
  auto actual = order_tickets(tickets);
  if(expected != actual)
  {
    cerr << "Ticket order is wrong ";
    copy(actual.begin(), actual.end(), ostream_iterator<string>(cerr, " "));
    cerr << endl;
  }
  else
    cout << "Success!!!" << endl;
  return 0;
}

We can construct a binary search tree where left child represents from and right child represents to.Then we can traverse in-order to print the result
Example

MUC
                        CDG                      LHR
                                                                 SFO
                                                                          SJC

Traversing this inorder will give correct result