今天在网上看到这样一个题目，是一个美国IT企业的面试题，要求在两天内写出来。
大意是从一个文件中读取出可连通的城市对，给出两个城市，判断是否可连通，如果
可连通就输出yes，不可连通就输出no，否则给出命令行帮助。
我想这考的就是一个算法，至于程序设计语言则是基础。
想了一下，半天就做出来了，看到中国人的智商都是比较高的！呵呵，说笑了！
看到有人以非常OOP的思想把这个题目做出来了，甚至扩展了，想到两个城市之间的最短路径。
我觉得想像力太丰富了，我认为超出需求的程序就是不合格的程序。这是题外话了。
以下是英文原题：
Suppose you are given a text file containing pairs of city names, one pair per line, with the names on each line separated by a comma. The
file might look something like:
Philadelphia, Pittsburgh
Boston, New York
Philadelphia, New York
Los Angeles, San Diego
New York, Croton-Harmon
St. Petersburg, Tampa
Each line of the file indicates that it is possible to travel between the two cities named. (More formally, if we think of the cities as nodes in a graph, each line of the file specifies an edge between two nodes.)
In the example above it is possible to travel between Boston and New York, and also between New York and Philadelphia and between Philadelphia and Pittsburgh, so it follows that Boston and Pittsburgh are connected. On the other hand, there is no path between Boston an Tampa, so they are not connected.
---
Write a Java(r) program, called "Connected", that reads in such a file and outputs whether two specified cities are connected. The program will be invoked from the command line as:
java Connected <filename> <cityname1> <cityname2>
and will output a single line stating:
yes or no
Here are some sample interactions, assuming the example file above is named "cities.txt".
> java Connected cities.txt "New York" Boston
yes
> java Connected cities.txt Boston Pittsburgh
yes
> java Connected cities.txt Boston Tampa
no
> java Connected cities.txt Boston Ypsilanti
no
---
Notes
* Commas will not appear within city names in the file. For example, "Washington, D.C." will not appear in the file as a city name.
* You can depend on command-line quoting for cities with spaces in their names, like "New York". This should, thus, require no extra code on your part.
* Your choice of algorithms and data structures should allow the program to handle arbitrarily large files reasonably efficiently. You can,
however, assume that the file will fit in memory.
* The program is permitted to return any or no output when given a malformed input file or malformed command line.
* If a city is not in the file, then it is connected to no other city.
以下是我写的程序的代码：
程序内容
package eli.math;
import java.io.FileReader;
import java.io.IOException;
import java.io.LineNumberReader;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
/** *//**
* @author <a href="mailto:eli.wuhan@gmail.com">屹砾</a>
*/
public class Connected 
{
/** *//**
* 将已知城市根据连通性进行分组，可连通的城市分在一个组.
*
* @param set
* 包含若干组连通城市对的集合
* @return 包含若干组可连通城市的集合
*/
@SuppressWarnings("unchecked")
protected Set<Set<String>> calcKinds(Set<Set<String>> set) {
Set<Set<String>> result = new HashSet<Set<String>>(0);
Set[] arr = new Set[set.size()];
set.toArray(arr);
for (int i = arr.length - 1; i > 0; i--) {
for (int j = i - 1; j >= 0; j--) {
if (arr[i] != null) {
for (Iterator it = arr[i].iterator(); it.hasNext();) {
if (arr[j].contains(it.next())) {
arr[j].addAll(arr[i]);
arr[i] = null;
break;
}
}
}
}
}
for (int i = 0; i < arr.length; i++) {
if (arr[i] != null) {
result.add(arr[i]);
}
}
return result;
}
/** *//**
* 指定的两个城市是否连接
*
* @param cities
* 包含若干组连通城市对的集合
* @param beginCity
* 开始的城市
* @param endCity
* 结束的城市
* @return 是否连通
*/
public boolean isConnected(Set<Set<String>> cities, String beginCity,
String endCity) {
Set<Set<String>> set = calcKinds(cities);
for (Iterator<Set<String>> it = set.iterator(); it.hasNext();) {
Set<String> set2 = it.next();
if (set2.contains(beginCity) && set2.contains(endCity)) {
return true;
}
}
return false;
}
/** *//**
* 从文件读取城市对。文件中每一行为一个城市对，以半角逗号分隔。
*
* @param file
* 文件名
* @return 包含若干组连通城市对的集合
* @throws IOException
*/
protected Set<Set<String>> readFromFile(String file) throws IOException {
Set<Set<String>> cities = new HashSet<Set<String>>(0);
LineNumberReader fileReader = new LineNumberReader(new FileReader(file));
Set<String> tmp = null;
for (String line = fileReader.readLine(); line != null; line = fileReader
.readLine()) {
String[] arr = line.split(",");
if (arr.length == 2) {
tmp = new HashSet<String>(0);
tmp.add(arr[0].trim());
tmp.add(arr[1].trim());
cities.add(tmp);
}
}
return cities;
}
public static void main(String[] args) {
Connected cities = new Connected();
try {
if (args.length == 3) {
boolean bool = cities.isConnected(cities.readFromFile(args[0]),
args[1], args[2]);
System.out.println(bool ? "yes" : "no");
} else {
throw new IllegalArgumentException();
}
} catch (Exception e) {
System.out.println("Usage: java " + Connected.class.getName()
+ " <citylist.txt> <beginCity> <endCity>");
}
}
}
相关链接：
老外的面试题，要求两天内完成