前两天接到了TW的面试邀请,虽然很遗憾并没有通过。但过程中很充实,所以想写博客记录下来。

面试题

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).
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.

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


说真的第一次看到全英文内心崩溃的,但也有点小兴奋,毕竟外企,似乎有点高大上,哈哈哈哈。生活中接触的英文不多,猛地一看题没看懂,仔细一看题,还是没看懂+_+。只了解了大概的意思,后来谷歌翻译折腾了一番,原来里面有些图的术语。

题意

设计一个程序。类似高德地图那样,输入起点和终点,按照指定的要求输出指定的线路。要求就是题中从The distance of the route A-B-C.开始的往下十条。

第一天的准备

接到面试题的时候,电话中给了四天时间。其中有一天有事去了外地。还有三天都是上班时间,但好在上班没特别忙,可以抽出一部分时间学习图论。

图论相关知识

理解题意后,我没有急着做题,而是思考会用到那些知识点。为什么这么做,我会在《如何成为一个有效学习的高手?》感想系列里面详细讲述,不同类型的知识应该怎么学习。这是我列下的需要学习的知识点。思维很天马行空,有些点我也忘了怎么联想到的。

知识点的资料来源:
数据结构和算法系列17 图
图的概念和抽象数据类型

什么是图?

以下是维基百科的解释

相信是个正常人都看不懂,初次学习,我觉得用生活解释术语比用术语解释术语,所以说下我的理解。

图是链表的最复杂形态。链表像糖葫芦,一个接着一个。链表的结构可以类比成独生子关系,爸爸下面只有一个儿子(A节点后只有B节点)。如果是双胞胎(A节点后既有B又有C),这种数据结构叫树。再复杂点,乱伦关系(A、B、C之间相互有关系),这种结构就可以叫图了。A、B、C称为图的节点,他们之间的关系,称为边。

图的数据结构-Java代码实现

需要实现的有节点、边,根据题意,还需要路线的类。
知识点的资料来源:
数据结构:图的存储结构之邻接表
图论——图的邻接表实现——Java语言(完整demo)
Java邻接表表示加权有向图,附dijkstra最短路径算法

节点

public class Vertex {

    // 顶点名称
    private Character name;
}

public class Edge {
    // 边的起始节点
    private Vertex startVertex;

    // 边的结束节点
    private Vertex endVertex;

    // 边的权重  可以理解为从start到end的距离
    private Integer weights;
}

路线

public class Route {
    // 到初始顶点所有的路程
    private List<Edge> edges = new ArrayList<>();

    // 经历的路程
    private String road;

    // 路途的总距离
    private Integer distance = Algorithm.MAX;
}

public class WeightDirectedGraphByList {

    // 图中的所有顶点数组
    private List<Vertex> vertexList;

    // 每个节点拥有的边的信息
    private Map<Vertex, List<Edge>> vertexEdgeMap;
}

以上是邻接表的实现方式,适用于边比较少的情况,如果边多,可以用邻接矩阵。只需将图改成如下代码,而且不需要边类。

public class WeightDirectedGraphByMatrix {

    // 图中的所有顶点数组
    private List<Vertex> vertexList;

    // 邻接矩阵,index为顶点在List中的index,值为两顶点之间的权重
     private int[][] edgeMatrix; 
}

计算图路径的相关算法

算法我只搜索了两种,大致浏览了下思想。发现是基层算法的重装组合,比如戴克斯特拉算法是贪心算法+广度优先算法。所以要先去巩固基层算法。
知识点的资料来源:
戴克斯特拉算法
Dijkstra算法(三)之 Java详解
普里姆算法

基层算法-贪心算法

贪心算法的意思是每一个阶段都选择当前看来最优解。这个算法适用性不广,但他适用于求图中两点最短距离,如果每一步的距离都是最短的,那么结果一定是最短的。

基层算法-深度优先和广度优先算法

深度优先算法和广度优先算法类似。