Amazon Interview Question
Developer Program EngineersCountry: India
Interview Type: Written Test
I forgot to post the explanation of above algorithm:
The key idea is to dynamically extend the graph to a graph g'. When ever we are on a vertex in the original graph g, there are the edges given + to every other vertex where no edge was given there exists the "bonus edge" (with extra weight). Once used we are in g' and can't use the "bonus edge" anymore.That is, in g' there exist only the original edges to vertices in g but to their "mirror" in g'.
Visually, I drew the original graph g and on top a layer with the graph g'... Besides this I could use dijkstra. A vertex is identified with an integer in this solution. A vertex in g has an id below a certain value and a vertex in g' has just an offset to that id. There are certainly more apealing designs to that, but it did work and I could verify some basic cases.
Runtime is: Dijkstra but with V^2 edges. So O(E V * lg(V)) become O(V^3*lg(V)) ... not that sexy ... (E is the number of edges and V is the number of vertices)
#include<cstdio>
#include<vector>
#include<climits>
#define min(a,b) (a<b?a:b)
#define MAXLEN 100
using namespace std;
int find_min(int dist[],bool visited[],int n)
{
int i,mx,m;
mx = INT_MAX;
for(i=0;i<n;i++)
{
if(dist[i]<mx && !visited[i])
{
mx = dist[i];
m = i;
}
}
return m;
}
int find_res(int start,int target,int graph[][MAXLEN],int n)
{
int u,v,w,dist[MAXLEN],cnt,i,j;
bool visited[MAXLEN];
for(i=0;i<n;i++)
{
dist[i] = INT_MAX;
visited[i] = false;
}
dist[start] = 0;
for(cnt = 1;cnt<n;cnt++)
{
u = find_min(dist,visited,n);
visited[u] = true;
for(v=0;v<n;v++)
{
if(graph[u][v]!=-1 && !visited[v] && dist[u]+graph[u][v]<dist[v])
{
dist[v] = dist[u] + graph[u][v];
}
}
}
return dist[target];
}
int minCost(int node,vector<int> from,vector<int> to,vector<int> wt,int start,int target,int weight)
{
int res,graph[MAXLEN][MAXLEN],i,j;
start--;
target--;
for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
graph[i][j] = -1;
}
for(i=0;i<from.size();i++)
{
from[i]--;
to[i]--;
graph[from[i]][to[i]] = graph[to[i]][from[i]] = wt[i];
}
res = find_res(start,target,graph,node);
// printf("res = %d\n",res);
for(i=0;i<node;i++)
{
for(j=0;j<node;j++)
{
if(graph[i][j]==-1)
{
graph[i][j] = weight;
res = min(find_res(start,target,graph,node),res);
graph[i][j] = -1;
}
}
}
return res;
}
int main()
{
int node,edge,a,b,w,i,st,target;
vector<int> to,from,wt;
scanf("%d%d",&node,&edge);
for(i=0;i<edge;i++)
{
scanf("%d%d%d",&a,&b,&w);
to.push_back(a);
from.push_back(b);
wt.push_back(w);
}
scanf("%d%d%d",&st,&target,&w);
printf("%d\n",minCost(node,from,to,wt,st,target,w));
return 0;
}
I think the problem statement is not complete due to the missing information what w_extra should do. Since I noticed its a dublicate I already solved (id=5721708662095872) I explain the question as I interpreted it first:
you get the graph as described. you get the w_extra which is the weight of an edge you can place between any two vertices that have not already a direct connection (an edge connecting them). You can only place that extra edge once.
I checked the two sample and it was right:
1) Path is 1->2->4 with weight 4 and no extra edge used
2) Path is 1->5->4 with extra edge used from 1 to 5 (path weight is 2+1 = 3)
I skiped the coding of parsing ala topcoder contest and handcoded the two samples.
The code is long because it has some convenience stuff around it.
- Chris October 22, 2016