Google Interview Question
Software DevelopersCountry: India
//BFS time complexity: O(V + E), space: O(V)
class Solution {
public static void main(String[] args) {
List<List<Integer>> adj = new ArrayList<List<Integer>>(9);
for (int i = 0; i < 9; i++) {
adj.add(new ArrayList<Integer>());
}
adj.get(4).add(5);
adj.get(5).add(6);
adj.get(5).add(7);
adj.get(7).add(6);
adj.get(7).add(8);
System.out.println(longestCycle(adj,4));
}
public static int longestCycle(List<List<Integer>> adj, int node) {
Deque<Integer> q = new LinkedList<Integer>();
boolean[] visited = new boolean[adj.size()];
int[] levels = new int[adj.size()];
levels[node] = 1;
q.addLast(node);
visited[node] = true;
while (!q.isEmpty()) {
int top = q.pollFirst();
for (Integer x: adj.get(top)) {
if (visited[x]) {
if (x == node) {
return levels[top];
}
} else {
levels[x] = levels[top] + 1;
q.addLast(x);
}
}
}
return -1;
}
}
public class DetectSmallestCycleInGraph {
private int shortestCycleSize = Integer.MAX_VALUE;
private Graph.Vertex[] shortestCycle;
Graph.Vertex[] findSmallestCycleDirectedGraph(Graph g) {
for(Graph.Vertex v :g.getVertices()) {//O(V)
Stack<Graph.Vertex> vertexStack = new Stack<>();
v.setVisited(false);//marking it unvisited so it can be traversed
boolean hasCycle = hasCycleDirectedGraph(v, vertexStack);
if(hasCycle) {
if(vertexStack.size() < shortestCycleSize){
shortestCycleSize = vertexStack.size();
shortestCycle = new Graph.Vertex[shortestCycleSize];
vertexStack.toArray(shortestCycle);
}
}
}
return shortestCycle;
}
boolean hasCycleDirectedGraph(Graph.Vertex source, Stack<Graph.Vertex> adjVertex) {
if(source.isVisited()) return false;
source.setVisited(true);
adjVertex.push(source);
for(Graph.Edge adj : source.getEdges()) {//O(A) , where A is adjacent edges to source
if(adj.getTo().isVisited() && adjVertex.contains(adj.getTo())) {//contains causes O(M) where M is the number of vertices on a path from the source node
return true;
} else if(!adj.getTo().isVisited() && hasCycleDirectedGraph(adj.getTo(), adjVertex)) {
return true;
}
}
adjVertex.pop();
return false;
}
public static void main(String[] args) {
int[][] edges = {
{0, 1},
{0, 2},
{2, 1},
{3, 0},
{1, 3},//shortest cycle
{1, 4},
{4, 5},
{5, 6},
{6, 7},
{7, 1}//cycle
};
Graph g = new Graph(edges);
DetectSmallestCycleInGraph da = new DetectSmallestCycleInGraph();
Graph.Vertex[] cycle = da.findSmallestCycleDirectedGraph(g);
System.out.println("\n Shortest cycle : ");
for (Graph.Vertex v : cycle) {
System.out.print(v.getId() + " -> ");
}
}
struct PathNode
{
shared_ptr<PathNode> prev;
int dist;
const GraphNode* node;
PathNode(const GraphNode* n, shared_ptr<PathNode>* p=NULL)
{
node = n;
if (p)
{
prev = *p;
dist = p->get()->dist + 1;
}
else
dist = 0;
}
bool has(const GraphNode* f)
{
PathNode* cur = this;
do {
if (cur->node == f)
return true;
cur = cur->prev.get();
} while (cur);
return false;
}
void getAllPath(list<const GraphNode*>& ret)
{
PathNode* cur = this;
do {
ret.push_front(cur->node);
cur = cur->prev.get();
} while (cur);
}
};
void findShortestCycle(const GraphNode& node, list<const GraphNode*>& ret)
{
queue<shared_ptr<PathNode>> to_visit;
to_visit.push(shared_ptr<PathNode>(new PathNode(&node)));
unordered_map<const GraphNode*, int> dist_map;
while (!to_visit.empty())
{
shared_ptr<PathNode> path = to_visit.front(); to_visit.pop();
cout << to_visit.size() << ":" << path->node->getValue() << " -> ";
for (const GraphNode* linked : path->node->links())
{
cout << linked->getValue();
if (path->has(linked)) // cycle
{
cout << endl;
path->getAllPath(ret);
return;
}
unordered_map<const GraphNode*, int>::iterator dist_it = dist_map.find(linked);
if (dist_it != dist_map.end() && dist_it->second < path->dist + 1)
{
cout << "-skip";
continue;
}
cout << " ";
shared_ptr<PathNode> new_path(new PathNode(linked, &path));
to_visit.push(new_path);
dist_map.insert({ linked, new_path->dist });
}
cout << endl;
}
}
void TestShortCycle()
{
/*
b --+ d
+ | \
/ | \
/ + +
a ------+ c +----- f
\ +
\ /
+ /
e
cycle1 : a -> b -> d -> c -> e -> f -> c
cycle2 : a -> c -> e -> f -> c
the lengths of two path are same until 'f' node : a -> b -> d -> f, a -> c -> e -> f
so, we can't use dijkstra's algorithm to calcuate shortest cycle.
we can't use visited hash table neither.
If you use it, second path(a -> c -> e -> f) will vanish.
But, I really want the faster way of checking cycle
*/
GraphNode a("a"), b("b"), c("c"), d("d"), e("e"), f("f");
a.addFriend(&b);
a.addFriend(&c);
b.addFriend(&d);
c.addFriend(&e);
d.addFriend(&f);
d.addFriend(&c);
e.addFriend(&f);
f.addFriend(&c);
list<const GraphNode*> ret;
findShortestCycle(a, ret);
cout << "path : ";
for(const GraphNode* node : ret)
cout << node->getValue() << " ";
cout << endl;
}
C++ solution with BFS, extended to track back nodes and the parent (to reconstruct the path):
class Graph
{
private:
int V;
vector<int>* adj;
public:
Graph(int V) :
V(V),
parents(V, -1)
{
adj = new vector<int>[V];
}
~Graph()
{
delete[] adj;
}
void addEdge(int src, int dest)
{
adj[src].push_back(dest);
}
bool findShortestCycle(int root)
{
vector<bool> visited(V, false);
vector<bool> backNode(V, false);
queue<int> q;
q.push(root);
visited[root] = true;
while(!q.empty())
{
int t = q.front();
q.pop();
for (int &a: adj[t])
{
if (backNode[a])
{
if (a == root)
{
parents[a] = t;
return true;
}
continue;
}
if (!visited[a])
{
visited[a] = true;
parents[a] = t;
q.push(a);
}
}
backNode[t] = true;
}
return false;
}
vector<int> parents;
};
int main() {
Graph g(6);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(2, 1);
g.addEdge(3, 2);
g.addEdge(3, 4);
g.addEdge(4, 3);
g.addEdge(4, 5);
g.addEdge(5, 2);
cout << "Cycle found: " << g.findShortestCycle(3) << endl;
string path = "3 <- ";
int v = 3;
while (g.parents[v] != 3)
{
path += std::to_string(g.parents[v]) + " <- ";
v = g.parents[v];
}
cout << path << "3 <- " << endl;
return 0;
}
Small modification to BFS to measure distance between two graph nodes. The issue is they should be the same node so you are confident you find the shortest cycle.
- baites January 23, 2019