Cycles in Directed Graphs (In Unexpected Places)

We are taking a break from data science, probability and statistics; and revisiting programming exercises. The problem we are going to tackle in this post comes from graph theory and efficient graph traversal. Graph theory is favorite of many interviewers, because formulating a problem in graph theory terms involves a lot of insight, and really tests a candidate’s skills. Most algorithms fit a few tens of lines of code, and whiteboard coding is a quick and easy way of testing those skills.

Problem

A rule looks like this:

A N B 
B NE C
C N A
A NW B 
A N B

Solution

Distinct points in space, and relations between them (North-South or NorthEast-SouthEast) points to an application of Graph theory. But what graph? What should be the vertices or edges of the graph? And how can we convert the given rules into this graph?

  • The rules are invalid if and only if there is a cycle in the transitive relations. i.e. if there is a rule A N B, and we also conclude that B N A through an independent transitive reasoning, then there is a cycle in the arrow (->) relation (as defined above), and hence the rules are invalid.
  • There are two independent dimensions for cycle-finding: north-south (vertical), and east-west (horizontal). Cycles can be found in either dimension. Any cycle found, in any of these dimenstions, makes the rules invalid.
  • All the points in the original problem (e.g. “A”, “B” etc) form the vertices of the graph.
  • If A is north of B (A N B), then there is an edge from B to A (B -> A) in the north_south graph. The direction of the edge is reversed when A is south of B.
  • If A is west of B (A W B), then there is an edge from B to A (B -> A) in the east_west graph. The direction of the edge is reversed when A is east of B.
  • We can combine the rules for east/west/north/south directions to construct edges for the remaining four directions. e.g. when A is north-west of B (A NW B), then there is an edge from B to A (B -> A) in the north_south graph AND there is an edge from B to A (B -> A) in the east_west graph.
  • We can find cycles in either east_west or north_south using Depth-First Search (DFS). If either graph contains a cycle, the rules are invalid.
The Graph class
A simple insert method to construct the graph
Checking whether the rules are valid
  • Populates the graphs according to the direction given in a rule. e.g. for the A NE B, it adds an edge (B, A) in north_south, and an edge (A, B) in east_west. Remember, there are 8 such if-else conditions, one per direction. You can simplify these conditions further if you want. For a white-board interview, you can also write a couple of them down, and omit the rest in the interest of time (Most interviewers won't mind 🙂 ).
  • An in_process set to indicate that the current node has started exploration, but not all reachable nodes from it have been explored.
Recursive DFS implementation to find cycles in the graph
contains_cycle method using DFS

One last thing … Tests

Never forget to write good tests — makes your interview stand out! ( If you have read some of our earlier posts, you might be familiar with our testing approach with GUnit tests).

Solutions to programming interview questions at some of the top companies in the world: cppcodingzen.com

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store