Google Interview Question for Software Developers

Country: United States

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

source: s, destination: t, extra vertex weight = wex
My algorithm would be:
1. Compute all-pair shortest path
2. For all vertices k do:
globalmin = min(globalmin, min(d[s,t], d[s,k]+wex, d[k,t]+wex) )

In the second step, wex must be equal to infinity whenever s<->k (directly connected) and k<->t.

- tahini October 15, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote

Simple Approach would be
1. Find the shortest path using dijkstra's algorithm
2. If cost of shortest less than the extra edge weight then use the dijkstra shortest path
3. Else create an edge between start and end node, and extra edge weight will be the cost.

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

Dumbo Strategy. Not smart but does the job.
Suppose the graph has K pair of nodes, which are not connected.
We are not considering
In that case we need to add to these pairs all pairs having edge length more than 2.
Now, the problem becomes :

find_min (  start, end,  [ original , modified_1, modified_2, ...modified_k ] )

That is, finding individual shortest path in the original graph, and then modifying the graph by joining the first pair and then continuing the same.

This surely solves the problem.
But let's take a look around this a bit more.
Suppose we do this :

find_min (  start, end,  [ original_graph ] )

and find the path P.
Now, if we go through the path verices by vertices, edge by edge,
can we not calculate if replacing 3 of the verices by a 2 ( by inserting the virtual edge )
reduces the min value or not?
Thus, we may solve the problem by :

1. Finding min path
2. Check if directly connecting start to end solves it or not? If not, then proceed to [2]
3. For each 3 verices in 2 edges, we check if adding a virtual edge reduces the min or not.
4. Continue storing the previous min and go to [3].

Proof Of Correctness: NONE.
As of now, this can go wrong drastically.

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

Why not just add extra edge between start and end node?

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

Here is the idea (assuming positive integer weights):
1) If there exists an edge between source and destination go to (2) else return 1;
2) Use normal dijkstra's algorithm to find minimum distances to all the vertices from source and destination.
3) From the source distance array, for every vertex v1 (except source and vertex) in source distance array, see if for every vertex v2 (except source)
distance_source(v1) + distance_destination(v2) + 1 < distance_source(destination) if v1,v2 is not edge. Update the minimum source-destination distance.
4) Repeat for destination vertex. ie From the destination distance array, for every vertex v1 (except source and vertex) in destination distance array, see if for every vertex v2 (except destination)
distance_destination(v1) + distance_source(v2) + 1 < distance_source(destination) if v1,v2 is not edge. Update the minimum source-destination distance.

The idea is to calculate minimum distances of vertices from source and destination and then see if by adding an edge of weight 1, can we reduce source-destination distance.

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

1) Find shortest path using Djikstra
2) If shortest path > extra edge weight, add extra edge between start and end node
3) Else do not add extra edge since shortest path < extra edge weight

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

	 * Using BFS compute the weight of the shortest path from the starting vtx(s) to the
	 * destination vtx(e). Use a HashMap to keep track of which verticies have already been visited
	 * and update the minimum cost of reaching each vertex from s. For each vtx removed from the queue (t) check if it  has a direct
	 * edge to e. If no direct edge exists, take the minimum cost of travelling to t(just do a lookup in the hash map) and add w to this value-
	 * this will be the minimum cost of going from t to e, update the hash map with the minimum cost
	 * of going to e from each vertex.
	 * Time: O(v + e) where v is the number of vertices and e is the number of edges.
	 * Space: O(v + e) due to hash map and bfs queue.
	private static class Edge
		int vtx;
		int cost;
	public int minCost(List<Edge>[] adj, int w,int s, int e)
		return minCostHelper(adj,w,s,e);
	private int minCostHelper(List<Edge>[] adj, int w, int s, int e){
		Map<Integer,Integer> lookUp = new HashMap<Integer,Integer>();
		Deque<Integer> q = new LinkedList<Integer>();
		int minCost = Integer.MAX_VALUE;
			boolean hasDirect = false;
			Integer top = q.pollFirst();
			int initial = lookUp.get(top);
			int cost;
			for(Edge vtx:adj[top]){
				cost = initial + vtx.cost;
				if(!lookUp.containsKey(vtx.vtx) || cost < lookUp.get(vtx.vtx)){
				if(vtx.vtx == e){
					hasDirect = true;
				cost = initial + w;
				if(!lookUp.containsKey(e) || cost < lookUp.get(e)){
		return lookUp.get(e);

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

   I solved it using dijkstra as in my previous post. I noticed how ever, the weight of the additional
   edge is not 0 but 2 and that you may go over an intermediate node since the node you currently are
   has a direct connection to end that is more expensive than when you would add the bonus-Edge to an 
   other node and go from there to the end.
   So, again, I noticed how important it is to verify the steps before coding and getting into depth or
   making wrong statements :-) The further I go with an error the more expensive to fix (in terms of 
   wasted time).

   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". Once used we are in g' and can't use the "bonus edge" anymore.
   That is, im g' there exist only the original edges to vertices in g but to their "mirror" in

   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

#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
	const int bonusVertexIdOffset = 100000;
	std::unordered_map<int, std::unordered_map<int, int>> edges_;
	std::unordered_set<int> vertices_;

	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;

	void addVertex(int vertexId) 
		if (vertexId >= bonusVertexIdOffset || vertexId >= bonusVertexIdOffset) throw "id out of range";

	// 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 =;

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

	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));
			// 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()
	Graph g;
	g.addEdge(1, 2, 2);
	g.addEdge(1, 4, 4);
	g.addEdge(2, 3, 1);
	g.addEdge(3, 4, 3);
	g.addEdge(4, 5, 1);
	g.addEdge(5, 6, 8);
	g.addEdge(3, 6, 9);
	g.addEdge(1, 6, 99);
	g.addEdge(2, 6, 99);

	printResult(1, 5, 2, g.getShortestPathWithBonusEdge(1, 5, 2));
	printResult(1, 4, 2, g.getShortestPathWithBonusEdge(1, 4, 2));
	printResult(1, 5, 50, g.getShortestPathWithBonusEdge(1, 5, 50));
	printResult(1, 6, 9, g.getShortestPathWithBonusEdge(1, 6, 9));
	printResult(1, 6, 7, g.getShortestPathWithBonusEdge(1, 6, 7));
	printResult(1, 20, 25, g.getShortestPathWithBonusEdge(1, 20, 25));

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

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

	shortes path from 1 to 5 with bonus edge weight 50 is
	weight: 5
	path: 1 4 5

	shortes path from 1 to 6 with bonus edge weight 9 is
	weight: 12
	path: 1 2 3 6

	shortes path from 1 to 6 with bonus edge weight 7 is
	weight: 11
	path: 1 4 6'

	shortes path from 1 to 20 with bonus edge weight 25 is
	weight: 25
	path: 1 20'

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

from collections import defaultdict
class Graph(object):
    def __init__(self, n):
        self.nodes = range(1, n+1)
        self.edges = defaultdict(list)
        self.distances = dict()
        for i in self.nodes:
            for j in self.nodes:
        for i in self.nodes:
            for j in self.nodes:
                self.distances[(i,j)] = 2
    def add_edge(self, u, v, dist):
        self.edges[u][v-1] = -1*self.edges[u][v-1]
        self.edges[v][u-1] = -1*self.edges[v][u-1]
        self.distances[(u, v)] = dist
        self.distances[(v, u)] = dist
    def dijkstra(self, start, end):
        unvisited = dict()
        for node in self.nodes:
            unvisited[node] = None
            unvisited[-node] = None
        visited = dict()
        cur = start 
        dist = 0
        unvisited[cur] = dist
        while unvisited:
            visited[cur] = unvisited[cur]
            del unvisited[cur]
            for nbor in self.edges[abs(cur)]:
                if cur < 0:
                    if nbor < 0: continue
                    else: nbor = -nbor
                if nbor in visited: continue
                new_dist = dist + self.distances[(abs(cur), abs(nbor))]
                if unvisited[nbor] == None \
                or unvisited[nbor] > new_dist:
                    unvisited[nbor] = new_dist
            if unvisited:
                candidates = [node for node in unvisited.items() if node[1]]
                candidates.sort(key=lambda k:k[1])
                cur, dist = candidates[0]
        return min(visited[end], visited[-end])
g = Graph(5)
g.add_edge(1, 2, 2)
g.add_edge(1, 4, 4)
g.add_edge(2, 3, 1)
g.add_edge(3, 4, 3)
g.add_edge(4, 5, 1)

print g.dijkstra(1, 4)

- Nitish Garg December 26, 2016 | Flag Reply

Add a Comment

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


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


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