3 ms·
seconding this, creating value is orthogonal to knowing CS. see the creator of homebrew, Max Howell infamously failing to invert a binary tree in an interview:
by guitarbill 8y ago
seconding this, creating value is orthogonal to knowing CS. see the creator of homebrew, Max Howell infamously failing to invert a binary tree in an interview: https://mobile.twitter.com/mxcl/status/608682016205344768?lang=en https://mobile.twitter.com/mxcl/status/608682016205344768?la...
- commandlinefan 8y agoI have yet to see a definition of what “invert a binary tree” even means.
- nickbarnwell 8y agoI think "mirror" is a more intuitive description of the problem, but essentially you reverse all of the left and right subtrees. This Quora question [1] has a few different approaches listed. [1]: https://www.quora.com/What-is-the-algorithmic-approach-to-invert-a-given-binary-tree https://www.quora.com/What-is-the-algorithmic-approach-to-in...
- balfirevic 8y agoThat doesn't sound like "inverting". If that is what it means then it is indeed a bad name. I always thought it means making one of the leaf nodes a root of the tree. Physically, it would look like taking one of the leaf nodes with your fingers and "hanging" the tree off of it.
- BearOso 8y agoInverting means inverting the sort order. The easy answer is to encapsulate the tree in a new structure and add a Boolean flag called “inverted,” since you’re just reinterpreting the meaning of left and right children. What you describe is called “rotation,” and is used to rebalance.
- boomlinde 8y agoinvert: to reverse in position, order, or relationship
- fenomas 8y agoI'm confused. Doesn't the operation described in those answers just rename each node's properties, but leave the topology of the data structure unchanged? Meaning one could just have the code accessing the tree swap which names it accesses, and the tree would behave as "inverted" with no actual need to invert anything?
- peterkelly 8y agoIt's when you swap the left and right branches of every node, e.g.: def invert(node): if node is not None: left = invert(node.left) right = invert(node.right) node.left = right node.right = left return node
- aldanor 8y agoOr simply node.left, node.right = map(invert, (node.right, node.left))
- quietbritishjim 8y agoCoalescing those four lines onto one is fine, but writing: map(invert, (node.right, node.left)) is definitely not simpler than: invert(node.right), invert(node.left)
- peterkelly 8y agoIndeed - I just wanted to write it in a form that could easily be mapped to languages which don't support multiple simultaneous assignments :)
- deleted 8y ago[deleted]
- sigi45 8y agoI read it, tried it out and it didn't took me long to understand and solve that issue. If you hack around for a long time and you never ever felt the need or motivation to understand very simple tree algorithms, okay. But don't rant when a company like google expects that from you. He also answered, after a few years on a website about it: https://www.quora.com/Whats-the-logic-behind-Google-rejecting-Max-Howell-the-author-of-Homebrew-for-not-being-able-to-invert-a-binary-tree https://www.quora.com/Whats-the-logic-behind-Google-rejectin...