Question

Atlassian | OA | SDE1 | Coding Questions and Solutions | 2022 | Set-20

Answer 1

 

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;
  }
}

Answer 2

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;
}

Answer 3

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;
    }

Answer 4

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]