收到ThoughtWorks的面试邀请，HR电话初面后，说是要做题。

给发了3道题，任选一道。

ThoughtWorks是什么样的公司呢？外企，听说很牛，什么“敏捷开发模式”就是那公司

首创的概念。出的题目也有些奇怪，选取第一道如下：

Problem one: Trains

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.

Input: 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.

Output: For test input 1 through 5, if no such route exists, output ‘NO SUCH ROUTE’. Otherwise, follow the route as given; do not make any extra stops! For example, the first problem means to start at city A, then travel directly to city B (a distance of 5), then directly to city C (a distance of 4).

1. The distance of the route A-B-C.
2. The distance of the route A-D.
3. The distance of the route A-D-C.
4. The distance of the route A-E-B-C-D.
5. The distance of the route A-E-D.
6. 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).
7. 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).
8. The length of the shortest route (in terms of distance to travel) from A to C.
9. The length of the shortest route (in terms of distance to travel) from B to B.
10. 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.

Test Input:

For the test input, the towns are named using the first few letters of the alphabet from A to D. A route between two towns (A to B) with a distance of 5 is represented as AB5.

Graph: AB5, BC4, CD8, DC8, DE6, AD5, CE2, EB3, AE7

Expected Output:

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

看题目，一开始摸不着头脑，甚至用了翻译琢磨。做完第一道提交了，具体对不对，

估计不好说。现把自己总结的解题思路写下来，留个念。

问题大致分5类：

1.求路径距离；
2.给定起始点，求路径条数；
3.给定遍历深度，求路径条数；
4.给定路径长度，求路径条数；
5.求最短路径

这道题考察的基础有很多：

1.项目结构

• 包的分类，命名
• 业务分层
• 依赖管理

2.数据结构设计

• 数据定义
• 选择哪几种集合
• 集合的使用方法

3.程序设计

• 遍历，查找
• 复杂度

4.异常处理

• 自定义异常
• 抛出异常

5.单元测试

1.项目结构

项目结构，分了entity，service，test，exception等几个包，分别存放不同功能的class。依赖，最好使用maven做依赖管理。

2.数据结构设计

定义了town（城镇），route（路线）等基本对象。集合选择，(k,v)结构的，使用HashMap；单纯的无序集合，使用HashSet；集合的随机修改，用到了LinkedList，对集合的随机查找，遍历，也用到了ArrayList。

3.程序设计

大致知道程序需要用到深度遍历，广度遍历等思路。我看了二叉树的遍历，说是，广度遍历，是使用队列；深度遍历，是
使用堆栈。但这里，其实是树遍历，其实还用到迭代遍历。迭代遍历不好理解。总之，也借鉴了别人的设计。

我也想到了复杂度这一点。O(N)当然是最好。但既有树遍历，又有迭代遍历，复杂度是O(N)的N次方。感觉这点无解，之前做的少，不知道有什么优化版本。查找的话，个人倾向for循环遍历。

4.异常处理

应该是要自定一个异常，然后打印输出异常情况。后来想，应该把打印输出，也写在自定异常类里面。可是提交答案的时候，忘记做了。

异常使用throw关键字。没有用try catch

5.单元测试

这里面，一开始我以为很简单，但看了下别人的处理，感觉这里的细节也很多。诸如类的初始化，注解的使用，测试方法的排序。

总之，这道题考察的基础有很多，除了上面提到的，应该还有一些，限本人能力，一时还看不出。就先记下吧。

更多精彩内容