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.
A rule looks like this:
A NE B
This means this means point
A is located northeast of point
A SW C
means that point
A is southwest of
Given a list of rules, check if the sum of the rules validate. For example:
A N B
B NE C
C N A
does not validate, since
A cannot be both north and south of
A NW B
A N B
is considered valid.
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 key insights of the problem come from these observations:
- The north-south or east-west relations between the points are transitive. If A is north of B, and B is north of C, then A is north of C. We can write it as
C -> B -> A. Here, the
->arrow indicates "north of".
- 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 Athrough 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.
These observations lead to the following graph algorithm
- We must maintain two graphs:
- 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_southgraph. 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_westgraph. 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_southgraph AND there is an edge from B to A (
B -> A) in the
- We can find cycles in either
north_southusing Depth-First Search (DFS). If either graph contains a cycle, the rules are invalid.
Let’s first declare and define a
Graph class. Let's add a construction method (
insert), and a const
contains_cycle method to return
true when the graph contains a cycle.
The bulk of implementation is concerned with implementing the
contains_cycle public methods of the
Graph class. Insert is the simplest of all (looking up and inserting in the
neighbors map). Let's add a quick implementation for it
Before implementing the
contains_cycle method, let's see how the entire graph class is going to be used from our main algorithm. Using a class usually gives us a better understanding of how the class is implemented. Feel free to change tracks during your interviews and make things as clear as possible.
Let’s implement the
is_valid method that takes a set of rules, and returns true if the rules are valid.
This method does three simple things:
- Declares two different maps
- Populates the graphs according to the direction given in a rule. e.g. for the
A NE B, it adds an edge
north_south, and an edge
east_west. Remember, there are 8 such
if-elseconditions, 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 🙂 ).
We are now ready to implement the
contains_cycle method. Depth-First Search (DFS) is the most appropriate algorithm for finding cycles in a directed graph. Recall that DFS maintains two auxiliary data structures
visitedset to indicate that all reachable nodes from the current node have been visited (and no cycles have been found), and
in_processset to indicate that the current node has started exploration, but not all reachable nodes from it have been explored.
A graph contains a cycle when a node which is present in the
in_process set, and not present in the
visited set is visited again! Here is the private method
DFS that implements this logic, and returns
true if the reachable graph from
curr contains a cycle.
As the final piece of the puzzle, let’s use the
DFS method in our
contains_cycle method, and complete the class implementation.
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).
Originally published at https://cppcodingzen.com on January 15, 2021.