Google Interview Question
Software Engineer in TestsGood one.
Logic is : he is trying to find out the centre. So the arbitarily selcted node might be an inside node which has node distributed its both of the sides. Now using first bfs and selecting farthest element we are starting from a corner of the graph and now selecting farthest element from the corner which will give you diameter of graphs.
So finad diameter and the node which is diameter/2 distance away from node is the root node.
The definition of the diameter of a graph is the maximum distance between any two nodes of a graph. How can that be found out if we start at an arbitrary node and stop on finding the furthest node from the arbitrarily chosen node?
As above comment, the part starting at arbitrary node and find the length is not clear. I will do BFS from a leaf. During the traversal, I will keep the records of the longest and the second longest distance to the leaves and the corresponding edges (direction) for every "branch node" (Node with degree > 2).
The graph is a tree since it has no cicles, so start at a random node and find the lowest leaf, then find the next lowest leaf. The path from the lowest leaf to the next lowest leaf has the root at the middle.
there's something wrong with the way you're finding the diameter of the graph... there's no known algorithm that can find the 2 furthest vertices in linear time.
Here comes the logic , doing bfs from the arbitrary node gurantees to give you one end of the diameter because , while doing bfs once you come to a node in diameter , now its similar to starting of bfs from a point in diameter , so whichever end it is farther from it will print that node it the end (and all other nodes will be nearer that it otherwise those would have become the diameter)
It is actually not so simple to prove that it will be on diameter but I think it is true.
a) you start already on diameter. Then the node most far away from you must be on diameter, otherwise diameter is wrong (further node from "diameter" and the latest further node found is longer than the diameter).
b) you are not already on diameter. There must be a path to diameter though (it is connected). So the minimum path you can get from diameter is diam/2. In case you can find something else that is not part of diameter (otherwise by a) you would end in diameter) is larger or equal, than diameter can be improved at least by +1 length.
Both cases lead to a conclusion, that you will find a node on a diameter.
meanwhile, i think this question is a little bit difficult for "SDE in tests", for SDE is a good question
Actually I was interviewed for SE in Test and the questions weren't any easier. And I got interviewed by both SEs and SETs. Yes, but they do ask you to extensively test the code that you write when you're interviewing for the SET position. Btw, SDET is a Microsoft thing. In Google it's SET.
Doesnt BFS or DFS have time complexity of O(N+E), where E=Nsquare for connected graphs(worst-case)?. Then net time complexity of this algo would be O(Nsquare)?
Let me know if i am correct on this...
the graph is connected and doesn't contain cycles. Thus the number E of edges is exactly V - 1.
//let u be any node in the graph
//consider 2 queues BFSQ and TreeQ
//I am trying to collect each node from graph in BFS way and enter each node in the tree in BFS way so that the height of the tree is minimized
the Algo
===========================================================================
BFSQ.enqueue(u)
while(BFSQ.isnotempty())
{
If we are given a tree and we have to find the maximum distance between any two point than also we can apply the same logic: we pick an arbitary point apply bfs/dfs to find the farthest point than we apply dfs/bfs on the farthest point and find the point farthest from it.But how to prove its correctness??
start from an arbitrarily node, do a bfs or dfs to find out the furtherest node, denote it as node a. O(n)
- songlj August 16, 2011start from node a, do a bfs or dfs again to find out the furtherest node from node a, get the length len. O(n)
then the least height of the tree is interget part of (len+1)/2, and the root node is node b which is (len+1)/2 from node a.
total time complexity is O(2n)=O(n)
correct me if sth wrong