Interview Question
Developer Program EngineersCountry: United States
Interview Type: In-Person
Walk through the nodes, finding the shortest path to all other nodes. Store the longest of these as the value of that node. Whichever node has the lowest value, will create the most balanced tree as the new root node.
Since the graph is not directed, this can be done in O(n^2*T) time, since distance between nodes is symmetric, where T is the time needed to find shortest paths from a single node. So, first node needs to visit (n-1) nodes to find it's longest path, the second needs to visit (n-2), etc. Total time n(n+1)/2 * T. Now, finding the shortest paths to each node also takes time (T), using a simple implementation of Dijkstra's algorithm gives us T=O(n^2) time as the traversal time per node, so the total time is O(n^4) .
I will note that you could build a new red-black tree a lot faster than this, but you would loose the information contained in the edges, which is preserved in the above approach. Therefor, adding all nodes to a new red-clack tree is probably not appropriate, but in the case that the edges are not important, it would save a lot of time.
The question makes no sense. Height of every node is minimum? What does that even mean? And balanced? Why talk about it?
- Anonymous July 24, 2012Do you mean the average height (or perhaps you meant depth?) is minimum?
"Normally" we don't talk about the height of internal nodes...