Interview Question
Program ManagersCountry: United States
@sri The complexities are O(n^2). Temporally this can be explained as we can solve the problem by traversing the matrix, even if you can do it by traversing just half of it. Spatially is easy to see using the worst case in which there is no preexisting connection between the cities. In that case you would need to generate n-1 + n-2 ..... + 1 connections which has a quadratic cost. Basically the question is asking you to generate a clique, you can research the topic to get a deeper understanding.
Solution in Python:
def RoadBuilder(nCities, builtRoads):
solutions = set()
m = [ [0] * nCities for _ in xrange(nCities) ]
for x,y in builtRoads:
m[x][y] = 1
m[y][x] = 1
for x in xrange(nCities):
for y in xrange(x+1, nCities):
if m[x][y] == 0:
solutions.add((x, y))
return solutions
#include <iostream>
using namespace std;
#include <vector>
vector<pair<int, int> > build_roads(int n, vector<pair<int, int> > in) {
vector<vector<int> > matrix(n, vector<int>(n));
for(vector<pair<int, int> >::iterator it = in.begin(); it != in.end(); ++it) {
// check wheth the it->first and it->second within the limits
matrix[it->first][it->second] = 1;
}
vector<pair<int, int> > out;
for(int i =0; i < n; i++) {
for(int j=i+1; j<n; j++) {
if (!matrix[i][j]) {
out.push_back(pair<int,int>(i,j));
}
}
}
return out;
}
int main() {
// your code goes here
int ara[][2] = {{0,1}, {1,2}, {2,3}};
vector<pair<int, int> > in;
for(int k = 0; k < sizeof(ara)/sizeof(ara[0]); k++) {
in.push_back(pair<int, int>(ara[k][0], ara[k][1]));
}
vector<pair<int, int> > result = build_roads(4, in);
for(vector<pair<int, int> >::iterator it = result.begin(); it != result.end(); ++it) {
cout << "{" << it->first<<"," <<it->second<<"}\n";
}
return 0;
}
create the adjacency matrix from the given pairs, build all possible pairs (unidirectional) and add to result if no edge is present. In Java
- Chris May 23, 2017