Microsoft on-site Coding Round

Round 1

Questions: Given cities n from 0 to N-1 in a doubly link manner, also given number of amenities m (0 to m-1 for each city). Also, given a matrix amenities of N x M where amenities [i][j] = 1 denotes amenity is present and 0 means amenity is not present. Distance between any two adjacent city is 1.

Find a city which has the smallest distance to access all amenities.

Example:

int n = 5, m = 3;
vector<vector<int>> inp = {
    {1, 0, 0},
    {0, 0, 0},
    {1, 1, 0},
    {0, 1, 0},
    {0, 0, 1}
};

ans = 3 // (city 3 has dist 2 to access all amenities)