News for hackers. Stuff that matters.
Re:Bootstrapping My Side Project to $6k/Month by znfii on Thursday November 16, 2017 @11:33AM (#15713986)
Was it ever figured out what "invert a binary tree" means? At least I had never heard this term used prior to this incident. This has me slightly worried about this particular example somehow, and I'm not quite sure what to make of it...
Re:Bootstrapping My Side Project to $6k/Month by guessmyname on Thursday November 16, 2017 @11:44AM (#15714112)

            2                             2        
           / \                           / \       
          /   \                         /   \      
         /     \                       /     \     
        1       3                     3       1    
       / \     / \                   / \     / \   
      0   7   9   1    reverse >>>  1   9   7   0  
     /   / \     / \               / \     / \   \ 
    2   1   0   8   8             8   8   0   1   2
           /                               \       
          7                                 7
— https://leetcode.com/problems/invert-binary-tree/description...
Re:Bootstrapping My Side Project to $6k/Month by znfii on Thursday November 16, 2017 @12:55PM (#15714806)
So several people replied with this same thing, which I have heard before being suggested. However, as I recall it at the time, if you tried to search for "invert binary tree" this term basically did not exist on the internet. I just tried searching on google with time set between 2000 and end of 2014 which seems to give similar results.

I guess I did not spell it out in my original post, but I always felt it might have been an intentional nonsense question intended to gauge how he would react to someone talking nonsense, or something like that, and not necessarily related to technical things. A sibling post of my original to suggest this was the case, without the weird detour through the term "invert binary tree".

Edit: Of course an alternative explanation is that the interview used another term and he then used the term "invert" on twitter.

Idk, this example at least has to me always felt like people who complain about not passing the driver's test coz they did some minor error and then forgetting to mention that they drove past a stop sign.

Re:Bootstrapping My Side Project to $6k/Month by xiphias on Thursday November 16, 2017 @04:25PM (#15716773)
I'm not 100% sure about the inverting part, but at Google nobody ever told me to ,,fuck off'' and nobody would tolerate that language, and that person would get a serious talk from his/her manager, maybe even laid off instantly, especially if it's written.
Re:Bootstrapping My Side Project to $6k/Month by Posibyte on Thursday November 16, 2017 @11:38AM (#15714039)
I assumed it as taking a binary tree (L|R) and reproducing a tree that's (R|L). And if it is that, then writing out the algorithm on a back of a napkin just now was a pretty thought provoking exercise :)
Re:Bootstrapping My Side Project to $6k/Month by gizmo on Thursday November 16, 2017 @11:37AM (#15714037)
It means to swap the left and right arm of each node. So you effectively "mirror" the tree.
Re:Bootstrapping My Side Project to $6k/Month by ezekg on Thursday November 16, 2017 @01:27PM (#15715158)
Yeah, it's relatively simple once you come to that realization:

    TreeNode* invertTree(TreeNode* root) {
      if (root == NULL) {
        return NULL;
      }
      
      TreeNode* tmp = invertTree(root->left);
      root->left = invertTree(root->right);
      root->right = tmp;
      
      return root;
    }
It sounds a lot more complicated than it is.
Re:Bootstrapping My Side Project to $6k/Month by vkou on Thursday November 16, 2017 @01:39PM (#15715257)
Until I throw this test case at you:

    TreeNode testRoot = new TreeNode();
    testRoot.left = testRoot;

    invertTree(root); // Stack overflow.
But that's not a tree, that's a cyclic graph, you may shout. That's true, but you still need to sanity-check your inputs.
Re:Bootstrapping My Side Project to $6k/Month by archagon on Thursday November 16, 2017 @02:40PM (#15715821)
That ought to be done in a separate validation step, and/or the tree object should enforce its invariants.

(I shouldn’t be arguing interview problems on HN, but I’ve had a few beers.)

Re:Bootstrapping My Side Project to $6k/Month by vkou on Thursday November 16, 2017 @05:34PM (#15717323)
I argue that if an interview question asks you to implement parseInt(String foo), it's your responsibility to handle inputs that aren't a properly formatted integer gracefully.

Or at least to point out to the interviewer that your solution fails to handle unexpected input, and ask if they want you to add input validation logic, or if they are satisfied with the answer.

Re:Bootstrapping My Side Project to $6k/Month by archagon on Thursday November 16, 2017 @05:46PM (#15717399)
Sure, but this assumes that foo is a valid String — just formatted incorrectly for use with an int. If we can't assume that TreeNode constitutes a valid (cycle-free) tree, we essentially have to embed a full cycle-checker in our otherwise simple inversion function. I would argue that goes against the intent of the question.
Re:Bootstrapping My Side Project to $6k/Month by matthewaveryusa on Thursday November 16, 2017 @11:39AM (#15714056)
Invert a binary tree as in heapify it maybe because inserting occurs at the leaf not root? Is that what it means? Does it simply mean changing the insert criteria so that a<b is now b<a?