Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
9
of 9 vote

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 ;
	}

- Scott May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You can break out of the loop after "start = it[0];"

- T.S. June 01, 2015 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

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);
		}
		
	}

}

- Shakti May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

perfect..

- blah_blah May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Nice! we don't need to do actual toposort here.

- Sergey May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

I am afraid that if itinerary contains loops ( like 1-2-3-1-4-5-1-6) then your map will loose 1-2 and 1-4 ...)

- Oleg G May 19, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 votes

Hi By using the containsValue method, you are basically making your implementation run O(N^2) because it take O(N) time to search if that value is there or not. What you can do is save the normal itenary that is given and also a reverse of that itenary i.e. in another hash map store "destination" as key and "source" as value. Now all you have to do is find if the key exists in this second hash map while iterating over the original itenary. I hope I made sense.

- madhur.eng May 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
3
of 3 vote

Create a directed graph and apply Topological Sorting.

- Nitin Gupta May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

This works but is a heavy solution for this simple case.
In this case we only need to find the first node n that does not have any incoming edge. After that, simply look for the next node whose src == n.dst and repeat until all nodes are resolved.
However, still bounded by O(n^2) due to the first step for finding the first node.

- JW May 22, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

But topological ordering of Cyclic graph will not be correct. How can we handle if there is cycle

- ash.taunk3 May 24, 2015 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

- Darkhan.Imangaliev May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Reading the problem statement there is only one path..

- rushikesh90 May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I think this is the only right answer, everyone else didn't take into account cases where there are circles and duplicate cities in the path. Though how do you find Euler path with just DFS? You would have to modify DFS and add circles which you didn't find in the DFS but that's Hierholzer's algorithm

- yaronbic October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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); 
		}
	}

- vic May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

can you explain

- rushikesh90 May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

@rushikesh90
TreeSet is a ordered and unique data structure. I just use the characteristic.

- vic May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Well, it doesn't solve the question.
It would be great if the question asked the natural ordering of the destinations but it asks for the itinerary route.
Your solution gives the result:
[CDG, LHR, MUC, SFO, SJC]
However it should give this one instead:
[CDG, MUC, LHR, SFO, SJC]

- 1uttMentek June 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- Vivek Katarya May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

What is your time complexity?

- rushikesh90 May 18, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- zortlord May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

// 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] << " ";
}

- Sergey May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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']]))

- loxxy May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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']]))

}

- loxxy May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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']]))

- loxxy May 19, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- Anonymous May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

- dar May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- d.pavel203 May 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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));
}
}
}}

- Good Maker May 23, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}
}

- T Jalim May 25, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- pc June 02, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- drincruz June 08, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

{{
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);
}}

- Alexey June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}}

- Alexey June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- alexey June 24, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
	}

- coolguy September 20, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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);
}

- boreal September 21, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- eigelc October 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

- Mihir Mehta May 18, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

No need of binary search tree.. we need a simple graph again we can assume here that except the root all other nodes will have either one or no children

- rushikesh90 May 18, 2015 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More