Google Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

1. Read the file and build graph from its contents
2. Use DFS to check for cycles
3. If cycle is detected throw an exception
4. Else, apply topological sort on the graph
5. Print the result

- srdjan August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Extra work.

Maintain list of "roots" even before building the graph. As you build it, remove from roots those nodes to wich someone had directed.

Iteration step.

Pick one from root and remove it. Update root list with its children that had not been directed.

So the reason I am saying your solution is extra work because in my way you know there is a problem, a cycle as soon as root list become empty and graph is not empty, there is no need for separate cycle check. BTW, such condition can happen after build and before first iteration or anytime later.

- CT August 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Better yet, along with graph keep sorted histogram of ALL nodes and how many times it has been directed. If the one on the top has 0 count, proceed with removing it. If not, cycle is detected. When removed, reduce count of all of its children.

- CT August 22, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

working code?

- enok August 23, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

TopSort in scala

case class Node(id:String) {
  var in:Seq[Edge] = Seq.empty[Edge]
  var out: Seq[Edge] = Seq.empty[Edge]
  
  def add(nodes:Node*):Unit = {
    out = nodes.map(Edge(this, _)).toSeq
    nodes.foreach(_.addIn(this))
  }
  
  def addIn(node:Node) = {
    in:+=Edge(node, this)
  }
}

case class Edge(from:Node, to:Node) 

object MyTopSort extends App {
    val (na, nb, nc, nd) = (Node("a"), Node("b"), Node("c"), Node("d"))
    val nodes = Seq(na, nb, nc, nd)
    na.add(nb)
    nb.add(nc, nd)
    nc.add(nd)
  
    def sort(nodes:Seq[Node]):Seq[Node] = {
	  var outNodes = nodes.filter(_.in.size==0)
	  var dependency = Seq[Node]()
	  
	  while (outNodes.length!=0) {
	    val n = outNodes.head
	    outNodes = outNodes.drop(1)
	    dependency:+=n
	    
	    for(e<-n.out) {
	      val t = e.to
	      n.out = n.out.filter(e !=) //erase the edge
	      t.in = t.in.filter(e !=) //erase the edge
	      
	      if (t.in.isEmpty) outNodes+:=t
	    }
	  }
	  dependency
    }
  
    val path = sort(nodes)
    val cycle = nodes.exists(!_.in.isEmpty)
    println("Has cycle?", cycle)
    println(path)
}

- sabz August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I don't like the check

nodes.exists(!_.in.isEmpty)

, this implies cycle, but it is not equivalence. In other words, I may have graph that has a branch with such node, but the second branch will be have a cycle

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

#Directed Graph #Topological Sort

- Googler August 18, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Add to this cycle detection.

- kr.neerav August 18, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can someone provide a working piece of code?

- enok August 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

You should use quick union algorithm to make an array of dependency then you have O(n) to find the correct order.

- Ash August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

DFS works well here.

void BuildAllProjects() {
  for (Project p : projects) {
    BuildProjectRec(p);
  }
}

void BuildProjectRec(Project project) {
  if (project.status == PROCESSED)
    return;
  if (project.status == IN_PROGRESS)
    throw exeption("There is cycle between projects");

  project.status = IN_PROGRESS;
  for (Dependence dep_project : project.dependencies) {
    BuilldProjectRec(dep_project);
  }
  project.status = PROCESSED;  
  printf("Build project: %s", project->project_name);
}

- zprogd August 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class DependenciesTree {
	private static final String input = "a->b\nb->c\nb->d\nc->d";
	private static final String inputLoop = "a->b\nb->c\nb->d\nc->d\nd->a";

	public static void main(String[] args) {
		System.out.println(getCompileOrder(input));
		System.out.println(getCompileOrder(inputLoop));
	}

	public static String getCompileOrder(String input) {
		Map<String, Node> nodes = new HashMap<String, Node>();
		List<Node> ret = new LinkedList<Node>();

		BufferedReader reader = new BufferedReader(new StringReader(input));
		try {
			while (true) {
				String line = reader.readLine();
				if (null == line)
					break;
				// System.out.println(line);
				String[] strs = line.split("->");
				if (strs.length != 2)
					throw new Exception("invalid rule:" + line);
				String firstStr = strs[0];
				String secondStr = strs[1];
				Node first = nodes.get(firstStr);
				Node second = nodes.get(secondStr);
				if (null == second) {
					second = new Node(secondStr);
					nodes.put(secondStr, second);
				}

				if (null == first) {
					first = new Node(firstStr);
					nodes.put(firstStr, first);
				}

				first.dep.add(second);
			}

			// for (Node n : nodes.values()) {
			// System.out.println(n);
			// }

			for (int i = 0; i < nodes.size(); i++) {
				boolean nochange = true;
				for (Node node : nodes.values()) {
					// check if all dependencies are processed
					if (!node.processed && node.isDepsAllProcessed()) {
						node.processed = true;
						ret.add(node);
						nochange = false;
					}
				}

				boolean allDone = true;
				for (Node node : nodes.values()) {
					if (!node.processed)
						allDone = false;
				}
				if (allDone) {
					break;
				}

				if (nochange) {
					throw new Exception("loop found");
				}
			}

		} catch (Exception e) {
			e.printStackTrace();
		}
		return ret.toString();
	}
}

- LeoChen4891 August 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

To solve this question, we can use a Topological Sort.
Actually, we need starting nodes that do not have any dependency. (That is, no incoming edge)

Let's call that those nodes are 'starting' nodes.
From 'starting' nodes, we can get each edge from them. And remove connections.

For example, if I have the following build dependencies:
a -> d
a- > b
b -> c

Only 'a' is a starting node. From 'a', I can remove from/to relationships from other nodes.
When other node also become 'starting' node that is not having incoming edges, I use this node again.

If I keep continuing this processes, I will get build file processing order.

public class TopologicalSort {
  public static String retrieveBuildsOrder(Task[] tasks) {
	checkArgument(tasks != null && tasks.length > 0);
	Map<String, Graph.Node> cache = intialize(tasks);

	List<Graph.Node> startingNodes = new ArrayList<>();
	cache.entrySet().stream().filter(
	    (entry) -> (entry.getValue().inEdges.isEmpty())).forEach((entry) -> {
	  startingNodes.add(entry.getValue());
	});

	List<Graph.Node> result = new ArrayList<>();
	while (!startingNodes.isEmpty()) {
	  Graph.Node removal = startingNodes.remove(0);
	  result.add(removal);
	    
	  int j = 0, outEdgeSize = removal.outEdges.size();
	  while (j < outEdgeSize) {
		Graph.Edge e = removal.outEdges.remove(0);
		Graph.Node target = e.to;
		// Remove <-> relationship from/to nodes.
		target.inEdges.remove(e);
		// If target node's inEdges is empty, this target node can be categorized as a new starting node.
		if (target.inEdges.isEmpty()) {
		  startingNodes.add(target);
		}
		j++;
	  }
	}
	
	for(Map.Entry<String, Graph.Node> entry : cache.entrySet()) {
	  if (!entry.getValue().inEdges.isEmpty()) {
		investigateCyclicNode(entry.getValue());
		throw new IllegalArgumentException("Cyclic connection detected");
	  }
	}
	
	StringBuilder stringResult = new StringBuilder();
	for (Graph.Node n : result) {
	  stringResult.append(n.toString()).append(",");
	}
	return stringResult.append("end").toString();
  }
  
  private static Map<String, Graph.Node> intialize(Task[] tasks) {
	Map<String, Graph.Node> cache = new HashMap<>();
	for (Task task : tasks) {
	  Graph.Node n1 = cache.get(task.from);
	  
	  if (n1 == null) {
		n1 = new Graph.Node(task.from);
		cache.put(task.from, n1);
	  }
	  
	  Graph.Node n2 = cache.get(task.to);
	  if (n2 == null) {
		n2 = new Graph.Node(task.to);
		cache.put(task.to, n2);
	  }
	  
	  n1.addEdge(n2);
	}
	return cache;
  }
  
  private static void investigateCyclicNode(Graph.Node node) {
	print("Name of node creating cyclic: " + node.toString());
	for (Graph.Edge e : node.inEdges) {
	  print(e);
	}
  }
  
  public static void main(String[] args) {
	Task task1 = new Task("7", "11");
	Task task2 = new Task("7", "8");
	Task task3 = new Task("5", "11");
	Task task4 = new Task("3", "8");
	Task task5 = new Task("3", "10");
	Task task6 = new Task("11", "2");
	Task task7 = new Task("11", "9");
	Task task8 = new Task("11", "10");
	Task task9 = new Task("8", "9");
	Task task10 = new Task("8", "10");
	Task[] tasks = new Task[]{task1, task2, task3, task4, task5, task6, task7, task8, task9, task10};
	print(retrieveBuildsOrder(tasks)+"\n");
	
	Task invalidBuild = new Task("2", "11");
	tasks = new Task[]{task1, task2, task3, task4, task5, task6, task7, task8, task9, task10, invalidBuild};
	try {
	  print(retrieveBuildsOrder(tasks));
	} catch(IllegalArgumentException expected) {
	  print("Cyclic detected, there should be an exception");
	}
  }
}

class Task {
  final String from;
  final String to;
  
  Task(String from, String to) {
	this.from = from;
	this.to = to;
  }
}

- soodongStudying August 24, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Create a graph and do reverse topological sort using queue.

#include <iostream>
#include <unordered_map>
#include <vector>
#include <queue>

using namespace std;

#define NUM_NODES 4

typedef unordered_map<string, vector<string>> Graph;

void nodesWithNoOutgoingEdges(Graph &outgoingEdges, queue<string> &Queue) {
  for (auto it = outgoingEdges.begin(), ie = outgoingEdges.end(); it != ie; ++it) {
    if ((it->second).size() == 0) {
      Queue.push(it->first);
    }
  }
}

void removeOutgoingEdges(Graph &outgoingEdges, Graph &incomingEdges, string node) {
  // remove this node
  outgoingEdges.erase(node);

  // remove node from outgoing nodes
  vector<string> nodes = incomingEdges[node];
  for (auto &it : nodes) {
    outgoingEdges[it].erase(remove(outgoingEdges[it].begin(),
                                           outgoingEdges[it].end(), node), outgoingEdges[it].end());
  }
}

void topologicalSort(Graph &outgoingEdges, Graph &incomingEdges) {
  queue<string> *Queue = new queue<string>();
  nodesWithNoOutgoingEdges(outgoingEdges, *Queue);

  vector<string> finalOrder;

  while (!Queue->empty()) {
    string tempNode = Queue->front();
    Queue->pop();
    finalOrder.push_back(tempNode);
    removeOutgoingEdges(outgoingEdges, incomingEdges, tempNode);
    if (Queue->empty())
      nodesWithNoOutgoingEdges(outgoingEdges, *Queue);
  }

  if (finalOrder.size() != NUM_NODES) {
    std::cerr << "Cycle in the dependency graph" << endl;
    abort();
  }

  for (auto it : finalOrder) {
    std::cout << it << std::endl;
  }
}

int main(void) {

  // maintain two maps for outgoing and incoming edges.
  Graph outgoingEdges;
  Graph incomingEdges;
  outgoingEdges.insert(make_pair("a", vector<string>()));
  outgoingEdges.insert(make_pair("b", vector<string>()));
  outgoingEdges.insert(make_pair("c", vector<string>()));
  outgoingEdges.insert(make_pair("d", vector<string>()));
  incomingEdges.insert(make_pair("a", vector<string>()));
  incomingEdges.insert(make_pair("b", vector<string>()));
  incomingEdges.insert(make_pair("c", vector<string>()));
  incomingEdges.insert(make_pair("d", vector<string>()));

  outgoingEdges["a"].push_back("b");  // a->b
  incomingEdges["b"].push_back("a");

  outgoingEdges["b"].push_back("c");  // b->c
  incomingEdges["c"].push_back("b");

  outgoingEdges["b"].push_back("d");  // b->d
  incomingEdges["d"].push_back("b");

  outgoingEdges["c"].push_back("d");  // c->d
  incomingEdges["d"].push_back("c");

  topologicalSort(outgoingEdges, incomingEdges);

  return EXIT_SUCCESS;
}

- gylnkt August 25, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Dependencies {

	public static void main(String[] args) {
		
		/* normal case */
		System.out.print("Normal case: ");
		System.out.println(buildOrder(
				new String[] { "a-b", "b-c", "b-d", "c-d"}));

		/* circular dependencies */
		System.out.println();
		System.out.println(buildOrder(
				new String[] { "a-b", "b-c", "c-a", "b-d", "c-d"}));

	}

	private static String buildOrder(String[] deps) {
		StringBuffer out = new StringBuffer("");

		int[] weights = new int[deps.length];
		int k = 0;
		int maxWeight = Integer.MIN_VALUE;
		for (String dep : deps) {
			weights[k++] = calcWeight(dep, deps, null);
			if (weights[k - 1] > maxWeight) {
				maxWeight = weights[k - 1];
			}
		}

		for (int w = 1; w <= maxWeight; w++) {
			for (int q = 0; q < deps.length; q++) {
				String[] parts = deps[q].split("-");
				if (weights[q] == w) {
					if (!out.toString().contains(parts[1].concat(","))) {
						out.append(parts[1]);
						if (w<maxWeight) {
							out.append(", ");
						}
					}
					if (!out.toString().contains(parts[0].concat(","))) {
						out.append(parts[0]);
						if (w<maxWeight) {
							out.append(", ");
						}
					}

				}
			}
		}

		return out.toString();
	}

	private static int calcWeight(String current, String[] deps, StringBuffer path) {
		int weight = 1;
		String[] pair = current.split("-");
		if (pair.length != 2) {
			throw new IllegalArgumentException(
					"Incorrect dependency: ".concat(current));
		}

		path = path == null ? new StringBuffer(current) : path;
		boolean circle = true;
		String lastEnd = "";
		for (String dep : deps) {
			String[] elements = dep.split("-");
			if (elements.length != 2) {
				throw new IllegalArgumentException(
						"Incorrect dependency: ".concat(dep));
			}

			if (!dep.equals(current) && !path.toString().contains(dep)) {
				if (elements[0].equals(pair[1]) || elements[0]
						.equals(pair[0])) {
					weight++;
					path.append("->").append(dep);
					circle = circle && lastEnd.equals(elements[0]);
					weight += calcWeight(dep, deps, path);
					lastEnd = elements[1];
				}
				
				if (path.charAt(0) == path.charAt(path.length() - 1) && circle) {
					throw new IllegalStateException(
							"Circular dependencies: ".concat(path.toString()));
				}
			}
		}

		return weight;
	}

}

- PS September 06, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

If a little more constraints are defined, I believe both Top Sort and DFS can be avoided with adj. matrix. Iterate one side of the adj matrix, if no nodes have been satisfied or dependency removed after an iteration, and nodes still in matrix, you must have a cycle. This probably isn't as efficient however.

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

struct Node{
  int data;
  Node *next;

};

void display(struct Node *head){
  Node *list = head;
  while (list){
    cout<<list->data<<" ";
    list = list->next;
  }
  cout<<endl;

}

struct Node *detectLoop(struct Node *head){
    struct Node  *n1 = head->next, *n2 = head;
    
    while(n2)
    {
        if (n1 == n2)
        {
            printf("Found Loop");
            break;
        }
        n1 = n1->next;
        n2  = n2->next->next;

    }
    if(n2 == NULL)
        return NULL;
    display(n2);
    return n2;
}

- Lalit September 28, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.io.InputStreamReader;
import java.io.BufferedReader;


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

class DependencyTree {
  public static void main(String args[]) throws Exception {
    
    List<CodeDependency> obj = new ArrayList<CodeDependency>();
    BufferedReader bufferedReader  = new BufferedReader(new InputStreamReader(System.in));  
    System.out.println("Enter number of dependencies\n");
    int num = Integer.parseInt(bufferedReader.readLine());
   

    CodeDependency codeObj;
    for(int i =0; i < num; i++) {
      System.out.println("Dependency "+i+": ");
	String[] arr = bufferedReader.readLine().split("->");
		codeObj = new CodeDependency(arr[0],arr[1]);
   		obj.add(codeObj); 
    }
    DependencyTree dependencyObj =  new DependencyTree();
    dependencyObj.printCodeDependency(dependencyObj.findDependency(obj)); 

  }
 
  public void printCodeDependency(List<SourceCode>  sourcecodes){
      Iterator<SourceCode> itr = sourcecodes.iterator();
      while(itr.hasNext()){
    	  System.out.print(itr.next().getParent());
    	  if(itr.hasNext()) System.out.print("->"); 
      }
  }
  
  public Map<String,SourceCode> mapParent;   
  
  public List<SourceCode> findDependency(List<CodeDependency> obj) {
     mapParent = new HashMap<String,SourceCode>();
     SourceCode code;
     Set<String> hsRootCode = new HashSet<String>();
     Set<String> hsChildCode = new HashSet<String>();


    for(CodeDependency dependency : obj) {
	// Add Child to parent with its child as null
	if(!mapParent.containsKey(dependency.getChild()) ){
		code = new SourceCode(dependency.getChild(), 0 , null);
		mapParent.put(dependency.getChild(), code);
		
	}
	
	// Add parent
	if(mapParent.containsKey(dependency.getParent()) ){
		code = mapParent.get(dependency.getParent());  
		code.setChild(dependency.getChild());
	}
	else {
		
		code = new SourceCode(dependency.getParent(), 0 ,dependency.getChild());
		
	}	
	
// Map root node and list of child node to help the iteration process
        hsChildCode.add(dependency.getChild());
	
        if(!hsChildCode.contains(dependency.getParent())) 
		hsRootCode.add(dependency.getParent());

        if(hsRootCode.contains(dependency.getChild())) 
		hsRootCode.remove(dependency.getChild());

	mapParent.put(dependency.getParent(),code);  
    }

    if(hsRootCode.size() > 0) {
	for(String codeName : hsRootCode)
	  findDepth(codeName , 1);
    }
    else 	  
    {
    	   System.out.println("\n ****************  Circular dependency found **************");
           System.exit(-1);
    }
	
    List<SourceCode> codeDependency = new ArrayList<SourceCode>();
    for( String codeItr: mapParent.keySet()) {
    	codeDependency.add(mapParent.get(codeItr));
    }
    
    Collections.sort(codeDependency);
    
     return codeDependency;
    
  }
 
  public Set<String> hsCode = new HashSet<String>();

  public void findDepth(String codeName, int pos) {
	if (!hsCode.contains(codeName)) {
		hsCode.add(codeName);
		SourceCode code =  mapParent.get(codeName);
		if(code.getDepth() < pos) {
			code.setDepth(pos);
			mapParent.put(codeName,code);
		// System.out.println("  "+codeName+ "  " + pos);
		    for (String itrCode : code.getChild())
		    {
			if (itrCode != null) findDepth(itrCode, pos+1);
		    }	
		}
	 
            hsCode.remove(codeName);
	}
        else {
	   System.out.println("\n ****************  Circular dependency found **************");
           System.exit(-1);
	}
   
  }


 public static class CodeDependency {
  String child;
  String parent;
  
  public CodeDependency(){ 
	   
  }
  public CodeDependency(String child, String parent) {
     this.child = child;
     this.parent = parent;
  }

  public String getChild() {
   return child;
  }
  public String getParent() {
   return parent;
  }
  
 }


 public class SourceCode implements Comparable<SourceCode> {
   String parent;
   int depth;
   List<String> child;

   public SourceCode(String parent, int depth, String child) {
	this.child = new ArrayList<String>();
	this.parent = parent;
	this.depth = depth; 
	this.child.add(child);
   } 
   
   public void setDepth(int depth) {
     this.depth = depth;
   }

   public int getDepth() {
     return depth;
   }

   public String getParent() {
	     return parent;
   }

   public List<String> getChild() {
      return child;
   }

   public void setChild(String child) {
 	this.child.add(child);
   }


   @Override
  public int compareTo(SourceCode obj) {
	return this.getDepth() - obj.getDepth();
  }
 }

}

- Arun November 13, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This code builds the graph first. During build, it will build projects with no dependency first, remove these projects from the graph, and repeat.

Code written in C++11 in google doc, so please excuse me if there is a typo.

std::vector<std::string> readAllLines(const std::string& filepath) {
    std::vector<std::string> lines;
    std::ifstream ifs(filepath);
    while (ifs) {
        lines.push_back(std::getline(ifs));
    }
    return lines;
}

Graph buildGraph(const std::vector<std::string>& lines) {
    Graph g;
    for (const auto& l : lines) {
        auto edge = split(l, ‘:’);
        g.addEdge(edge[0], edge[1]);
    }
    return g;
}

class Node {
    std::string name;
    std::vector<std::string> inNodes;
    std::vector<std::string> outNodes;

    void eraseNode(std::vector<std::string>& nodes, const std::string& n) const {
        nodes.erase(
            nodes.remove(std::begin(nodes), std::end(nodes), n), 
            std::end(nodes));
    }

public:
    Node(const std::string& name, std::vector<std::string> inNodes,
         std::vector<std::string> outNodes) 
         : name(std::move(name))
         , inNodes(std::move(inNodes))
         , outNodes(std::move(outNodes))
    {}

    void erase(const std::string& node) {
        eraseNode(inNodes, node);
        eraseNode(outNodes, node);
    }

    int inDegree() const { return static_cast<int>(inNodes.size()); }
};



class Graph {
    std::map<std::string, std::unique_ptr<Node>> nodes;

public:
    void addEdge(const std::string& from, const std::string& to) {
        auto& fnode = find(from);
        if (fnode) {
            fnode->addTo(to);
        } else {
            fnode = std::make_unique(Node(from, {}, {to}));
        }
        auto& tnode = find(to);
        if (tnode) {
            tnode->addFrom(from);
        } else {
            tnode = std::make_unique(Node(to, {from}, {});
        }
    }

    void addNode(std::unique_ptr<Node> n) {
        assert(!find(n));
        nodes[n.name()] = n;
    }

    std::unique_ptr<Node>& find(const std::string& name) {
        return nodes[name];
    }

    int nodeCount() const { return static_cast<int>(nodes.size()); }

    std::vector<std::string> selectNodes(
        const std::function<bool(const Node&)>& predicate) const {
        std::vector<std::string> r;
        for (const auto& pair : nodes) {
            if (predicate(pair.second)) {
                r.push_back(pair.first);
            }
        }
        return r;
    }

    void remove(const std::vector<std::string>& nodes) {
        for (const auto& n : nodes) {
            find(n).reset();
        }
        for (auto& pair : this->nodes) {
            for (const auto& n : nodes) {
                pair.second.erase(n);
            }
        }
    }
};

class CyclicDependencyException : public std::runtime_error { /* … */ }

void buildPorjects(const std::vector<string>& projects) { /* … */}

void build(const std::string& filepath) {
    auto g = buildGraph(readAllLines(filepath));
    while (g.nodeCount() > 0) {
        auto nodes = g.selectNodes([](const Node& n) { 
            return n.inDegree() == 0; 
        });
        if (nodes.size() == 0)
            throw CyclicDependencyException(g);
        buildProjects(nodes);
        g.remove(nodes);
    }
}

- Anonymous November 16, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def myAp(ch, lst):
    if ch in lst:
        lst = lst
    else:
        lst.append(ch)
    return lst

def recursion(result, all, dic):

    if len(all) == 0:
        return result



    for idx, i in enumerate(all):
        try:
            if len(dic[i]) == 0:
                del dic[i]
                result = (myAp(all.pop(idx), result))
        except:
            result = (myAp(all.pop(idx), result))


        for k in dic:
            if k not in dic[k]:
                for idx2, x in enumerate(dic[k]):
                    for item in result:
                        if item in dic[k]:
                            dic[k].pop(idx2)

                    if x not in dic:
                        try: result = (myAp(dic[k].pop(idx2) , result))
                        except:
                            pass


    return(recursion(result, all, dic))


def parse():
    file = """a->b\n
    b->c\n
    b->d\n
    c->d"""
    dic2 = {}
    all2 = []

    file = file.replace(' ', '')
    file = file.split('\n')
    for row in file:
        try:
            lst = row.split('->')
            if lst[0] != '' and not lst[0] in all2: all2.append(lst[0])
            if lst[1] != '' and not lst[1] in all2: all2.append(lst[1])
            try: dic2[lst[0]].append(lst[1])
            except: dic2[lst[0]] = [lst[1]]
        except: pass

    all2 = set(all2)
    all2 = list(all2)

    print recursion([], all2, dic2)


parse()

- Anonymous November 21, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Recursive way to do it in python, with some time might be able to do it with a Dictionary Comprehension. Thinking you write this very quickly in prolog.

- Cole Kennedy November 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

It will also throw a runtime error that can be handled if you have a circular dependency.

- Cole Kennedy November 21, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

using System;
using System.Collections.Generic;

namespace CareerCup
{
    public class BuildOrder
    {
        private const int Undiscovered = 1;
        private const int Discovered = 2;
        private const int Processing = 4;

        public void ResolveBuildOrder(string input)
        {
            var adjLists = Parse(input);
            var buildQueue = TopologicalSort(adjLists);

            foreach (var item in buildQueue)
            {
                Console.WriteLine(item);
            }
        }

        private Dictionary<char, LinkedList<char>> Parse(string input)
        {
            var result = new Dictionary<char, LinkedList<char>>();
            var tokens = input.Split(' ');

            foreach (var token in tokens)
            {
                char from = token[0], to = token[3];
                if (!result.ContainsKey(from))
                {
                    result[from] = new LinkedList<char>();
                }
                if (!result.ContainsKey(to))
                {
                    result[to] = new LinkedList<char>();
                }
                result[from].AddLast(to);
            }

            return result;
        }

        private Queue<char> TopologicalSort(Dictionary<char, LinkedList<char>> adjLists)
        {
            var states = new Dictionary<char, int>();
            foreach (var vertice in adjLists.Keys)
            {
                states[vertice] = Undiscovered;
            }
            var queue = new Queue<char>();

            foreach (var vertice in adjLists.Keys)
            {
                if ((states[vertice] & Discovered) != Discovered)
                {
                    DfsVisit(vertice, adjLists, states, queue);
                }
            }

            return queue;
        }

        private void DfsVisit(
            char root, 
            Dictionary<char, LinkedList<char>> adjLists, 
            Dictionary<char, int> states,
            Queue<char> postorderQueue)
        {
            states[root] |= Processing;
            states[root] |= Discovered;

            foreach (var child in adjLists[root])
            {
                if ((states[child] & Processing) == Processing)
                {
                    throw new Exception("Cycle found!");
                }

                if ((states[child] & Discovered) != Discovered)
                {
                    DfsVisit(child, adjLists, states, postorderQueue);
                }
            }

            states[root] ^= Processing;
            postorderQueue.Enqueue(root);
        }
    }
}

- stanislav.khalash January 23, 2015 | Flag Reply


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