# Interview questions (graphs and cycles)

### david karapetyan Oct 12, 2017

Pretty much any interview problem is going to be something about data structures with a very thin veneer for “motivation”. The most recent one for me was a basic problem in graph theory under the guise of printing a dependency tree

```
Problem: Given a dependency graph, print the hierarchical view.
Example: If A depends on B and C, and B depends on C and D,
and C depends on E then the output should look like
-- A
-- B
-- C
-- E
-- D
-- C
-- E
```

Notice that the problem does not mention anything about ill-defined dependency graphs with cycles. A well-formed dependency graph is a DAG (directed acyclic graph) and so we can assume that is the contract for our function and go from there but generalizing it a little bit to detect cycles is not much more complicated than assuming we have a well-formed graph.

We will traverse the graph in depth first order and keep track of an ancestry chain. The ancestry chain is the set of nodes we have seen so far while traversing the graph. We track the ancestry chain because we want to know when we have a cycle. If we see a node that we have already traversed then we know we are stuck in a cycle.

Here's some python implementing the solution

```
def print_deps_of_node(node, graph, path=None, nesting=0, warning=False):
print ' ' * nesting, '--', node
# We detected a cycle so print a warning and bail
if warning:
print ' ' * nesting, ' ', '^ WARNING: cycle'
return
# Initialize the ancestry chain
if path is None:
path = []
# Node has children so we recurse after some bookkeeping
if graph.get(node) is not None:
path = path + [node]
children = graph[node]
for child_node in children:
# This means we have visited this node before so this is a cycle
if child_node in path:
return print_deps_of_node(child_node,
graph, path, nesting + 1, True)
# No cycle so continue the recursion
# NOTE: I initially had a return statement here
# which was incorrect and would stop processing early.
# Thx to George Simpson for pointing it out
print_deps_of_node(child_node,
graph, path, nesting + 1)
```

The above solution is recursive and converting it to an iterative solution is left as an exercise for the reader. To make it iterative you need to manually track the frontier of what is being traversed by keeping your own stack instead of relying on function calls.

Running the above function on the following graph

```
# 'A': ['B', 'C'] means 'A' depends on 'B' and 'C'
{'A': ['B', 'J'], 'C': ['E'], 'B': ['C', 'D'],
'E': ['H', 'M'], 'D': ['F', 'G', 'J'], 'F': ['H'],
'I': ['O', 'P', 'K'], 'H': ['L'], 'K': ['N', 'L'],
'J': ['I', 'Q'], 'M': ['N', 'H'], 'L': ['I'],
'O': ['P'], 'P': ['Q']}
```

Gives us the following output

```
-- A
-- B
-- C
-- E
-- H
-- L
-- I
-- O
-- P
-- Q
-- P
-- Q
-- K
-- N
-- L
^ WARNING: cycle
-- M
-- N
-- H
-- L
-- I
-- O
-- P
-- Q
-- P
-- Q
-- K
-- N
-- L
^ WARNING: cycle
-- D
-- F
-- H
-- L
-- I
-- O
-- P
-- Q
-- P
-- Q
-- K
-- N
-- L
^ WARNING: cycle
-- G
-- J
-- I
-- O
-- P
-- Q
-- P
-- Q
-- K
-- N
-- L
-- I
^ WARNING: cycle
-- Q
-- J
-- I
-- O
-- P
-- Q
-- P
-- Q
-- K
-- N
-- L
-- I
^ WARNING: cycle
-- Q
```

Cool. This is exactly the question I got during a frontend role interview with

`<a-big-company-that-I-signed-an-NDA-to-not-disclosure-the-interview-detail>`

last year, given a JSON object, build a multi level menu.I was too stupid to think that they were asking me to build a react-like framework (lol), but what they really want to ask is the algorithm :(