Amazon Interview Question for Developer Program Engineers


Country: India
Interview Type: Written Test




Comment hidden because of low score. Click to expand.
2
of 2 vote

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.

#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <vector>
#include <iostream>

struct Edge
{
	int destId_, weight_;

	Edge(int destId, int weight) : destId_(destId), weight_(weight) { }	
};

struct TraversalItem
{
	int vertexId_, cost_, parentId_;
	TraversalItem(int vertexId, int cost, int parentId) 
		: vertexId_(vertexId), cost_(cost), parentId_(parentId) { }
	TraversalItem() : TraversalItem(-1, -1, -1) { }
};

using Path = std::pair<int, std::vector<std::pair<int, bool>>>;

class Graph
{
private:
	const int bonusVertexIdOffset = 100000;
	std::unordered_map<int, std::unordered_map<int, int>> edges_;
	std::unordered_set<int> vertices_;

public:
	void addEdge(int u, int v, int weight)
	{
		if (u >= bonusVertexIdOffset || v >= bonusVertexIdOffset) throw "id out of range";
		edges_[u][v] = weight;
		edges_[v][u] = weight;
		addVertex(u);
		addVertex(v);
	}

	void addVertex(int vertexId) 
	{ 
		if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";
		vertices_.insert(vertexId);
	}

	// main part of algorithm 
	// it returns the path cost and the visited vertice id's with a flag wether they were in g or g'
	Path getShortestPathWithBonusEdge(int start, int end, int bonusWeight)
	{
		auto tiComparer = [](const TraversalItem& a, const TraversalItem& b) -> bool { return a.cost_ > b.cost_; };
		std::priority_queue<TraversalItem, std::vector<TraversalItem>, decltype(tiComparer) > tqueue(tiComparer);
		std::unordered_map<int, TraversalItem> state;

		tqueue.push(TraversalItem(start, 0, -1)); // start with start
		state.emplace(std::pair<int, TraversalItem>(start, TraversalItem(start, 0, -1))); // start must be in state, too
		while (tqueue.size() > 0)
		{
			auto u = tqueue.top();
			tqueue.pop();

			int uId = u.vertexId_;
			if (uId == end || uId == end + bonusVertexIdOffset)
			{
				end = uId; // path end id, it might be in g'
				break; // if end is now the cheapest to reach: done
			}
			auto edges = getOutEdges(uId, bonusWeight);
			for (auto edge : edges)
			{
				int cost = u.cost_ + edge.weight_;
				int vId = edge.destId_;
				auto vStateIt = state.find(vId);
				if (vStateIt == state.end())
				{
					TraversalItem ti(vId, cost, uId);
					vStateIt = state.emplace(std::pair<int, TraversalItem>(vId, ti)).first;
					tqueue.push(ti); 
				}
				else if(vStateIt->second.cost_ > cost)
				{
					vStateIt->second.cost_ = cost;
					vStateIt->second.parentId_ = uId;
					tqueue.push(vStateIt->second); // since there's no update-key function... 
				}			
			}
		}

		// reconstruct path
		auto stateIt = state.find(end);
		if (stateIt != state.end())
		{
			// reached the end
			std::vector<std::pair<int, bool>> path;
			int vertexId = stateIt->second.vertexId_;
			int cost = stateIt->second.cost_;
			while (vertexId != -1)
			{
				bool gs = vertexId >= bonusVertexIdOffset;
				int vId = gs ? vertexId - bonusVertexIdOffset : vertexId;
				path.push_back(std::pair<int, bool>(vId, gs));
				vertexId = state[vertexId].parentId_;
			}
			return Path(cost, std::vector<std::pair<int, bool>>(path.rbegin(), path.rend()));
		}
		return Path(-1, std::vector<std::pair<int, bool>>()); // empty path
	}

private:
	std::vector<Edge> getOutEdges(int vertexId, int bonusEdgeWeight)
	{
		std::vector<Edge> edges;
		
		int u = vertexId;
		int vIdOffset = 0;
		if (u >= bonusVertexIdOffset)
		{
			u -= bonusVertexIdOffset;
			
			// bonusedge already used, so only original edges are possible
			auto edgeIt = edges_.find(u);
			if (edgeIt != edges_.end())
			{
				for (auto v : edgeIt->second)
				{
					// use orginial edge but stay in g'
					edges.push_back(Edge(v.first + bonusVertexIdOffset, v.second));
				}
			}
			return edges;
		}

		// a vertex that was reaches without bonus edge, so
		// every pair of edges is possible: either from the original 
		// graph or using the bonusEdge
		for (auto v : vertices_)
		{
			if (v == u) continue;
			auto edgeIt1 = edges_.find(u);
			if (edgeIt1 != edges_.end())
			{
				auto edgeIt2 = edgeIt1->second.find(v);
				if (edgeIt2 != edgeIt1->second.end())
				{
					// use original edge within g
					edges.push_back(Edge(v, edgeIt2->second));
					continue;
				}
			}
			// add bonus edge to g'
			edges.push_back(Edge(v + bonusVertexIdOffset, bonusEdgeWeight));
		}

		return edges;
	}
};

void printResult(int start, int end, int bonusWeight, const Path& path)
{
	std::cout << "shortes path from " << start << " to " << end 
		<< " with bonus edge weight " << bonusWeight << " is " << std::endl;
	std::cout << "  weight: " << path.first << std::endl;
	std::cout << "  path: ";
	for (auto v : path.second)
	{
		std::cout << v.first << (v.second ? "' " : " ");
	}
	std::cout << std::endl << std::endl;
}

int main()
{
	// sample 1
	Graph g1;
	g1.addEdge(1, 2, 2);
	g1.addEdge(2, 3, 1);
	g1.addEdge(2, 4, 2);
	g1.addEdge(3, 4, 3);
	printResult(1, 4, 5, g1.getShortestPathWithBonusEdge(1, 4, 5));

	Graph g2;
	g2.addEdge(1, 2, 2);
	g2.addEdge(1, 4, 4);
	g2.addEdge(2, 3, 1);
	g2.addEdge(3, 4, 3);
	g2.addEdge(4, 5, 1);
	printResult(1, 4, 2, g2.getShortestPathWithBonusEdge(1, 4, 2));

	/* Output
	shortes path from 1 to 4 with bonus edge weight 5 is
	weight: 4
	path: 1 2 4

	shortes path from 1 to 4 with bonus edge weight 2 is
	weight: 3
	path: 1 5' 4'
	*/
 }

- ChrisK October 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 vote

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)

- ChrisK October 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

could u please code this question in c language.Actually i dont know c++ much...@ ChrisZ

- zila.techy October 22, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

#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;
}

- Richa Tibrewal October 24, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More