Question Level: Hard
Best Telescope Site
Sclentists want to select the best site to bulld thelr new space observatory. The best site Is defined as the city with the least ambient light from surrounding cities.
There are city.nodes cities numbered from 1 to city_nodes. The cities are connected by bidirectional edges to form a connected graph. The welght of each edge represents the distance between the connected clties. There is a distance Threshold that represents the minimum desired distance from any other city. Determine the city with the smallest number of neighbouring cities that are nearer than the distance Threshold. if there are multiple answers, choose th higher city number.
Example
distanceThreshold= 3
city nodes = 3
city_ from = [1, 2]
city to = [2, 3]
city_weight = [3, 1]
Rest information given in the images below
Solution given by @vivek6301
If someone could find an even more optimized solution please let us know
I got this question in the Atlassian Coding Test.
Solution:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class BestTelescopeSite {
public static void main(String[] args) {
int distanceThreshold = 1;
int city_nodes = 4;
int[] city_from = {1,1,1,2,2,3};
int[] city_to = {2,3,4,3,4,4};
int[] city_weight = {1,3,2,1,1,1};
System.out.println(findBestTelescopeSite(distanceThreshold, city_nodes, city_from, city_to, city_weight));
}
private static int findBestTelescopeSite(int distanceThreshold, int city_nodes, int[] city_from, int[] city_to, int[] city_weight) {
List<List<List<Integer>>> adjList = new ArrayList<>();
for (int i = 1; i <= city_nodes; i++) {
adjList.add(new ArrayList<List<Integer>>());
}
for (int i = 0; i < city_from.length; i++) {
adjList.get(city_from[i]-1).add(List.of(city_to[i]-1, city_weight[i]));
adjList.get(city_to[i]-1).add(List.of(city_from[i]-1, city_weight[i]));
}
int minConnections = Integer.MAX_VALUE, minConnectedNode = Integer.MAX_VALUE;
for (int i = 0; i < adjList.size(); i++) {
int[] dist = dijkstra(adjList, i);
int connections = 0;
for (int j = 0; j < dist.length; j++) {
if (i != j && dist[j] <= distanceThreshold) {
connections += 1;
}
}
if (connections <= minConnections) {
minConnections = connections;
minConnectedNode = i;
}
}
return minConnectedNode + 1;
}
private static int[] dijkstra(List<List<List<Integer>>> adjList, int source) {
int vertexCount = adjList.size();
int[] dist = new int[vertexCount];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[source] = 0;
PriorityQueue<Pair> pq = new PriorityQueue<>();
pq.add(new Pair(source, 0));
boolean[] visited = new boolean[vertexCount];
while (!pq.isEmpty()) {
Pair removed = pq.poll();
visited[removed.node] = true;
for (List<Integer> adj: adjList.get(removed.node)) {
int adjNode = adj.get(0);
int weight = adj.get(1);
if (!visited[adjNode] && dist[removed.node] != Integer.MAX_VALUE && dist[removed.node] + weight < dist[adjNode]) {
dist[adjNode] = dist[removed.node] + weight;
pq.add(new Pair(adjNode, dist[adjNode]));
}
}
}
return dist;
}
}
class Pair implements Comparable<Pair> {
int node;
int dist;
Pair (int node, int dist) {
this.node = node;
this.dist = dist;
}
public int compareTo(Pair b) {
if (this.dist != b.dist) {
return this.dist - b.dist;
}
return this.node - b.node;
}
}