Google Interview Question
Software Engineer / DevelopersCountry: United States
Interview Type: In-Person
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.
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.
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)
}
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);
}
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();
}
}
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;
}
}
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;
}
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;
}
}
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.
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;
}
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();
}
}
}
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);
}
}
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()
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.
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);
}
}
}
1. Read the file and build graph from its contents
- srdjan August 19, 20142. 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