Facebook Interview Question for Software Engineer / Developers


Country: United States
Interview Type: In-Person




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

find all paths from source to destination, sort them and store.
remove one edge, go through the stored paths and find the first which doesn't contain the removed edge

- Anonymous April 22, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

There could be an exponential number of paths, so this would not be fast. Finding all *independent* paths isn't right either, because the new shortest path to a destination need not be independent of the original shortest path; it needs to simply not contain 1 edge.

- eugene.yarovoi April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Can you talk a little more about it? If the graph has cycles. It maybe runs forever to find all paths from source to destination.

- Anonymous October 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

I saw this problem "Going Office" on Interviewstreet.
PS - This is not my solution. Credit goes to Richard Kempe

The main idea behind the problem is simple: given a weighted undirected graph G=(V,E) and two nodes s,t∈V, we wish to answer Q queries of the following form:

What is the shortest path from s to t given that edge e∈E is removed from the graph?
(This type of problem is also known as the "most vital arc" problem )
Let N=|V| and M=|E| as usual. In this case, we are guaranteed that N,M,Q≤200000.

Prerequisites
You should definitely know Dijkstra's algorithm before attempting to solve this problem. Also, knowing about segment trees with lazy propagation would be good, but is not required to understand the solution.

Building Bridges
First of all, it should be clear that naively running Dijkstra's isn't going to run in time, because it requires O(QNlogN) operations. In fact, the size of the input suggests that we should look for at worst an O(NlogN) solution. What can we do then? We may first try to solve an easier problem: can we determine whether an edge e, when removed, will increase the shortest path length between s and t?

Definitions:
An edge is optimal if it is on a shortest path from s to t.
An edge is a bridge* if it is on all shortest paths from s to t. (Here we refer only to shortest paths in G, without having removed any edges.)
Let ds(u) (resp. dt(u)) be the shortest-path distance from s (resp. t) to u, and let OPT be the shortest-path distance from s to t. Then we can show the following properties:

Lemmata:
e=(u,v) is optimal if and only ds(u)+length(e)+dt(v)=OPT.
e=(u,v) is a bridge if and only if it is optimal and for all other optimal e′=(u′,v′), we have either ds(v′)≤ds(u) or ds(v)≤ds(u′). In other words, when we travel along an optimal path from s to t, then between lengths ds(u) and ds(v), we must be traveling along e. By convention we denote a bridge with the letter b.
As a corollary of the above statement, e is a bridge if and only if, when removed from G, the shortest path distance from s to t increases.
(Proofs are left to the reader.) These properties should give you some idea of how to find all the bridges in G. If you still need some hints, an algorithm for computing bridges is included at the end of this post.
Islands
Now we have a way of identifying which edges, when removed, affect the shortest path length. This still leaves one major question unanswered: given a bridge b, how exactly do we determine the shortest path length from s to t once b is removed? Running Dijkstra's repeatedly is too slow, since we can easily construct examples in which every edge is a bridge. (Consider a graph consisting of only a path from s to t.)

Let K denote the number of bridges. Note that Lemma 2 above implies that we can uniquely order the bridges b0,b1,…,bK−1 based on their relative distances from s. Could we use this to help us?

Definition: Let the i-th island be defined as the set of all vertices v, such that there exists a shortest path from s to v using no more than i bridges. (If v is not connected to either s or t, then we can ignore it -- it lies on some strange continent somewhere far away.)
The intuition behind islands and bridges is this: bridges are the fastest way to "travel" between the islands when going from s to t. If we remove an edge that is not a bridge, our shortest path is not affected. However, when we take out a bridge, we are forced to travel along another (possibly much longer) path.
Proposition: Consider the bridge bi, connecting the i-th and i+1-st islands. Let Ei be the set of all edges e connecting an island with index ≤i to an island with index >i. Then the shortest path from s to t that bypasses bi must have length
mine=(u,v)∈Ei{ds(u)+length(e)+dt(v)}
Proof: Any path P from s to t bypassing bi must include some edge in Ei. Now consider some edge e=(u,v)∈Ei -- the shortest path from s to t that goes through e must have length ds(u)+length(e)+dt(v). Lastly, by the way we have constructed the islands, we know that bi is not on the shortest paths from s to u or from v to t.
A Data Structure for Bypass Length
Let bypass(i) denote the length of the shortest path that bypasses bi. The above observations suggest that we can run the following algorithm to compute bypass(i):

For each non-bridge edge e=(u,v) connecting islands i and j, where i<j:
For each k∈{i,i+1,…,j−1}:
bypass(k)←min{bypass(k),ds(u)+length(e)+dt(v)}
However, there is a slight problem with this algorithm: it's too slow. Through some tricky analysis, you can show that in the worst case, we can construct a graph that will cause the above subroutine to take O(M3/2) operations.
What we need is a data structure that supports the following two operations efficiently:

update(i,j,val), which runs bypass(k)←min{bypass(k),val} for all k∈{i,i+1,…,j−1}
query(i), which returns bypass(i)
One possible data structure that can support both operations in O(logK) time is called a segment tree with lazy propagation or a segment tree with range update. There are several tutorials online about this type of tree, and it's a good data structure to be familiar with. (The main problem right now is that the structure is rather complicated and the online tutorials are not very good. I may do an article on it some time, if there is sufficient demand.)


Putting It All Together
The previous observations suggest the following algorithm for solving the problem:

Compute ds and dt using Dijkstra's algorithm.
Find the bridges:
First find all the optimal edges by iterating over all edges e=(u,v), and storing the edges such that ds(u)+length(e)+dt(v)=OPT.
Sort all the optimal edges by ds(u) and ds(v). Use the criterion from above to find the bridges.
Find the islands.
One way (the hard way) is to run a modified version of Dijkstra.
A smarter and shorter alternative is to just run multiple depth-first searches from s and from the far end of each bridge. It's up to the reader to figure out how to do so.
Find the bypassing paths.
Initialise your favourite range-update data structure.
Iterate over all the non-bridge edges. If e=(u,v) is an edge crossing from island i to island j>i, then range-update bypass(i),bypass(i+1),…,bypass(j−1) such that they are no more than ds(u)+length(e)+dt(v).
Process all the queries. If the edge in question is not a bridge, then we simply return the optimal length. Otherwise, we query the range-update data structure to find the best bypass length.
All of the above steps run in require O(RlogR) operations where R=max{N,M,Q}, so the algorithm has complexity O(RlogR).

- sajaljain4 August 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

There are many ambiguities in that definition of the problem. First of all is the graph weighted or unweighted? If graph is weighted all you need to do to avoid considering some edge is mark it somehow and then skip it during traversal. Dijkstra with binary heap would give you O(n lg n). Simple solution, something must be missing.

- Dim April 23, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

I'm guessing he wants to find ALL of the paths in something like O(NlogN).

- eugene.yarovoi April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

One small update.
There is only one path from one city to another.

- ediston April 20, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Is it required to do n lgn?

- Yu April 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not necessary

- ediston April 22, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Wait...what? If there's only 1 path, and you remove one of the edges on it, won't that mean there now definitely won't be any paths.

- eugene.yarovoi April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

is that mean the graph is in fact a tree?

- lambda2fei August 02, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

that's an important update. Now you have only one shortest path between source and destination which will get destroyed if you remove an edge from that path. Since it is a tree, you can have at most (n-1) edges which can be the longest path. Then Complexity is O(n).

- danielhasegan October 26, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

?
Guys the graph is weighted .. and we cannot sort and store all pahts as the number of paths could be 10^22.

- ediston April 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

You should clarify the problem more. What did you mean when you said there's only one path between any two cities? If that's true, it sufficies to check whether the deleted edge is on the only path, and depending on that, the shortest path will either be the path you had before or will not exist.

- eugene.yarovoi April 24, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

If there is only one path between any two cities, there are cycles in the graph. It's a minimum spanning tree. Can you revisit the problem and clear the ambiguities.

- Anonymous May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

read "cycles" as "no cycles"

- Anonymous May 15, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Sounds like the edges are weighted (representing the distance), such as e1 = (v1,v2,d) and there exists at most 1 edge between any two nodes? Then a weighted shortest path algorithm helps...but do we want to execute it fully n times, once for each round, for the entire graph?

Suppose on round 1, some edge e1 = (v1,v2,d) is missing and the shortest path is computed from the start to end node. but we could also compute the shortest path from
the start node to every node and save those paths (or at least the cost).

Then on round 2, e1 is placed back in and another edge, e2 = (v3,v4,d) is removed. If e2 is on the shortest path in round 1, then the solution for round 1 no longer holds, otherwise the solution from round 1 -may- still hold.

By placing e1, is e1 now on the new shortest path...seems like we could focus on the cost of the path from (a) the start node to v1, (b) cost of e1, (c) the cost of v2 to the end node. (a) and (b) are already known, so we compute (c), add them together to get the cost of the new path containing e1.

So maybe something along these lines, where shortest path is recomputed, not for the whole graph, but from the vertices of the two changed edges.

- Anonymous June 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

sounds like interviewstreet problem Going Office.

- Abhishek July 16, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Suppose we have run the Dijkstra algorithm on original graph: g0;
We have got the shortest distance array dist0[n].

Now, we have a new graph: g with the edge (w, v) removed;

dist0[n] and dist[n] are two global arrays, which store the shortest distance array from source of the original and removed edge graph.

Algorithm should be as followed;

void shortest(int s, int t) // s source, t destination
{
// 1. initialize
// copy dist0[n] to dist[n]// dist[n] is the array storing the new shortest distance;
for (int v = 0; v < n; v++)
{
dist[v] = dist0[v];
}

// 2. compare dist0[v] - dist0[w] and weight(w, v), if weight(w, v) == dist0[v] - dist0[w], we need // to update dist[v];
if (dist0[v] - dist0[w] == weight(w, v))
{
dist[v] = 10000000;
for ( j in adjR[v] ) // adjR is the reversed graph adjacency list
dist[v] = min(shortest, dist[j] + weight(j, v));
} // new dijkstra greedy score dist[v] is the minimum score of all other vertices scores + edge weights;

// recursively update the dijkstra greedy score vertices connected to vertices v;
update(s, t, v);
}

// recursive program.
void update(int s, int t, int v)
{
int u;
for (u in adj[v])
{
if (dist0[u] - dist0[v] = weight(u, v))
{
dist[u] = dist[v] + weight(u, v);
update(s, t, v);
}
}

- Wangqing (Steve) Yuan July 19, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

my answer is, find the DAG with source 's' and destination 't' produced by dijkstra. if the removed edge is a cut in this DAG, then..I think you need to run dijkstra again... and if not, the shortest path is not changed.. I can't figure out better solutions..

- lambda2fei August 02, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find a shortest path. Then recursively find shortest path where you remove one node each from your first shortest path. You will end up with a set of shortest paths and regardless which node is removed in the graph you now you always have an alternative shortest path.

- FBNerd February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

One way could be to store the path lengths from source to dest in in a min heap. now whenever you remove the an egde , you check if the edge belongs to the shortest path(O)1) time). If yes then delete the egde, swap the shortest path with the path stored at the end of heap array, and heapify the array(excluding the swapped array). continue this process till you find a the shortest path which is not a part of removed edge.

This can work for the cases when edge is added back. Just figure out the path sums which were part of that edge , increase the size of heap array by 1 and heapify again to get the shortest path

- vivekh August 18, 2015 | 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