Facebook Interview Question Software Engineer / Developers
LOL. Simple huh?
Minimum spanning tree is obviously wrong. (Try thinking about what you write, once in a while).
Consider the following input:
f_d 0
toilet 1.0
bedroom 0.0
kitchen 0.0
f_d toilet 2
f_d kitchen 2
f_d bedroom 1
bedroom toilet 1.5
kitchen toilet 1
If we take minimum spanning tree, expected time is 2.5, but the optimal is 2.
Also to original poster,
there could be more than n! possibilities. What prevents multiple trips to the front door? You can visit the same location twice, if that gives easy access to other locations, no?
Interesting problem, seems like dynamic programming might work here, but have to think about it...
He He my mistake. Agreed LOLer. Loved the statement **(Try thinking about what you write, once in a while).** :D . Actually I thought - but wrongly.
Min span tree still works - come to think about it - in case any vertex with p=0 is removed, unless there is a connectivity issue in the graph.
[Also I said *should*. I never said - "It did". :(
But yes - u do have a point. I should have said "MAY".]
Can you please add the constraint - and give me another example?
This time me, Sidious,Padme and Yoda all sat together and thought about it. No kidding :(
Looks like the issue is:
1. "All the vertex with non zero probability we need to traverse".
2. "Also minimize the path weight"
Hence -
"Find a path with minimal weight so that it goes through the vertex which are having non zero probability"
@LOLer -->Is the above a proper formulation?
Sorry for being a dumb :( for the 1st time.
In case that is the formulation - then
"Find shortest path connecting all vertices reachable from a single point" is the same formulation.
The above one - implies
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
In case those kind of node exists - we would 1. Either remove them to create a pass-through path.
2. In case a path through them is more economical than a direct connection we would keep them.
Note: Original Problem did not tell anything about 0 probability.
This should do the trick.
http://mathworld.wolfram.com/ChinesePostmanProblem.html
**A problem asking for the shortest tour of a graph which visits each edge at least once (Kwan 1962; Skiena 1990, p. 194).**
http://www.uclic.ucl.ac.uk/harold/cpp/CPP.java
[Whops - a days end]
[Was not simple to find even.]
And why would this work? Why do you even have to visit each edge? The example I gave in counterexample to your MST still disproves that this won't work.
That should read ...also proves that this won't work...
instead of "still disproves...".
Nops.
LOLer - did you read the comment?
Note: Original Problem did not tell anything about 0 probability.
In case those kind of node exists - we would 1. Either remove them to create a pass-through path.
2. In case a path through them is more economical than a direct connection we would keep them.
That does not change the problem.
In case you still disagree - I need to find the guy who gave the puzzle and get a communication out of him.
Thanks.
Even if you do that and it is correct, so what? What are you arguing for? The all edges version? The all edges solution is incorrect, even if we disallow 0 probability. I will leave it to you to figure that out.
The puzzle is on the facebook website, you can email them and ask them for clarification...
This is what I feels
1. Starts from first node
2. Its a complete graph
lets say we have solution for 2 nodes
We can find out quickly which node to start in case of 2 nodes
Now adding a third node means only including it in any of the 3 positions
3-2-1 or 2-3-1 or 2-1-3.
Earlier order need not be affected because it is already optimal and new addition wont change the order as the tree is complete
I guess we can keep on adding new nodes
n*n*n maximum ........
I would rephrase the problem this way:
Given a graph (V,E) where V = the set of all vertices and E = the set of all edges between them.
To each edge E(v1,v2) assign weight = P(v2) * t(v1->v2).
Now, given a starting vertex V, produce a traversal order of the graph such that the vertices with non-zero probability are visited at least once and the weight of the traversal is minimized.
Isn't it a general case of TSP? (If assign same probability for every node). NP-Complete therefore? Did I miss anything here?
Two tricks I will do:
1. Use some heuristic function to get near minimal at the beginning.
2. Run "All pairs short path" at the beginning and store the result. So calculating cost for every possible permutation might be improved.
The problem can be simplify as finding a walk of the Graph, that traverse all the nodes while minimize the sum of di*pi, where pi is the possibility and di is the distance of the walk from the source.
I do not think it is a P complete problem as it is even more complicate than the mail man problem, which, as far as I can remember, is a NP-complete issue.
The probem of finding the minimum cost k intermediate nodes between source s and destination d can be solved with following
DP formulation
V(k) = Min( V(k-1) + P(k)*DkDk-1)
This simply means if there is path with k-1 length then the path of k length for any given node exists provided there is path
from that node to end node of k-1 path. Also taking the min cost for k intermediate node to get optimal path.
Now the problem remains is what to choose for source s and destination d. We dont know !
so apply above algorithm for each possible s and d
for(i = n0; i < nn; i++)
for(j = i+1; j < nn; j++ ) //to avoid duplicates like ij, ji start from j=i+1
V(k) = Min( V(k-1) + P(k)*DkDk-1)
Simple.
- Lord Darth Plagueis June 19, 2009Find minimal spanning tree for the graph. Then check the expected time. This should do the trick.