CareerCup

I wanted to stick rigidly to the API provided.

I have done a rather brute force algorithm but is still O(N) (maybe O(N^2) worst case)

I use a shifted counter to make sure we have finished shifting our nodes into place
I take the first start and end to be my start and end nodes then I shift

List<String> findPath(List<Step> steps) {
        Node startNode = new Node(steps.get(0).start); // C
        Node endNode = new Node(steps.get(0).end); // D
        int shifted = 0;
        int index = 1;
        while(shifted < steps.size() - 1) { // will need to do size - 1 shifts
            Step step = steps.get(index);
            if(step.end.equals(startNode.value)) {
                // shift the start
                Node n = new Node(step.start);
                n.next = startNode;
                startNode = n; // shifted so B - C nodes
                shifted++;
            }

            if(step.start.equals(endNode.value)) {
                // shift the end
                Node e = new Node(step.end);
                endNode.next = e;
                e = endNode;
                shifted++;
            }

            index = index + 1;
            if(index == steps.size())
                index = 1;
        }

        List<String> results = new ArrayList<String>();
        while(startNode != null) {
            results.add(startNode.value);
            startNode = startNode.next;
        }

        while(endNode != null) {
            results.add(endNode.value);
            endNode = endNode.next;
        }

        return results;
    }

PFB code finds the path, avoid possible loops also.

/**
 * 
 */
package cc.google.pathfinder;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Akhil
 * 
 */
public class PathFinder {

	static List<String> visitedCity;
	static boolean pathFound = false;

	/**
	 * @param args
	 */
	public static void main(String[] args) {

		List<Step> steps = new ArrayList<Step>();
		List<String> pathToBeTaken = new ArrayList<String>();
		visitedCity = new ArrayList<String>();
		steps.add(new Step("A", "B"));
		steps.add(new Step("B", "B"));
		steps.add(new Step("B", "A"));
		steps.add(new Step("E", "P"));
		steps.add(new Step("C", "X"));
		steps.add(new Step("B", "C"));

		pathToBeTaken = findPath(steps, "A", "X");
		System.out.println("Path : " + pathToBeTaken);

	}

	static List<String> findPath(List<Step> steps, String start,
			String destination) {

		List<String> pathTobeTaken = new ArrayList<String>();
		List<String> temp = new ArrayList<String>();
		visitedCity.add(start);
		if (!pathFound) {
			List<Step> avilableRoutes = availRoutesTo(start, steps);
			if (!avilableRoutes.isEmpty()) {
				for (Step step : avilableRoutes) {

					if (step.getFinish().equals(destination)) {
						pathFound = true;
						pathTobeTaken.add(start);
						pathTobeTaken.add(destination);
						return pathTobeTaken;
					} else {

						if (!step.getStart().equals(step.getFinish())
								&& !visitedCity.contains(step.getFinish())) {
							temp = findPath(steps, step.getFinish(),
									destination);
							if (pathFound && temp != null) {
								pathTobeTaken.add(start);
								pathTobeTaken.addAll(temp);
								return pathTobeTaken;

							} else {
								visitedCity.remove(step.getFinish());
							}
						}
					}
				}
			} else {

				return null;
			}
		}
		return null;
	}

	static List<Step> availRoutesTo(String city, List<Step> routes) {

		List<Step> avilableRoutes = new ArrayList<Step>();

		for (Step step : routes) {

			if (step.getStart().equals(city)) {
				avilableRoutes.add(step);
			}
		}

		return avilableRoutes;

	}

}

Result:

Path : [A, B, C, X]

List<String> findPath(List<Step> steps) {

	HashMap<String ,String> step_map = new HashMap<String, String>() ;	
	foreach(Step s : steps) {
		
		map.put(s.start, s.finish); //store everything in HashMap O(N)
	
	}
	
	String start;	
	foreach(Step s : steps) {
	
		if(!map.containsValue(s.start)){
			
			start = s.start;     //get start position  O(N)
		}
	}
	
	List<Step> steps_new = new List<Step>();	
	String finish = map.get(start);
	Step  temp_step;	
	while(finish){  // generate new list O(N)
		
		temp_step = new Step(start,finish);
		steps_new.add(temp_step);		
		start = finish;
		finish = map.get(start);
	
	}	
	
	return steps_new;
	
}

I think this should be solved using BFS, it will take care of the cycles if there are any. Simply build an adjacency list out of the given individual steps list may look something like this
for example, notice there can be multiple paths from one city to another and there can be cycles too, this list can be build in O(N). all you need to do is iterate over the given steps and keep putting them in the appropriate list.

A -> [B,D]
C -> [F, D]
F - > [G]
B -> [C,D,A]
D -> [C,A]
Q => [F]

After this all you have to do is BFS and record which node was reached from which node( to be used in the end to reconstruct the actual path found )

Here is how the code would roughly look like in c++. Note that this can be easily modified to use the said API of Node.

vector<string> findPath(vector<Step> steps, char start, char end){
	map<string, vector<string>> m; //stores the graph
	map<string, string> path; //stores the path
	for(int i=0;i<steps.size();i++){ //build the adjacency list
		m[steps[i].start].push_back(steps[i].finish);
	}
	//Simple BFS
	queue<string> Q;
	Q.push_back(start);
	path[start] = "#"; //Assuming # wont be an actual city;
	while(!Q.empty()){
	string top = Q.front();
	Q.pop();
	if(top == end){ break;}
	for(int i=0;i<m[start].size();i++){
		if(path.find(m[start][i]) == path.end()){ //do not visit a Node Twice
			path[m[start][i]] = top;
			Q.push(m[start][i]);
}
}
}
//recover the path
string reached = end;
while(reached != ‘#’){
	pathV.push_front(reached);
	reached = path[reached];
}
return pathV;

}

I don't entirely understand the API required.
What is the relation between List and Node?
Basically, what is List?

My suggested algorithm is this:

First, initialize a result - sortedPath, and build 2 maps (String to String) - startsToFinishes and finishesToStarts (O(N))

Then, find the one key on startsToFinishes, that is not a key in finishesToStarts - this is the city from which the path begins. (O(N))

Add this key to the sortedPath

Then, iteratively, city by city, build the path by going over the startsToFinishes keys, adding the current key to the sortedPath and making the value the new currentKey (currentKey = startsToFinishes.get(currentKey); ).
The iteration will break when the currentKey no longer exists in the startsToFinishes. (O(N))

return the sorted path

package com.cnu.ds.graphs;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class Traveler {
	public static List<String> printPath(Step[] steps, String start,
			String finish) {
		Map<String, String> map = new HashMap<String, String>();
		for (Step step : steps) {
			map.put(step.start, step.finish);
		}
		List<String> nodes = new LinkedList<>();
		nodes.add(start);
		while (!map.isEmpty()) {
			start = map.remove(start);
			nodes.add(start);
		}
		return nodes;
	}

	public static void main(String[] args) {
		Step[] steps = { new Step("C", "D"), new Step("B", "C"),
				new Step("A", "B") };
		List<String> path = printPath(steps, "A", "D");
		for (String string : path) {
			System.out.print(string + " ");
		}
	}
}

class Step {
	String start;
	String finish;

	public Step(String start, String finish) {
		super();
		this.start = start;
		this.finish = finish;
	}

}

Looking at the Node class, since it holds a single reference. Observing this, we might 
Assume each node is distinct. ie, if we have a node B , then there are only one node B
which implies, there is no cycle in the graph


public List<String> findPath(List<Step> steps) {
		/* Maintain the complete map of nodes*/
		List<String> computePath = new ArrayList<>();
		Map<String,Node> nodevaluemap = new HashMap<String, Node>();
		
		Step s;
		Node n1 = null;
		Node n2 = null;
		for (int i=0;i<steps.size() ;i++ )
		{
			s = steps.get(i);
			if (!nodevaluemap.containsKey(s.getStart()))
			{
				n1 = new Node();
				n1.value = s.getStart();
				nodevaluemap.put(n1.getValue(), n1);
			}
			else
			{
				n1 = nodevaluemap.get(s.getStart());
			}
			if (!nodevaluemap.containsKey(s.getFinish()))
			{
				n2 = new Node();
				n2.value = s.getFinish();
				nodevaluemap.put(n2.getValue(), n2);
			}
			else
			{
				n2 = nodevaluemap.get(s.getFinish());
			}
			if(n1.next == null)
			{
				n1.setNext(n2);
			}
		}
		
		/* From a given input ie start and finish*/
		String start = "A";
		String finish = "D";
		Node n = nodevaluemap.get("A");
		computePath.add(start);
		
		while(n.getNext().getValue() != finish)
		{
			
				computePath.add(n.getNext().getValue());
			
			n = n.getNext();
		}
		computePath.add(finish);

		return computePath;
	}
	
	
	
	public static void main(String[] args) {
		TestPath t = new TestPath();
		t.testFindPath();
	}
	public void testFindPath()
	{
		Step s1 = new Step("C", "D");
		Step s2 = new Step("A", "B");
		Step s3 = new Step("B", "C");
		List<Step> steps = new ArrayList<>();
		steps.add(s1);
		steps.add(s2);
		steps.add(s3);
		List<String> result = findPath(steps);
		System.out.println(result);
	}

TopSort?

package test;
import java.util.*;
public class Path {

	/**
	 * @author: Rohitraman2006
	 */
	public static void main(String[] args) {		

		List<Step> inputPath = new ArrayList<Step>();
		inputPath.add(new Step("C", "D"));
		inputPath.add(new Step("A", "B"));
		inputPath.add(new Step("B", "C"));
		inputPath.add(new Step("A", "B"));
		inputPath.add(new Step("B", "B"));
		
		List<String> returnPath = findPath(inputPath);

		for(String singlePath : returnPath)
		{
			System.out.println(singlePath);
		}		
	}

	public static List<String> findPath(List<Step> Steps){

		if(Steps.size()==0)
			return null;
				
		List<Node> listNodes = new ArrayList<Node>();
		
		//Maintain a list of all possible nodes which are not being pointed to.
		List<Node> listStartNodes = new ArrayList<Node>();
		
		for(int i=0;i<Steps.size();i++)
		{
			Node Start = new Node();
			Node Finish = new Node();
			
			Start.value = Steps.get(i).Start;
			Finish.value = Steps.get(i).Finish;
						
			if(listNodes.contains(Start) && listNodes.contains(Finish)) { 
				//Following check can be done in a single line, but broken down for clarity
				Node n1 = listNodes.get(listNodes.indexOf(Start));
				Node n2 = listNodes.get(listNodes.indexOf(Finish));
				if(n1.next == null)
				{
					n1.next = n2;
					//If listStartNodes contains n2, remove it, as it is being pointed to by n1.
					if(listStartNodes.contains(n2))
						listStartNodes.remove(n2);
				}
				else if(n1.next != null && n1.next.equals(n2)) // duplicate
						continue;
				else if (n1.next != null && !n1.next.equals(n2))
				{
					//means n1 and n2 exist in list, but n1 points to some other node and n2. 
					///this cannot happen. ignore condition, else alert.
				}
			}
			else if(Start.equals(Finish))
			{//Cycle
				continue;
			}
			else if(listNodes.contains(Start) && !listNodes.contains(Finish))
			{
				//Start node is in list but finish is not
				Start = listNodes.get(listNodes.indexOf(Start));
				Start.next = Finish;
				listNodes.add(Finish);
			}				
			else if(!listNodes.contains(Start) && listNodes.contains(Finish))
			{
				//Start node is not in list, but finish is.
				Finish = listNodes.get(listNodes.indexOf(Finish));
				Start.next = Finish;
				listNodes.add(Start);
				//add Start node in listStartNode
				listStartNodes.add(Start);
			}
			else
			{
				Start.next = Finish;
				listNodes.add(Start);
				listNodes.add(Finish);
				
				listStartNodes.add(Start);
			}					
		}
		
		List<String> listReturnString = new ArrayList<String>();
		if(listNodes.size()>0)
		{
			String entry = "";
			///We will always have 1 node in the listStartNode per the problem statement.
			Node startNode = listStartNodes.get(0);
			//Number of paths in a minimal spanning tree will be 1 less that the total number of nodes 
			for(int i=0;i<listNodes.size()-1;i++)
			{
				if(startNode.next == null)
					break;
				
				entry = startNode.value+"->"+startNode.next.value;
				listReturnString.add(entry);
				if(startNode.next!=null)
					startNode = startNode.next;
			}
		}
		
		
		return listReturnString;
	}
}

class Step{
	String Start;
	String Finish; 
	Step(String start, String finish)
	{
		Start = start;
		Finish = finish;
	}
}

class Node{
	String value;
	Node next;
	
	public boolean equals(Object o)
	{
		if((o instanceof Node) && (((Node)o).value == this.value))
			return true;
		else return false;
		
	}
}

The program runs correctly - tried all combinations of cycles, duplicates, etc.

Output to set input in program is:
A->B
B->C
C->D

What would be the complexity of this program? O(N logN) or O(n^2)?

I apologize ahead of time, but I am not quite using the API, either. I am not sure what the Node class adds and I have had interviews where extra information was given just to throw a candidate off course. I am not claiming that is the case here. I would need to do more reflection to see if a Node class would add benefit, but in real-world scenarios I would not use a class or call, either, if I the solution is just as good without it. Another thing I do not like about the API provided is that the "findPath" method provides no way to specify the destination! Do I really want to program a solution that always goes to 'D' if the more generic version is just as easy to implement? I might as well program the generic version and then simply provide an overload that always goes to 'D'. Again, maybe I have just overlooked something in the question.

For the benefit of other readers and my own reflection, I did want to share my solution just with edges:

private static List<Edge> FindPath(char from, char to, IEnumerable<Edge> edges, IEnumerable<char> seen)
{
    if (seen.Contains(from)) return null;
    if (from == to) return new List<Edge>();

    foreach (var edge in edges)
    {
        if (edge.From == from)
        {
            var pathEdges = new HashSet<Edge>(edges.Except(new[] {edge}));
            var pathSeen = new HashSet<char>(seen).Union(new[] {from});
            var pathTry = FindPath(edge.To, to, pathEdges, pathSeen);
            if (pathTry != null)
            {
                pathTry.Insert(0, edge);
                return pathTry;
            }
        }
    }
    return null;
}

It avoids loops and keeps all edges under consideration on the call stack, as opposed to making the signature more complicated and passing an extra container to contain all candidate edges for each path tried. When a path to the destination is found, the stack simply unwinds and adds edges into the resultant path in reverse order, starting from the edge leading to the destination.

Here is a sample I have tried:

HashSet<Edge> edges = new HashSet<Edge>()
{
    new Edge('A', 'B'),
    new Edge('B', 'C'),
    new Edge('C', 'D'),
    new Edge('D', 'A'),
    new Edge('D', 'E'),
    new Edge('E', 'F'),
    new Edge('F', 'G'),
    new Edge('A', 'Z'),
    new Edge('Z', 'A'),
    new Edge('G', 'A'),
};
HashSet<char> seen = new HashSet<char>();
List<Edge> path = FindPath('A', 'G', edges, seen);

It contains extraneous dead end paths and loops. Here is the result I arrive at for the above:

65 'A' -> 66 'B'
66 'B' -> 67 'C'
67 'C' -> 68 'D'
68 'D' -> 69 'E'
69 'E' -> 70 'F'
70 'F' -> 71 'G'

For added convenience, I will even share my Edge class :D Do not use it in commercial products, because I am planning to apply for 100 patents on it (kidding):

[DebuggerDisplay("{From} -> {To}")]
class Edge
{
    public char From, To;
    public Edge(char from, char to)
    {
        this.From = from;
        this.To = to;
    }
}

I like this much better, because it is a lot closer to the terminology of other graph based algorithms than "Step" is. IMHO it is good to name your types according to what their terminology is in literature, because other people that read your code will instantly recognize their semantics.

The usage of Node class might just be a test of understanding.
If you really have to use it, you can make some fancy place for it.
The below solution backtracks from destination to source, and throws an error of it cannot trace back.

Time complexity = O(n) where n is number of steps

class Step {
public:
string start;
string finish;
Step(string value1, string value2)
{
	start = value1;
	finish = value2;
}
};

vector<string> findPath(vector<Step> steps, string startPoint, string endPoint) 
{
	vector<string> path;
	unordered_map<string,string>  stepMap;
	for(int i = 0; i < steps.size(); ++i)
	{
		stepMap[steps[i].finish] = steps[i].start;
	}

	unordered_map<string,string>::iterator p = stepMap.find(endPoint);

	if(p == stepMap.end())
	{
		cout<<"No such destination in input!"<<endl;
		return vector<string>() ;
	}
	else
	{
		while (p->second != startPoint)
		{
			path.push_back(p->second +"->"+p->first);
			p = stepMap.find(p->second);
			if(p == stepMap.end())
			{
				cout<<"No valid path exists!"<<endl;
				return vector<string>();
			}
		}
		path.push_back(p->second +"->"+p->first);			
	}

	for (int i = (path.size() -1); i >= 0 ; --i)
	{
		cout<<path[i]<<endl;
	}

	return path;	
}

int main(int argc, char **argv)
{
	vector<Step> steps;
	steps.push_back(Step("C","D"));
	steps.push_back(Step("A","B"));
	steps.push_back(Step("B","C"));
	findPath(steps,"A","D");

public static List<String> findPath(List<Step> steps) {
List<String> ls = new ArrayList<String>();

// put all steps into a hashMap
Map<String, String> hm = new HashMap<String, String>();
for (Step s: steps) {
hm.put(s.start, s.finish);
}

//build the path from "A" to "D"
String stop = "A";
while (!stop.equals("D")){
ls.add(stop);
stop = hm.get(stop);
}
ls.add(stop);

return ls;
}

I am not pretty sure, but this could be solved through Map and reduce method, I believe.