So I’ve been applying for internship jobs and in order to prepare for technical interviews, I’ve scouted a bunch of websites (including GlassDoor), read a bunch of interview tips and gathered a list of questions that I think are challenging and worth solving. I enjoy some of these problems so this will be an ongoing blog series. I’m going to use one blog post per question. So let’s get started.

### Given a directed and connected graph, find a cycle (or loop) in it, if one exists

So our input is a simple, directed and connected graph and our output is a boolean (true or false). For simplicity, I’ll stick to finding just one cycle in the graph. The problem of finding all cycles in a graph is more complicated and likely deserves a blog post of its own. With these questions, I often find it easy to come up with a simple solution first, even if it’s not the most efficient one. Once we have a solution, we can iterate on it and make it better by considering time and space efficiency.

### Adjacency Matrix

There are two types of cycles within a graph. A strong cycle is one where there is a path from node A to B and from B to A whereas a weakly connected cycle would look like A->B->C->A. Finding strongly connected nodes is relatively easy because you can look for symmetry in an adjacency matrix. However, weakly connected cycles are tricky and building an adjacency matrix requires O(n^{2}) time (where n is the number of nodes). So let’s try another approach.

### Traversal

If we start at some arbitrary node A, and traverse through the graph, we can “flag” each node as “visited.” During our traversal, if we arrive at a previously visited node, we’ve detected a cycle and can return true. Otherwise, we’ve traversed through the whole graph and can return false. This seems to have a time complexity of O(n). Time to implement it.

```
public class Node {
Node next = null;
//...other fields
boolean visited = false;
public Node() {
//...initialize fields if needed
}
}
public class Graph {
Node start = new Node();
public Graph() {
//...initialize fields if needed
}
public boolean findCycle(Graph g) {
while(g.start.next != null) { // continue if this isn't the last node
if(g.start.visited) { // return if node has been visited
return true;
}
g.start.visited = true; // otherwise, flag as visited
g.start = g.start.next; // move to the next node
}
return false; // otherwise, return because no cycles found
}
}
```