Given a tree with potentially multiple child nodes, write an algorithm that describes how you would completely reverse (or mirror image) the tree. That is, given a tree with a root node of A and three children, BCD, and two children of B named EF, he wanted to generate a new tree that looked like a root node of A, then DCB with "FE" being the reversed children under B.

Question

Sigiloso · Accepted Answer

I started writing down a function that walks down the nodes while building an array.

E.G. the above tree would convert to:

A0
B1
E2
F2
C1
D1

I'd then walk that array by level, starting with the last entry for each level.  E.G. level 0 is A, level 1 would print out D, C... and before B prints out, I'd print out the children for B on level 2.

I only had perhaps between 7 - 10 minutes to scribble out the concept on the white board and I don't think I was able to adequately flesh out my thoughts, so if I had to hazard a guess as to why I got rejected from the job, it would have been because I didn't impress this hiring manager.

cb · Answer

void reverseTree(Node root)
{
    if (root == null || root.children.length == 0) return;
    // Reverse children nodes, and recurse on those kids
    int start = 0; 
    int end = root.children.length - 1;
    while (start <= end) {
        if (start == end) {
            reverseTree(root.children[start]);
            break;
        }
        Node tmp = root.children[start];
        root.children[start] = root.children[end];
        root.children[end] = tmp;
        reverseTree(root.children[start]);
        reverseTree(root.children[end]);
        start++;
        end--;
    }
}

Nest

Pergunta de entrevista da empresa Nest

Respostas da entrevista

Empresas seguidas

Buscas de vagas