is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.
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.
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.
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.
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.
- mijmarq July 24, 2012Since 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.