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

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

Answer 1

#include <bits/stdc++.h>
using namespace std;

vector<pair<int,int>> adj[105];

int dijkstra(int src, int n, int distanceThreshold)
{
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
    vector<int> distance(n + 1, INT_MAX);
    
    distance[src] = 0;
    pq.push({0,src});
    
    while(! pq.empty())
    {
        int prev = pq.top().second;
        int prevDist = pq.top().first;
        pq.pop();
        
        for(auto it : adj[prev])
        {
            int next = it.first;
            int nextDist = it.second;
            if(distance[next] > distance[prev] + nextDist)
            {
                distance[next] = distance[prev] + nextDist;
                pq.push({distance[next], next});
            }
        }
    }
    
    int cnt = 0;
    for(int i=1;i<=n;i++)
    {
        if(i != src && distance[i] <= distanceThreshold)
            cnt++;
    }
    
    return cnt;
    
}

int findTheCity(int n, int distanceThreshold) {
    
    // for(int i=0;i<edges.size();i++)
    // {
    //     int u = edges[i][0], v = edges[i][1], w = edges[i][2];   
    //     adj[u].push_back({v,w});
    //     adj[v].push_back({u,w});
    // }
     int ans=-1,mn=INT_MAX;
        
        //Finding the node which has minimum neigbhours
        for(int i=1;i<=n;i++){
            int res=dijkstra(i,n,distanceThreshold);
            if(res<=mn){
                mn=res;
                ans=i;
            }
        }
        return ans;
 }

int main(){
    int dt;
    cin>>dt;
    int n,m;
    cin>>n>>m;
    
    for(int i=1;i<=m;i++){
        int x,y,w;
        cin>>x>>y>>w;
        adj[x].push_back({y,w});
        adj[y].push_back({x,w});
    }
    
    cout<<findTheCity(n,dt);
    return 0;
}

Comments

perfect solution with code

---

@error_44, Hi, Thanks for this code, this works for general test cases. But I am not sure what constraints were given in actual question. Like complexity of this code is  nmlog(n), thus if n and m both can reach upto 10^5, then this might give TLE. Can you please share some more optimized approach if possible?

Thanks

Answer 2

Images of ques