This coding-challenge was part of the interview process with ThoughtWorks for a software developer role. Time frame was about 3 days.
Commuter railroad service for the towns in Kiwiland.
The local commuter railroad services a number of towns in Kiwiland. Because of monetary concerns, all of the tracks are 'one-way.' That is, a route from Kaitaia to Invercargill does not imply the existence of a route from Invercargill to Kaitaia. In fact, even if both of these routes do happen to exist, they are distinct and are not necessarily the same distance!
The purpose of this problem is to help the railroad provide its customers with information about the routes. In particular, you will compute the distance along a certain route, the number of different routes between two towns, and the shortest route between two towns.
A directed graph where a node represents a town and an edge represents a route between two towns. The weighting of the edge represents the distance between the two towns. A given route will never appear more than once, and for a given route, the starting and ending town will not be the same town.
The towns are named using the first few letters of the alphabet from
E. A route between two towns (
B) with a distance of
5 is represented as
AB5. A directed graph is represented by a list of routes, with each route as a separate line.
- Compute the distance along a certain route. If no such route exists, output 'NO SUCH ROUTE'. Otherwise, follow the route as given; do not make any extra stops!
- Compute the number of different routes between two towns.
- Compute the shortest route between two towns.
Example Input & Output
Below follows an example with input data, actions performed and expected output result.
The distance of the route A-B-C.
The distance of the route A-D.
The distance of the route A-D-C.
The distance of the route A-E-B-C-D.
The distance of the route A-E-D.
The number of trips starting at C and ending at C with a maximum of 3 stops. In the sample data below, there are two such trips: C-D-C (2 stops). and C-E-B-C (3 stops).
The number of trips starting at A and ending at C with exactly 4 stops. In the sample data below, there are three such trips: A to C (via B,C,D); A to C (via D,C,D); and A to C (via D,E,B).
The length of the shortest route (in terms of distance to travel) from A to C.
The length of the shortest route (in terms of distance to travel) from B to B.
The number of different routes from C to C with a distance of less than 30. In the sample data, the trips are: CDC, CEBC, CEBCDC, CDCEBC, CDEBC, CEBCEBC, CEBCEBCEBC.
Output #1: 9
Output #2: 5
Output #3: 13
Output #4: 22
Output #5: NO SUCH ROUTE
Output #6: 2
Output #7: 3
Output #8: 9
Output #9: 9
Output #10: 7
Run JUnit Tests
To run the existing JUnit tests using Gradle, execute the following commands
$ cd path/to/Trains
$ gradle test
JUnit tests are located under
Output messages are both availabe in English and German, depending on the system's default locale. The messages are available in the
trains_de.properties file, respectively, and can be found under
The project is a Gradle project. To build, open up your Terminal and fire up the following commands:
$ cd path/to/Trains
$ gradle build
You should see a 'BUILD SUCCESSFUL' message when everything went well. When the build completed succesfully, the program will be named
Trains.jar and can be found under
/build/libs/ in the
Trains project directory.
Run the program as follows:
$ java -jar Trains.jar path/to/graph.txt path/to/commands.txt
MacBook-Pro:Trains lucas$ java -jar build/libs/Trains.jar ../../graph.txt ../../commands.txt
Import Project with an IDE
Import Project with IntelliJ IDEA
To import the project using Eclipse, do the following:
File -> New -> Project from Existing Sources from the main menu.
- Browse to the project directory and click
Gradle as build tool and click
Gradle home and make sure the
Gradle JVM is set to version
Import Project with Eclipse
To import the project using Eclipse, do the following:
File -> Import... -> Gradle -> Gradle Project from the main menu.
Browse... for the
- Select and open the
- Select all projects.
- You may need Gradle Integration for Eclipse
- Make sure to replace
apply plugin: 'idea' with
apply plugin: 'eclipse' in the
build.gradle file located in project's root directory.
JavaDoc can be found in the here.
Important Classes & Interfaces
Main class is the main entry point of the application. It contains a
main() method whose signature looks like this
public static void main(String args)
which the runtime system calls when the program starts. The
main() method then calls all the other methods required to run the application. It takes two arguments. The first argument is the path to the file containing the Town Graph, while the second argument points to the file containing the commands we want our application to execute.
LLDirectedGraph represents a generic directed graph. It provides basic functionality for adding nodes and edges as well as methods for computing the shortest path (Dijkstra) and distance between nodes.
LLTownMap interface represents a map that stores towns using a
LLDirectedGraph underneath. It wraps the functionality of
LLDirectedGraph and provides methods for accessing it using the town names.
Model representing a town.
LLRailRoadServiceImpl implements the
LLRailRoadService interface. It makes use of
LLTownMap. Although most of the functionality in
LLRailRoadServiceImpl is cascaded to
LLTownMap, the idea of providing
LLRailRoadServiceImpl, is to separate the functionality between a service system and a map. That is,
LLRailRoadServiceImpl could be expanded to support further functionality such as
nextTrainDepartureTime() without the need to modify the
Interface defining a command that can be executed by calling its
execute() method. A typical command would be calculating the distance of a route.
Interface that defines which functionality an
LLCommand factory must provide.
LLCommandFactory provides functionality for creating new commands that implement the
This class implements the
LLCommandFactory interface. It provides methods for creating concrete command implementations of the abstract type
LLRailRoadServiceCommandFactory gets initialised with an
LLRailRoadService, which it sets as receiver in
LLCommandFactory commandFactory = new LLRailRoadServiceCommandFactory(service);
Classes inheriting from
LLAbstractRailRoadServiceCommand are commands that implement the
LLCommand interface but are specifically implemented for the
LLRailRoadService. An example would be the
LLCommand commands. The
LLCommandProccesor gets initialised with an
LLCommandProccesor processor = new LLCommandProccesor(commandFactory);
LLCommandFactory will then be used by
LLCommandProccesor to create
LLCommand objects for a given input.
LLCommandProccesor can take and execute a single command in the form of text:
String result = processor.run("distance;A;D"); // compute distance between node 'A' and 'B'
or run all commands contained in a text file:
String result = processor.runAll("/Users/lucas/commands.txt"); // execute all commands in commands.txt
- distance;[TOWN 1];[TOWN 2]; ... ;[TOWN N] - Compute distance of route. Example:
- count_routes_with_max_hops;[START TOWN];[DESTINATION TOWN];[MAX HOP COUNT] - Count routes with maximum number of hops. Example:
- count_routes_with_hops;[START TOWN];[DESTINATION TOWN];[HOP COUNT] - Count routes with exact number of hops. Example:
- count_routes_with_max_distance;[START TOWN];[DESTINATION TOWN];[MAX DISTANCE] - Count routes with maximum distance. Example:
- length_of_shortest_path;[START TOWN];[DESTINATION TOWN] - Compute length of shortest path between node. Example:
- shortest_path;[START TOWN];[DESTINATION TOWN] - Compute shortest path between nodes. Example:
static methods for global access to the application's properties.
Sample data for a graph and commands can be found here.