ollieoblivious:

varlogme:

I did a second round interview with Twitter recently and the two technical questions I was asked are pretty interesting. The first I solved rather quickly but the second took a bit more time (and a hint).

Question 1:

Given a binary tree with elements of type int determine if the…

For question 1 I would have made a crawler for the tree, incrementing along the nodes in a symmetric pattern and comparing on each step.This would’ve taken (n-1)/2 iterations, I guess.

I rooted around the internet and found this SUPER elegant recursion solution:

Call mirrorEquals(root.left, root.right) where mirrorEquals is

boolean mirrorEquals(BTree left, BTree right) {
  if (left == null || right == null) return left == null && right == null;
  return left.value == right.value && mirrorEquals(left.left, right.right) && mirrorEquals(left.right, right.left);
}

For the second question, I guess..hmm.

Wow thats super elegant. My solution was two traversals on the two immediate children, both preorder (but the left side side was root, left, right while the right was root, right, left). I pop these traversals into arrays and compare. In retrospect, this solution isn’t constant memory :/