Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
3,056 views
in Online Assessments by Expert (46,090 points) | 3,056 views

4 Answers

0 like 0 dislike
Best answer

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;
  }
}
by Expert (46,090 points)
0 like 0 dislike

O(n^3) solution ...
using flyod warshall algo..pretty easy

 

void solve(){
 
int thresh;
cin>>thresh;
int n,m;
cin>>n>>m;
vector<vector<int>>adj[n+1];
vector<vector<int>>dis(n+1,vector<int>(n+1,INT_MAX));

for(int i=0;i<n;i++) dis[i][i]=0;

for(int i=0;i<m;i++)
{
    int a,b,c;
    cin>>a>>b>>c;
    adj[a].push_back({b,c});
    adj[b].push_back({a,c});
    dis[a][b] = c;
    dis[b][a] = c;
}
for(int i=0;i<n;i++) dis[i][i]=0;

for(int k=1;k<=n;k++)
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(dis[i][k]!=INT_MAX && dis[k][j]!=INT_MAX && dis[i][k] + dis[k][j] < dis[i][j]){
                dis[i][j] = dis[i][k] + dis[k][j];
            }
        }
    }
}

int mini=INT_MAX;
int city=-1;

for(int i=1;i<=n;i++)
{
    int count = 0;
    for(int j=1;j<=n;j++)
    {
        if(i != j and dis[i][j] <= thresh)
        {
            count++;
        }
        cout<<i<<" "<<dis[i][j]<<" ";
    }
    cout<<endl;
    if(count <= mini)
    {
        mini = count;
        city = i;
    }
    // mini = min(count,mini);
}

cout<<city<<endl;
cout<<"nextt<<"<<endl;
}
by Expert (46,090 points)
0 like 0 dislike

floyd warshall algorithm in C#:

 

public int BestSite(int cityNumber, int distanceThreshold, int[][] edges)
{
int answer = 0;
int minCityCount = int.MaxValue;
int[,] matrix = new int[cityNumber, cityNumber];

 

        for (int i = 0; i < cityNumber; i++)
        {
            for (int j = 0; j < cityNumber; j++)
            {
                if(i ==  j) 
                    matrix[i, j] = 0;
                else 
                    matrix[i, j] = 1001;
            }
        }

        foreach (int[] e in edges)
        {
            matrix[e[0] - 1, e[1] - 1] = e[2];
            matrix[e[1] - 1, e[0] - 1] = e[2];
        }

        // for each city
        for (int k = 0; k < cityNumber; k++)
        {
            // do floyd algorithm
            for (int i = 0; i < cityNumber; i++)
            {
                for (int j = 0; j < cityNumber; j++)
                {
                    matrix[i, j] = Math.Min(matrix[i, j], matrix[i, k] + matrix[k, j]);
                }
            }
        }

        for (int i = 0; i < cityNumber; i++)
        {
            int cityCount = 0;
            for (int j = 0; j < cityNumber; j++)
            {
                if (matrix[i, j] <= distanceThreshold)
                    cityCount++;
            }

            if(cityCount <= minCityCount)
            {
                minCityCount = cityCount;
                answer = i + 1;
            }
        }
        return answer;
    }
by Expert (46,090 points)
0 like 0 dislike

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]

 

image
image
image
image

by Expert (46,090 points)