Microsoft Interview Question
Software EngineersTeam: bing
Country: United States
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <stdio.h>
#include <queue>
using namespace std;
const int INF = 100000;
void print_adj (int** adj) {
//Print adj
for (int i=0;i<sizeof(adj)-1;i++) {
for (int k=0;k<sizeof(adj)-1;k++) {
cout<<adj[i][k]<<" ";
}
cout<<endl;
}
}
void _recurse (int** adj, int** augmented_adj, int ref, int cur, int dist, int* visited) {
if (visited[cur]==1) return;
visited[cur] = 1;
augmented_adj[ref][cur] = dist;
for (int k=0; k<sizeof(adj)-1;k++) { //loop on neighbors
if (adj[cur][k] != -1) {
_recurse (adj, augmented_adj, ref, k, dist+adj[cur][k], visited);
}
}
}
int** compute_all_distances (int** adj) {
int** augmented_adj = new int* [sizeof(adj)];
for (int k=0;k<sizeof(adj);k++) {
augmented_adj[k] = new int [sizeof(adj)];
for (int j=0; j<sizeof(adj);j++) augmented_adj[k][j] = adj[k][j];
}
for (int i=0;i<sizeof(adj)-1; i++) { //Loop on all cities
int* visited = new int [sizeof(adj)];
for (int k=0;k<sizeof(adj);k++) visited[k] = 0;
_recurse (adj, augmented_adj, i, i, 0, visited);
//Free memory
delete [] visited;
}
return augmented_adj;
}
void update_distances (int** adj, int** augmented_adj, int city1, int city2, int dist) {
int old_dist = augmented_adj[city1][city2];
//Separate nodes into 2 clusters
vector<int> cluster1, cluster2;
queue<int> q;
q.push (city1);
vector<int> visited (sizeof(adj), 0);
while (!q.empty()) {
int front = q.front();
q.pop();
if (visited[front]) continue;
visited[front] = 1;
cluster1.push_back(front);
for (int k=0;k<sizeof(adj)-1; k++) {
if (adj[front][k]!=-1 && front!=k && k!=city2) {
q.push(k);
}
}
}
visited.clear();
visited.resize(sizeof(adj), 0);
q.push(city2);
while (!q.empty()) {
int front = q.front();
q.pop();
if (visited[front]) continue;
visited[front] = 1;
cluster2.push_back(front);
for (int k=0;k<sizeof(adj)-1; k++) {
if (adj[front][k]!=-1 && front!=k && k!=city1) {
q.push(k);
}
}
}
//Update on clusters
for (int i=0;i<cluster1.size();i++) {
for (int j=0;j<cluster2.size();j++) {
int node1 = cluster1[i];
int node2 = cluster2[j];
augmented_adj[node1][node2] = augmented_adj [node2][node1] = augmented_adj[node1][node2] + dist - old_dist;
}
}
}
int calculate_metric (int** adj) {
int tot = 0;
for (int i=0;i<sizeof(adj)-1;i++) {
for (int j=0;j<sizeof(adj)-1;j++) {
tot += adj[i][j];
}
}
return tot/2;
}
int main () {
freopen ("in.txt", "r", stdin);
int cities, queries;
cin>>cities>>queries;
int** adj = new int* [cities+1];
for (int k=0;k<=cities;k++) {
adj[k] = new int[cities+1];
for (int j=0;j<=cities;j++) adj[k][j] = -1;
}
for (int k=0;k<cities-1;k++) {
int city1, city2, dist;
cin>>city1>>city2>>dist;
city1--; city2--;
adj[city1][city2] = adj[city2][city1] = dist;
// printf ("dist between %d & %d = %d\n", city1, city2, dist);
}
int** augmented_adj = compute_all_distances (adj);
// print_adj (augmented_adj);
for (int k=0;k<queries;k++) {
string s;
cin>>s;
if (s=="EDIT") {
int city1, city2, dist;
cin>>city1>>city2>>dist;
city1--; city2--;
update_distances (adj, augmented_adj, city1, city2, dist);
}
else {
// print_adj(augmented_adj);
cout<<calculate_metric(augmented_adj)<<endl;
}
}
return 0;
}
#include <iostream>
#include <set>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <stdio.h>
#include <queue>
using namespace std;
const int INF = 100000;
void print_adj (int** adj) {
//Print adj
for (int i=0;i<sizeof(adj)-1;i++) {
for (int k=0;k<sizeof(adj)-1;k++) {
cout<<adj[i][k]<<" ";
}
cout<<endl;
}
}
void _recurse (int** adj, int** augmented_adj, int ref, int cur, int dist, int* visited) {
if (visited[cur]==1) return;
visited[cur] = 1;
augmented_adj[ref][cur] = dist;
for (int k=0; k<sizeof(adj)-1;k++) { //loop on neighbors
if (adj[cur][k] != -1) {
_recurse (adj, augmented_adj, ref, k, dist+adj[cur][k], visited);
}
}
}
int** compute_all_distances (int** adj) {
int** augmented_adj = new int* [sizeof(adj)];
for (int k=0;k<sizeof(adj);k++) {
augmented_adj[k] = new int [sizeof(adj)];
for (int j=0; j<sizeof(adj);j++) augmented_adj[k][j] = adj[k][j];
}
for (int i=0;i<sizeof(adj)-1; i++) { //Loop on all cities
int* visited = new int [sizeof(adj)];
for (int k=0;k<sizeof(adj);k++) visited[k] = 0;
_recurse (adj, augmented_adj, i, i, 0, visited);
//Free memory
delete [] visited;
}
return augmented_adj;
}
void update_distances (int** adj, int** augmented_adj, int city1, int city2, int dist) {
int old_dist = augmented_adj[city1][city2];
//Separate nodes into 2 clusters
vector<int> cluster1, cluster2;
queue<int> q;
q.push (city1);
vector<int> visited (sizeof(adj), 0);
while (!q.empty()) {
int front = q.front();
q.pop();
if (visited[front]) continue;
visited[front] = 1;
cluster1.push_back(front);
for (int k=0;k<sizeof(adj)-1; k++) {
if (adj[front][k]!=-1 && front!=k && k!=city2) {
q.push(k);
}
}
}
visited.clear();
visited.resize(sizeof(adj), 0);
q.push(city2);
while (!q.empty()) {
int front = q.front();
q.pop();
if (visited[front]) continue;
visited[front] = 1;
cluster2.push_back(front);
for (int k=0;k<sizeof(adj)-1; k++) {
if (adj[front][k]!=-1 && front!=k && k!=city1) {
q.push(k);
}
}
}
//Update on clusters
for (int i=0;i<cluster1.size();i++) {
for (int j=0;j<cluster2.size();j++) {
int node1 = cluster1[i];
int node2 = cluster2[j];
augmented_adj[node1][node2] = augmented_adj [node2][node1] = augmented_adj[node1][node2] + dist - old_dist;
}
}
}
int calculate_metric (int** adj) {
int tot = 0;
for (int i=0;i<sizeof(adj)-1;i++) {
for (int j=0;j<sizeof(adj)-1;j++) {
tot += adj[i][j];
}
}
return tot/2;
}
int main () {
freopen ("in.txt", "r", stdin);
int cities, queries;
cin>>cities>>queries;
int** adj = new int* [cities+1];
for (int k=0;k<=cities;k++) {
adj[k] = new int[cities+1];
for (int j=0;j<=cities;j++) adj[k][j] = -1;
}
for (int k=0;k<cities-1;k++) {
int city1, city2, dist;
cin>>city1>>city2>>dist;
city1--; city2--;
adj[city1][city2] = adj[city2][city1] = dist;
// printf ("dist between %d & %d = %d\n", city1, city2, dist);
}
int** augmented_adj = compute_all_distances (adj);
// print_adj (augmented_adj);
for (int k=0;k<queries;k++) {
string s;
cin>>s;
if (s=="EDIT") {
int city1, city2, dist;
cin>>city1>>city2>>dist;
city1--; city2--;
update_distances (adj, augmented_adj, city1, city2, dist);
}
else {
// print_adj(augmented_adj);
cout<<calculate_metric(augmented_adj)<<endl;
}
}
return 0;
}
This can be solved by DFS+Memo.
- qingqingmm October 10, 2015