Friday, March 29, 2013

Distance between 2 cities

There is a straight road with several towns along the road. Your program is given the distance between each pair of adjacent towns. You need to write a class to accept this input (as initialization) and has a method to calculate the distances between two arbitrary towns.

class Road - initialized with list of towns and distances between adjacent towns
    Road(String[] towns, int[] distances)
    Road.findDistance(String from, String to)
    Road.findDistance - takes two towns and returns distance between them

A --- B ---- C --- D --- E
    10    23     12     10

towns = {“A”, “B”, “C”, “D”, “E”}
distances = {10, 23, 12, 10}

findDistance(“C”, “E”) = 22 -> takes constant time.

import java.util.HashMap;
import java.util.Map;

public class Road {

static Map<String, Integer> map = new HashMap<String, Integer>();
int size;
static int distance_sum[];

public Road(String[] towns, int[] distances) {

if (towns.length < 2 || distances.length < 1
|| distances.length != towns.length - 1)
return;

distance_sum = new int[distances.length];
for (int i = 0; i < towns.length; i++) {
map.put(towns[i], i);
}

distance_sum[0] = 0;
for (int i = 1; i < distances.length + 1; i++) {
distance_sum[i] += distances[i - 1] + distance_sum[i - 1];
}
}

public static int findDistance(String from, String to) {
int startIndex = -1;
if (map.get(from) != null)
startIndex = map.get(from);

int toIndex = -1;
if (map.get(to) != null)
toIndex = map.get(to);

if (toIndex == -1 || startIndex == -1)
return -1;
if (startIndex == toIndex)
return 0;

if (startIndex > toIndex) {
return distance_sum[startIndex] - distance_sum[toIndex];
} else
return distance_sum[toIndex] - distance_sum[startIndex];
}

}

No comments: