Indeed, it's not a difficult question.

I think people were making fun of Google, because it is a caricature of their whole interview process.

If a large number of your engineers is using Homebrew, having its developer is an asset for many different reasons (e.g. influencing the focus of the project, getting formulae in that interest you, or simply improving a tool that is important to your productivity). But no, they reject him because he cannot invert a binary tree.

It's like throwing one of the better offenders out of your soccer team, because he cannot substitute as a goalkeeper.

Having the developer of Homebrew as an employee is only an advantage if you want to influence it's development, and if the developer is happy for his application to be influenced by his employer rather than the Homebrew community as a whole.

In fact, I would see Google hiring the leaders of open source projects in order to influence the direction the project takes as a problem. Sponsoring an open source project is brilliant, and Google are great at that, but buying influence over it is completely different and (potentially) an issue that would lead to people forking the project.

If interviews are really made to maintain high-engineering standards and prevent bad hires, interviewing and rejecting the author of a software that 90% of your employees use everyday is quite perplexing indeed.

While I understand that interviews are sometimes necessary to evaluate a candidate, it seems completely out of touch for Google to pass on an applicant with such an impressive background.

Not only that, but heaven knows that it takes a lot of dedication and leadership to lead an open source project from ideation to wide-spread use. If I were a startup founder, I would kill to get someone like him on my team.

It's more like not letting the CEO of your soccer ball manufacturer play on your team because he can't kick a soccer ball.

I don't see how this is relevant - in this case, a coder was rejected for a coding position. If we substitute your case, you could re-state it as "A player was rejected for defender" (or attacker/etc). In your example, you've changed that to "A manager was rejected for defender". Not the same.

>I think people were making fun of Google, because it is a caricature of their whole interview process.

To be honest, it kind of makes me wonder about the kind of code Google has, if this is a measure of a good coder. Are low level algorithms haphazardly re-implemented in python everywhere there is a need for one?

I've seen lots of code like that before. I was very unimpressed.

Btw, Python has nifty multiple assignment, so you can write the swap simply as:

    root.left, root.right = (self.invertTree(root.right),
                             self.invertTree(root.left))

(Parentheses added to break over two lines.)

Same in Ruby, but it doesn't need the parens to cross lines:

   root.left, root.right = invert_tree(root.right),
                           invert_tree(root.left)

I don't like that. I see it as potentially causing more far too many potential problems for such a niece feature.

Especially as Ruby has automatic unpacking of function returns, yes?

So something along the lines of:

    a,b = function_returning_two_things(),
    function_returning_one_thing()

could cause bugs.

That's certainly possible - this would get you 'a' containing an array from the first function and 'b' with the result of the last.

Can't off the top of my head recall actually seeing such a bug. I totally appreciate the desire to reduce the potential for errors from typos, but that ship has kind of already sailed with either language. I guess it just depends how far you're willing to let it go.

Yay choice. Testing will catch it anyway, right?

:/

That was my immediate thought too. It's nice to think of those 2 operations as an atomic unit.

Very interesting that the 3 answers here are 2 Python and 1 C++; I feared the world had descended into a JS downward spiral, but clearly not.

I am your fear:

var invertTree = function(root) {

    if (!root) {
        return root;
    }
    
    var left  = root.left;
    var right = root.right;

    root.right = invertTree(left);
    root.left  = invertTree(right);
    
    return root;
    

};

That was my fear, too. And I also will go with C++ first.

It's not the difficulty people are whacking, but the practice of white board coding.

Iterative solution:

    def invertTree(self, root):
        queue = []
        if root is not None:
            queue.append(root)
        while queue:
            current = queue.pop()
            current.left, current.right = current.right, current.left
            if current.left is not None:
                queue.append(current.left)
            if current.right is not None:
                queue.append(current.right)
        return root

Better solution:

    def invertTree(self, root):
        queue = []
        if root is not None:
            queue.append(root)
        while current is not None or len(queue) > 0:
            while current is None:
                current = queue.pop()
            current.left, current.right = current.right, current.left
            if current.left is not None:
                if current.right is not None:
                    queue.append(current.right)
                current = current.left
            else:
                current = current.right
        return root

No needless enqueuing / dequeuing of things unless you need to. As a bonus, if the nodes maintain a count of how many children the have overall you can always recurse on the smaller child first and use less memory.

Any particular reason why you're using an array as a stack (LIFO) but calling it "queue" (FIFO)?

Not sure why, but I'd feel iffy iterating on a list while mutating its content.

But I guess it's file while ignoring the order of the items, and just caring if it's containing items or empty.

Carry on :)

A functional approach:

      (defun mirror (tree)
        (when tree
          (tree 
              (tree-data tree)
              (mirror (tree-right tree))
              (mirror (tree-left tree)))))

For completness, here are the definitions:

      (defpackage :trees (:use :cl)
                  (:shadow #:copy-tree))
      (in-package :trees)
      (defstruct (tree (:constructor tree (data &optional left right))
                       (:type list))
        data left right)

As well as a test case:

      (mirror (tree 4 
                    (tree 2
                          (tree 1)
                          (tree 3))
                    (tree 7
                          (tree 6)
                          (tree 9))))

      => (4 (7 (9 NIL NIL) (6 NIL NIL)) (2 (3 NIL NIL) (1 NIL NIL)))