Interview Question Java Developers
Interview Type: In-Person
looks like an easy question, since your graph is COMPLETE.
1. If A<=B then go directly from node 0 to node (N-1), with a cost of at most A.
2. If A>B:
2.1. Find a shortest path P from node 0 to node (N-1) using only edges in the set "K edges of cost B", using BFS algorithm.
2.2 If cost of P < A, return path P, else go directly from node 0 to node N-1.
So, the question actually asks for BFS algorithm in un-weighted graph.
EDITED:
1. If A<=B: do the same as 2. for the set of cost A edges.
Hello, ninhnnsoc.
You missed a case, that's not an easy question. Think about the situation when A < B and you have a B-edge from node 0 to node N-1. In that case you can't go directly from 0 to N-1 and you'll have to do a BFS on the complementary graph (which is pretty huge).
you are correct, thanks!
So, we need to do a BFS on either A-edge set or B-edge set, depends on A<=B or B<=A, and compare the path found with the path going directly from 0 to N-1.
Haha, easy to make mistake then.
Hi ninhnnsoc.
If A<B, what you said is correct, but first of all note that we cannot store the edges with cost A, and second, during the interview, probably you'd need to prove that doing this would work, because we have O(n^2) edges with cost A and BFS is runs linear in number of edges. My initial intuition is that, when n grows, the length of the path becomes incredibly short; therefore, the algorithm would run in O(n) anyway. I cannot formally proof why it would work, though.
Hi iroodaz,
I found your intuition is correct.
The average path length in a random graph is Lp = ln(N), where N is the number of nodes.
If the graph/network is scale-free (such as internet, social networks, ...), the average path length is 'incredibly short": Lp = ln(N)/ ln ln(N).
You may ask google for: Agata+Fronczak+"Average path length in random networks" to see the proof, which I don't really digest all the maths :))
In this question, can I assume that the sub-graph with A-edge set (or B-edge set) is random? Or since its origin is COMPLETE, it may even be scale-free...
Thus, I can expect the length of the path is less than ln(N).
An other point is that, let k = B/A or A/B, I will never run BFS further than k steps, since after that the resulting path never be shorter than the direct path.
In short, the BFS in this problem is upper bounded by O(m.N), where m = min(k, ln(N))
Further more we can implement an 2-way BFS to further cut down unnecessary search.
P/S: I have another question: Is there any algorithm better than BFS to find a shortest path from u to v in an unweighted graph?
Thank you very much for the analysis ninhnnsoc, and also thanks for the paper on the average path length.
Hahaha, I could not digest the proof; however, the good news is, we can use what they proved :-D
I think, as you said, it is okay to assume the sub-graph is a random graph with p = ( (N^2) - E)/N^2 where E is the number of the edges with cost B. However, have got no idea if the graph is scale-free as I couldn't understand the definition in the Wikipedia article :-(
In addition, I totally agree with you on maximum step count; therefore, the O(m.N) upper bound seems correct. By the way, the 2-way BFS idea is great and maybe even necessary.
I'm not sure if there is a better algorithm than BFS for finding a shortest path, because at any node we probably have no information about our distance from the target node.
Thanks again for your research and analysis.
(this is a partial solution)
If C(i) is the cost of reaching the ith node from the 0th node, and D(x, y) is the cost of the edge between the xth and the yth node, the answer is C(n-1) and can be expressed as
C(n-1) = min { C(n-2) + D(n-2, n-1), C(n-3) + D(n-3, n-1), ..... C(1) + D(1, n-1), D(0, n-1) }I'm not sure how to compute a closed form expression when k edges have a cost of B.
- dr.house April 12, 2014