ThoughtWorks 的一道笔试题 - blog - CSDN博客

blog

凡所有相，皆是虚妄，若见诸相非相，即见如来

• 条新通知
• 登录
• 注册
• 欢迎
• 退出
• 我的博客
• 配置
• 写文章
• 文章管理
• 博客首页

*

• 全站 当前博客 *

• 空间

• 博客
• 好友
• 相册
• 留言

用户操作 [留言] [发消息] [加为好友] 订阅我的博客 [编辑]passos的公告 [编辑]文章分类 * 01010101

• C/Linux
• Delphi
• dotNet
• 人生
• 世事难料
• 形而上学
• 杂类语言存档 * 2009年12月(2)
• 2009年11月(1)
• 2009年07月(1)
• 2009年05月(2)
• 2009年02月(1)
• 2008年12月(1)
• 2008年10月(2)
• 2008年06月(1)
• 2008年04月(1)
• 2006年04月(2)
• 2005年07月(1)
• 2005年05月(1)
• 2005年04月(6)
• 2005年03月(2)
• 2004年10月(4)
• 2001年09月(2)

  公告： [意见反馈][官方博客]

ThoughtWorks 的一道笔试题 收藏

PROBLEM ONE: TRAINS Problem: 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

简单来说，就是一个图的搜索问题。用数组来表示图，简化之后大致的解决方案都差不多。

6:

1. public class Graphmain { 1.
2. public int[][] map = {
3. {-1, 5, -1, 5, 7},
4. {-1, -1, 4, -1, -1},
5. {-1, -1, -1, 8, 2},
6. {-1, -1, 8, -1, 6},
7. {-1, 3, -1, -1, -1},
8. };
10. public void dfs(String end, String path, int maxLength)
11. {
12. if (path.length() - 1 > maxLength) return;
14. if ( path.length() > 1 && path.endsWith(end) ) {
15. System.out.println(path + ", " + path.length());
16. }
18. char lastChar = path.charAt(path.length()-1);
19. int lastNodeIndex = lastChar - 'A';
21. for ( int i=0; i<map[lastNodeIndex].length; i++ )
22. {
23. char newChar = (char)(i + 'A');
24. if ( map[lastNodeIndex][i] > 0) {
25. dfs(end, path + newChar, maxLength);
26. }
27. }
28. }
30. public static void main(String[] args) {
31. Graphmain g = new Graphmain();
33. g.dfs("C", "C", 3);
34. }
35. } 1.

7:

1. public class Graphmain { 1.
2. public int[][] map = {
3. { -1, 5, -1, 5, 7 },
4. { -1, -1, 4, -1, -1 },
5. { -1, -1, -1, 8, 2 },
6. { -1, -1, 8, -1, 6 },
7. { -1, 3, -1, -1, -1 }
8. }; 1.
9. public void bfs(String start, String end, int hops) {
10. String lastRoute = start; 1.
11. for (int hop = 0; hop < hops; hop++) {
12. String route = "";
13. for (int i = 0; i < lastRoute.length(); i++) {
14. char c = lastRoute.charAt(i);
15. int id = c - 'A'; 1.
16. for (int j = 0; j < map[id].length; j++) {
17. if (map[id][j] > 0)
18. route = route + (char) (j + 'A');
19. }
20. }
21. // System.out.println(lastRoute);
22. lastRoute = route;
23. } 1.
24. // System.out.println(lastRoute);
25. System.out.println(lastRoute.split(end).length - 1);
26. } 1.
27. public static void main(String[] args) {
28. Graphmain g = new Graphmain(); 1.
29. g.bfs("A", "C", 4);
30. }
31. } 1.

8/9:

1. public class Graphmain { 1.
2. public int[][] map = {
3. {-1, 5, -1, 5, 7},
4. {-1, -1, 4, -1, -1},
5. {-1, -1, -1, 8, 2},
6. {-1, -1, 8, -1, 6},
7. {-1, 3, -1, -1, -1},
8. };
10. public void dfs(String end, String path, int cost) {
11. if (path.endsWith(end) && cost < bestCost && cost > 0) {
12. bestPath = path;
13. bestCost = cost;
14. return;
15. }
16. char lastChar = path.charAt(path.length() - 1);
17. int lastNodeIndex = lastChar - 'A'; 1.
18. for (int i = 0; i < map[lastNodeIndex].length; i++) {
19. char newChar = (char) (i + 'A');
20. int newCost = map[lastNodeIndex][i];
21. if (newCost > 0) {
22. if (path.indexOf(newChar) > 0)
23. continue;
24. dfs(end, path + newChar, cost + newCost);
25. }
26. }
27. } 1.
28. public String bestPath = "";
29. public int bestCost = Integer.MAX_VALUE; 1.
30. public static void main(String[] args) {
31. Graphmain g = new Graphmain(); 1.
32. g.dfs("C", "A", 0); // 8
33. // g.dfs("B", "B", 0); // 9 1.
34. System.out.println("Best Path: " + g.bestPath + "\nCost: " + g.bestCost);
35. }
36. } 1.

10:

1. public class Graphmain { 1.
2. public int[][] map = {
3. {-1, 5, -1, 5, 7},
4. {-1, -1, 4, -1, -1},
5. {-1, -1, -1, 8, 2},
6. {-1, -1, 8, -1, 6},
7. {-1, 3, -1, -1, -1},
8. };
10. public void dfs(String end, String path, int cost) {
11. if (cost >= 30)
12. return; 1.
13. if (cost > 0 && path.endsWith(end)) {
14. System.out.println(path + ", " + cost);
15. } 1.
16. char lastChar = path.charAt(path.length() - 1);
17. int lastNodeIndex = lastChar - 'A'; 1.
18. for (int i = 0; i < map[lastNodeIndex].length; i++) {
19. char newChar = (char) (i + 'A');
20. int newCost = map[lastNodeIndex][i];
21. if (newCost > 0) {
22. dfs(end, path + newChar, cost + newCost);
23. }
24. }
25. } 1.
26. public static void main(String[] args) {
27. Graphmain g = new Graphmain(); 1.
28. g.dfs("C", "C", 0);
29. }
30. } 1.

发表于 @ 2008年12月11日　15:30:00 | 评论( loading... )| 编辑| 举报| 收藏

旧一篇:Android源码构建工具速览（二）—— 清单文件 | 新一篇:为什么cpio要比tar好

查看最新精华文章 请访问博客首页相关文章

• 发表评论

• 表 情：

• 

• 评论内容： *

• 用 户 名：

• 登录 注册 匿名评论

• 验 证 码：

• 重新获得验证码

热门招聘职位