## Google Interview Question for Software Developers

Country: India

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

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.

``````from collections import deque

thenode = u
dist[u] = 0
queue = deque()
queue.appendleft(u)
while len(queue) > 0:
u = queue.pop()
if dist[v] == -1 or dist[v] == 0:
dist[v] = dist[u] + 1
prev[v] = u
if v == thenode:
return dist[v], prev
queue.appendleft(v)
return -1, []

def print_cycle(path, u):
v = path[u]
result = str(u)
while v != u:
result += ' <- {}'.format(v)
v = path[v]
result += ' <- {}'.format(v)
print(result)

if dist != -1:
print('cycle size:', dist)
print_cycle(path, u)
else:
print('no cycle')

[1],
[2,3],
[4,5,6],
[0],
[],
[],
[0]
]

find_shortest_cycle(adj, 0) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 1) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 3) # return 0 <- 3 <- 1 <- 0
find_shortest_cycle(adj, 2) # return 2 <- 1 <- 0 <- 6 <- 2
find_shortest_cycle(adj, 6) # return 6 <- 2 <- 1 <- 0 <- 6
find_shortest_cycle(adj, 4) # return "no cycle"``````

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

``````//BFS time complexity: O(V + E), space: O(V)

class Solution {
public static void main(String[] args) {

for (int i = 0; i < 9; i++) {
}

}

public static int longestCycle(List<List<Integer>> adj, int node) {

levels[node] = 1;

visited[node] = true;

while (!q.isEmpty()) {
int top = q.pollFirst();

if (visited[x]) {
if (x == node) {
return levels[top];
}
} else {

levels[x] = levels[top] + 1;
}
}

}

return -1;
}

}``````

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

``````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);
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;
return true;
}
}
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() + " -> ");
}
}``````

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

``````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() << " -> ";
{
{
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 << " ";

to_visit.push(new_path);
}
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");

list<const GraphNode*> ret;
findShortestCycle(a, ret);

cout << "path : ";
for(const GraphNode* node : ret)
cout << node->getValue() << " ";
cout << endl;
}``````

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

C++ solution with BFS, extended to track back nodes and the parent (to reconstruct the path):

``````class Graph
{
private:
int V;

public:
Graph(int V) :
V(V),
parents(V, -1)
{
}

~Graph()
{
}

{
}

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();

{
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);

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;
}``````

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.

### 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.