Interview Question for Developer Program Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
0
of 0 vote

The question makes no sense. Height of every node is minimum? What does that even mean? And balanced? Why talk about it?

Do you mean the average height (or perhaps you meant depth?) is minimum?

"Normally" we don't talk about the height of internal nodes...

- Anonymous July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Edit:
Yes it is Height of root to be minimized.

- Yoda July 25, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Find out the centre of graph :P

- xxx July 24, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- mijmarq July 24, 2012 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

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.

Learn More

Resume Review

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.

Learn More

Mock Interviews

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.

Learn More