## Google Interview Question for Software Developers

Country: United States

Comment hidden because of low score. Click to expand.
5
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.

Comment hidden because of low score. Click to expand.
1
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.

Comment hidden because of low score. Click to expand.
0
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 en.wikipedia.org/wiki/Multigraph.
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.

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

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

Comment hidden because of low score. Click to expand.
0
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.

Comment hidden because of low score. Click to expand.
0
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

Comment hidden because of low score. Click to expand.
0
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)
{

}

private int minCostHelper(List<Edge>[] adj, int w, int s, int e){
Map<Integer,Integer> lookUp = new HashMap<Integer,Integer>();
lookUp.put(s,0);
int minCost = Integer.MAX_VALUE;
while(!q.isEmpty()){
boolean hasDirect = false;
Integer top = q.pollFirst();
int initial = lookUp.get(top);
int cost;
cost = initial + vtx.cost;
if(!lookUp.containsKey(vtx.vtx) || cost < lookUp.get(vtx.vtx)){
if(!lookUp.containsKey(vtx.vtx)){
}

lookUp.put(vtx.vtx,cost);

}
if(vtx.vtx == e){
hasDirect = true;
}
}
if(!hasDirect){
cost = initial + w;
if(!lookUp.containsKey(e) || cost < lookUp.get(e)){
lookUp.put(e,cost);
}
}
}
return lookUp.get(e);
}
}``````

Comment hidden because of low score. Click to expand.
0
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
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.
*/

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

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

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()
{
Graph g;

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'
*/
}``````

Comment hidden because of low score. Click to expand.
0
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:
self.edges[i].append(-j)
for i in self.nodes:
for j in self.nodes:
self.distances[(i,j)] = 2

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)

print g.dijkstra(1, 4)``````

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.

### 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.