Google Interview Question
Jr. Software EngineersCountry: United States
Interview Type: Phone Interview
Good one :) but I think (IMHO) you should put the :
stack.push(vertex); inside the if:
if (visitedVertices[*reverseListIterator] == false) {
runTopologicalSortUtility(*reverseListIterator, visitedVertices, stack);
stack.push(vertex);
}
Otherwise your keep pushing the 5 vertex (from the example)...
Java implementation of Tarjan's algorithm:
public static <T> List<Node<T>> sortTopological(Set<Node<T>> nodes) {
List<Node<T>> result = new ArrayList<>(); // Sorted list of Nodes
Set<Node<T>> visited = new HashSet<>(); // Used in lieu of a boolean flag on Node
Set<Node<T>> visitedTemp = new HashSet<>(); // Used in lieu of a boolean flag on Node
for (Node<T> node : nodes) {
if (!visited.contains(node)) visit(node, result, visited, visitedTemp);
}
return result;
}
private static <T> void visit(Node<T> node, List<Node<T>> sorted, Set<Node<T>> visited, Set<Node<T>> visitedTemp) {
if (visitedTemp.contains(node)) throw new RuntimeException("Graph is not acyclic");
visitedTemp.add(node);
for (int i = 0; i < node.adjacent.size(); i++) {
Node<T> adjacentNode = node.adjacent.get(i);
if (!visited.contains(adjacentNode)) {
visit(adjacentNode, sorted, visited, visitedTemp);
}
}
visited.add(node);
visitedTemp.remove(node);
sorted.add(0, node);
}
Just do bfs from vertex with zero in-degree.
Delete vertex of in-degree 0 and all its outgoing edges from the graph.
Continue doing so until no more in-degree 0 vertex.
If the graph still have vertexes, then it has cycle. Return what ever the reviewer want (could be null or the vertexes deleted)
If the graph do not have vertexes then the deleted vertexes is in topological order.
We could keep a stack for the deleted vertexes and return it as the answer.
#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];
void top(int u)
{
vis[u]=1;
//s.pb(u);
for(int el: g[u]){
if(!vis[el]){
top(el);
}
}
s.pb(u);
}
int main()
{
int m=6;
int u,v;
for(int i=0;i<m;i++){
cin>>u>>v;
g[u].push_back(v);
vis[v]=1;
//g[v].push_back(u);
}
int st;
for(int i=1;i<=5;i++){
if(!vis[i]){
st=i; break;
}
}
memset(vis,0,sizeof(vis));
top(st);
reverse(s.begin(),s.end());
for(int el: s){
cout<<el<<" ";
}
return 0;
}
#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];
void top(int u)
{
vis[u]=1;
//s.pb(u);
for(int el: g[u]){
if(!vis[el]){
top(el);
}
}
s.pb(u);
}
int main()
{
int m=6;
int u,v;
for(int i=0;i<m;i++){
cin>>u>>v;
g[u].push_back(v);
vis[v]=1;
//g[v].push_back(u);
}
int st;
for(int i=1;i<=5;i++){
if(!vis[i]){
st=i; break;
}
}
memset(vis,0,sizeof(vis));
top(st);
reverse(s.begin(),s.end());
for(int el: s){
cout<<el<<" ";
}
return 0;
}
#include <bits/stdc++.h>
#define pb(x) push_back(x)
using namespace std;
vector<int> g[20],s;
bool vis[20];
void top(int u)
{
vis[u]=1;
//s.pb(u);
for(int el: g[u]){
if(!vis[el]){
top(el);
}
}
s.pb(u);
}
int main()
{
int m=6;
int u,v;
for(int i=0;i<m;i++){
cin>>u>>v;
g[u].push_back(v);
vis[v]=1;
//g[v].push_back(u);
}
int st;
for(int i=1;i<=5;i++){
if(!vis[i]){
st=i; break;
}
}
memset(vis,0,sizeof(vis));
top(st);
reverse(s.begin(),s.end());
for(int el: s){
cout<<el<<" ";
}
return 0;
}
from copy import copy
class Queue:
def __init__(self):
self.items = []
def isEmpty(self):
if len(self.items) == 0 :
return True
else:
return False
def enqueue(self, v):
self.items.insert(0, v)
def dequeue(self):
return self.items.pop()
class Node:
def __init__(self, v):
self.v = v
self.adjNodes = []
def adjacentTo(self, vs):
self.adjNodes = copy(vs)
class Graph:
def __init__(self, nodes):
self.nodes = nodes
self.inDegree = self.getinDegree()
self.printinDegree()
def printinDegree(self) :
for n in self.nodes:
print('n:= ', n.v,' >> inDegree:= ' ,self.inDegree[n])
def getinDegree(self):
inDegree = dict()
for n in self.nodes:
if n not in inDegree:
inDegree[n] = 0
js = n.adjNodes
for j in js:
if j not in inDegree:
inDegree[j] = 1
else:
inDegree[j] += 1
return inDegree
def topologicalSort(self):
sortedList = []
q = Queue()
for n in self.nodes:
if self.inDegree[n] == 0:
q.enqueue(n)
for t in n.adjNodes:
self.inDegree[t] -= 1
if self.inDegree[t] == 0:
q.enqueue(t)
while(not q.isEmpty()):
p = q.dequeue()
sortedList.append(p)
for t in p.adjNodes:
self.inDegree[t] -=1
if self.inDegree[t] == 0:
q.enqueue(t)
for s in sortedList:
print(s.v)
a = Node(1)
b = Node(2)
c = Node(3)
d = Node(4)
e = Node(5)
f = Node(6)
a.adjacentTo([b,c])
b.adjacentTo([c,d,e])
c.adjacentTo([d,a])
f.adjacentTo([a])
g = Graph([a,b,c,e,d,f])
g.topologicalSort()
class Node {
public:
int key;
Node(int k) : key(k) {}
};
class Graph {
public:
std::stack<int> topSort()
{
std::stack<int> ret;
std::vector<int> st (nodes.size(), 0);
for (int i = 0; i < heads.size(); i++)
dfs(heads[i], ret, st);
return ret;
}
private:
void dfs(int root, std::stack<int>& ret, std::vector<int>& st)
{
st[root] = 1;
for (int j = 0; j < adjacency[root].size(); j++)
if (st[adjacency[root][j]] == 0)
dfs(adjacency[root][j], ret, st);
st[root] = 2;
ret.push(root);
}
std::vector<Node> nodes;
std::vector<int> heads;
std::vector<std::vector<int>> adjacency;
};
- Hsien Chang Peng November 30, 2015