🖥️
Log4think
  • Introduction
  • Archive
  • 2016-12-13 JavaScript 中几种不同的基于 prototype 继承方式的区别
  • 2014-09-02 Facebook的Dalvik运行期补丁
  • 2014-08-19 理解AnguarJS中的模板编译
  • 2014-08-13 在Android中使用OSGi框架(Knopflerfish)
  • 2014-08-13 在Android中使用OSGi框架(Apache Felix)
  • 2014-07-30 3rd-party apt-key list for Ubuntu
  • 2014-07-21 'Failed to clone a large git repository: The remote end hung up unexpectedly'
  • 2014-07-02 genymotion Qt error in Ubuntu
  • 2014-04-30 可自动安装依赖的Ubuntu离线包安装工具 gdebi
  • 2014-04-23 解决搜狗输入法Ubuntu 14.04下黑块状态条
  • 2014-04-08 Setup Ghost blog system on Ubuntu
  • 2014-03-28 Trace a process
  • 2014-03-25 Forecast::IO 599 Internal Exception
  • 2014-03-23 Mac Tips
  • 2014-01-17 LD_LIBRARY_PATH shouldn't contain the current directory
  • 2014-01-10 Python on vim
  • 2013-11-12 ibus-pinyin doesn't work in KUbuntu 13.10
  • 2013-11-11 phpMyAdmin login error to remote server
  • 2013-11-04 Get SNMP(v3) working on Ubuntu 12.04
  • 2013-10-30 Accessing Facebook by LWP
  • 2013-10-17 Log4perl多个Appender重复输出日志的问题解决办法
  • 2013-04-19 How to enable ORMLite internal log on Android
  • 2013-02-20 Bash Shortcuts
  • 2013-02-20 '"adb shell dumpsys" parameter list'
  • 2013-01-27 循环有序数组的二分查找
  • 2013-01-23 为Java运行环境导入根证书解决Eclipse的TFS插件的"PKIX path building failed"错误
  • 2013-01-21 ant 中通过重新定义 project.all.jars.path 在 classpath 中引入外部 jar 文件
  • 2012-09-22 Android的滚动条实现细节
  • 2012-02-05 hostname自动变成bogon的问题
  • 2011-07-09 代码段速记 gist.github.com
  • 2011-07-08 A perl Data.Dumper clone for Python
  • 2011-06-22 魔兽世界私服Trinity,从源码开始
  • 2011-06-13 魔兽世界3.3.5 13930登录数据包分析
  • 2011-06-13 魔兽世界 3.3.5 13930 Trinity 认证补丁
  • 2011-05-20 统一业务模型(UBM) in ERP5
  • 2011-03-08 制作ASCII字符动画
  • 2011-01-14 Ubuntu升级导致的udevd错误修复
  • 2011-01-09 行列有序矩阵求第K个数
  • 2011-01-09 字节按位逆序
  • 2011-01-01 编程之美 1.2 中国相帅问题的一个简洁解法
  • 2010-11-26 为Windows 7/Windows Server 2008添加IPX协议
  • 2010-11-12 How to debug with Android Logging
  • 2010-09-16 利用google-code-prettify做网页内源码的语法高亮
  • 2010-09-05 10 Ways We Hurt Our Romantic Relationships
  • 2010-08-30 利用ipkall+xlite+iptel.org开通google voice
  • 2010-08-27 避免Android开发中的ANR
  • 2010-08-27 在Eclipse中查看Android SDK的源代码
  • 2010-08-18 Git中判断一个commit是否在某个branch中
  • 2010-08-04 修正auto-excerpt产生带格式的摘要
  • 2010-03-31 Go 编程语言入门教程
  • 2010-03-13 利用外部VPS主机通过ssh隧道穿透防火墙连接内网
  • 2009-12-30 旋转矩阵
  • 2009-02-10 为什么cpio要比tar好
  • 2008-12-11 ThoughtWorks 的一道笔试题
  • 2008-11-18 长距离打车如何省钱?
  • 2007-02-08 ftp后台自动上传下载
  • 2006-06-12 vi cheatsheet
  • 2006-04-19 修正mysqlcc在MySQL 5.0上常报的 Table 'xxx' doesn't exist 错误
  • 2006-04-01 'Perl中不寻常的 ?: 运算符'
  • 2005-09-13 关于IoC、低耦合、配置文件及其本质意义的思考
  • 2005-09-13 Perl与数据库DBI快速入门
  • 2005-09-12 Perl无废话入门指南
  • 2005-07-16 Solaris 下安装Perl的DBD-mysql模块失败的原因以及解决办法
  • 2004-10-15 SharpDevelop的AddInTree View 插件
  • 2004-10-14 SharpDevelop源码分析 (完整版)
由 GitBook 提供支持
在本页

这有帮助吗?

2008-12-11 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

用一个带权重的有向图表示节点之间的关系,使用深度优先搜索。

1-5:

package com.log4think.code;

public class TrainMap {

    public int[][] map = {
        //    A   B   C   D   E
            {-1,  5, -1,  5,  7},
            {-1, -1,  4, -1, -1},
            {-1, -1, -1,  8,  2},
            {-1, -1,  8, -1,  6},
            {-1,  3, -1, -1, -1},
    };

    public int getDistance(String path)
    {
        int distance = 0;

        for (int i=0; i
<path.length()-1; i++) {
            // get the node index in map
            int fromNodeIndex = path.charAt(i) - 'A';
            int toNodeIndex = path.charAt(i+1) - 'A';

            // check the distance of two node in map
            if (map[fromNodeIndex][toNodeIndex] == -1) {
                return -1;
            } else {
                distance += map[fromNodeIndex][toNodeIndex];
            }
        }

        return distance;
    }

    public static void main(String[] args) {
        TrainMap g = new TrainMap();

        int distance = g.getDistance("ABC");
        if (distance > 0)
            System.out.println(distance);
        else
            System.out.println("NO SUCH ROUTE");

//        g.findDistance("AD");
//        g.findDistance("ADC");
//        g.findDistance("AEBCD");
//        g.findDistance("AED");
    }
}

6:

public class TrainMap {

    public int[][] map = {
            {-1, 5, -1, 5, 7},
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };

    // used to record the trip round count
    public int tripCount = 0;

    /***
     *
     * @param end , the end node. if we reach it we found a path
     * @param path , the current path we already have
     * @param maxLength, the maximum stops
     */
    public void dfs(String end, String path, int maxLength)
    {
        // this is for debug and trace
        // System.out.println(";; " + path);

        // if the path reach the maximum stops, then cancel search
        if (path.length() - 1 > maxLength) return;

        // check if we have reach the "end" node
        if ( path.length() > 1 && path.endsWith(end) ) {
            System.out.println(path + ", " + tripCount);
            tripCount ++;
        }

        // caculate the lastest node index in map
        char lastChar = path.charAt(path.length()-1);
        int lastNodeIndex = lastChar - 'A';

        // loop all nodes in map which connected to lastNode, and try it
        for ( int i=0; i
<map[lastNodeIndex].length; i++ )
        {
            // convert index to node name
            char newChar = (char)(i + 'A');
            // try and search
            if ( map[lastNodeIndex][i] > 0) {
                dfs(end, path + newChar, maxLength);
            }
        }
    }

    public static void main(String[] args) {
        TrainMap g = new TrainMap();

        g.dfs("C", "C", 3);
    }
}

7:

public class TrainMap {

    public int[][] map = {
            { -1, 5, -1, 5, 7 },
            { -1, -1, 4, -1, -1 },
            { -1, -1, -1, 8, 2 },
            { -1, -1, 8, -1, 6 },
            { -1, 3, -1, -1, -1 }
    };

    public void bfs(String start, String end, int hops) {
        String lastRoute = start;

        for (int hop = 0; hop < hops; hop++) {
            String route = "";
            for (int i = 0; i < lastRoute.length(); i++) {
                char c = lastRoute.charAt(i);
                int id = c - 'A';

                for (int j = 0; j < map[id].length; j++) {
                    if (map[id][j] > 0)
                        route = route + (char) (j + 'A');
                }
            }
//          System.out.println(lastRoute);
            lastRoute = route;
        }

//      System.out.println(lastRoute);
        System.out.println(lastRoute.split(end).length - 1);
    }

    public static void main(String[] args) {
        TrainMap g = new TrainMap();

        g.bfs("A", "C", 4);
    }
}

8/9:

public class TrainMap {

    public int[][] map = {
            {-1, 5, -1, 5, 7},
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };

    public void dfs(String end, String path, int cost) {
        if (path.endsWith(end) && cost < bestCost && cost > 0) {
            bestPath = path;
            bestCost = cost;
            return;
        }
        char lastChar = path.charAt(path.length() - 1);
        int lastNodeIndex = lastChar - 'A';

        for (int i = 0; i < map[lastNodeIndex].length; i++) {
            char newChar = (char) (i + 'A');
            int newCost = map[lastNodeIndex][i];
            if (newCost > 0) {
                if (path.indexOf(newChar) > 0)
                    continue;
                dfs(end, path + newChar, cost + newCost);
            }
        }
    }

    public String bestPath = "";
    public int bestCost = Integer.MAX_VALUE;

    public static void main(String[] args) {
        TrainMap g = new TrainMap();

        g.dfs("C", "A", 0); // 8
//      g.dfs("B", "B", 0); // 9

        System.out.println("Best Path: " + g.bestPath + "\nCost: " + g.bestCost);
    }
}

10:

public class TrainMap {

    public int[][] map = {
            {-1, 5, -1, 5, 7},
            {-1, -1, 4, -1, -1},
            {-1, -1, -1, 8, 2},
            {-1, -1, 8, -1, 6},
            {-1, 3, -1, -1, -1},
    };

    public void dfs(String end, String path, int cost) {
        if (cost >= 30)
            return;

        if (cost > 0 && path.endsWith(end)) {
            System.out.println(path + ", " + cost);
        }

        char lastChar = path.charAt(path.length() - 1);
        int lastNodeIndex = lastChar - 'A';

        for (int i = 0; i < map[lastNodeIndex].length; i++) {
            char newChar = (char) (i + 'A');
            int newCost = map[lastNodeIndex][i];
            if (newCost > 0) {
                dfs(end, path + newChar, cost + newCost);
            }
        }
    }

    public static void main(String[] args) {
        TrainMap g = new TrainMap();

        g.dfs("C", "C", 0);
    }
}
上一页2009-02-10 为什么cpio要比tar好下一页2008-11-18 长距离打车如何省钱?

最后更新于5年前

这有帮助吗?