Code Signal — Graphs — New Road System
Today we are going to solve the graph test from CodeSignal New Road System, we will take a look at the test and solve it step by step while explaining how such a test can be solved.
If you haven’t tried the test yet, please go to CodeSignal and try the test before reading, it will be more interesting that way, always try to solve the test before looking at the solutions 😇.
*The full solution is at the bottom of the post*
The king of the kingdom has decided to make a new road system in which, each city should have the same amount of single direction roads leading in and out of the city, for example, if city number 1 has one road in, it should also have one road out, this can be seen in the graph in the example.
We start with an empty function that receives a roadRegister which is a 2D array of cities that contain roads, this can be read as a table, city index 0 means the first array, so the 2D array:
roadRegister = [[false, true, false, false],
[false, false, true, false],
[true, false, false, true ],
[false, false, true, false]]The array can also be described as this table:
My first intuition was to start by printing the roads which lead somewhere, using a simple double loop I printed out which city leads where, city 0 => 1 means a road is coming out of city 0 and going into city 1.
In order to finish the task I need to know how many roads go in and out of every city, this means that I have to loop over all the cities and all the roads which means O(n²) complexity, and collect how many roads lead in and out of each city.
To collect the number of roads leading in and out I created 2 arrays the same length as the cities and filled them with 0.
const inComingRoads = new Array(roadRegister.length).fill(0);
const outGoingRoads = new Array(roadRegister.length).fill(0);
When we are done filling the arrays with the in/out roads we can loop over them again and make sure each city has the same amount of cities in and out with the every array function.
return inComingRoads.every((inComingRoadsCount, cityIndex) => {
return outGoingRoads[cityIndex] === inComingRoadsCount;
});And putting it all together would look like this:
Last words
This is a pretty simple test in my opinion, but it gives an understanding of how to view graphs and how to work with 2D arrays, hopefully, the next graph challenges will be harder 🤓.
Please clap and follow as I will publish content every couple of weeks, I truly appreciate every follower, clapper, and commenter 🙂.
