On my interview for an internship, I was asked following question: On a whiteboa

Question

On my interview for an internship, I was asked following question:

On a whiteboard write the simplest algorithm with use of recursion which would take a root of a so called binary tree (so called because it is not strictly speaking binary tree) and make every child in this tree connected with its sibling.

So if I have:

then the sibling to 2 would be 3, to four five, to five six and to seven eight.

I didn't do this, although I was heading in the right direction. Later (next day) at home I did it, but with the use of a debugger. It took me better part of two hours and 50 lines of code. I personally think that this was very difficult question, almost impossible to do correctly on a whiteboard.

How would you solve it on a whiteboard? How to apprehend this question without using a debugger?

Explanation / Answer

This is I believe the cleanes solution to your problem:

typedef std::map<int,std::vector<Node*>> tree;

void load_tree(int level, Node* node, tree& nodes)
{
if (node)
{
nodes[level].push_back(node);
load_tree(++level,node->l_,nodes);
load_tree(level,node->r_,nodes);
}
}

unsigned tree_height(Node* root)
{
if (!root)
{
return 0;
}
else
{
return 1 + max(tree_height(root->l_),tree_height(root->r_));
}
}

void connect_siblings(tree& nodes,unsigned counter)
{
for (unsigned i = 0; i < counter; ++i)
{
for (auto beg = nodes[i].begin(),end = nodes[i].end(), sibling = beg; beg != end; ++beg)
{
sibling = (beg + 1);
if (sibling != end)
{
(*beg)->s_ = *sibling;
}
}
}
}
In my opinion this question is waaay too hard for someone who applies for an internship position. It requires too much coding. This is not a quesition for a whiteboard.
I believe that either people who were interviewing you didn't really realized the complexity of it or you were given the question with the aim that you won't be able to answer it (read: they already found a person for the position they wanted to fill and you were just being given curtesy of being interviewed).
Anyway, don't fill bad about not being able to answer to it. Most so called professionals (as glaringly proved here) wouldn't be able to do it either. Not on a whiteboard and not within an hour.
Good luck in your future interviews!

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.