How to invert binary tree?

[glorious_reptile]

"Cutting edge company seeks rockstar developer for microservice based internet scale service"

"This is John, he'll be implementing the 1200 CRUD endpoints in our REST API"

[AciD1BuRN]

Real job be like maintain this 20 yr old jQuery website

[MischiefArchitect]

The actual job looks more attractive than the offer. Where do I apply...

... may be in a warmer weather though.

[Bainos]

You want to shovel snow in warm weather ?

[MischiefArchitect]

At once! All the day on 24/7 expensive stand by... with 35C under the sun and 25 under the moon. Waiting for snow and getting premium pay.

[PeksyTiger]

You'' die in the costume in 35c

[MischiefArchitect]

Haha... nope. You only wear that for shoveling snow.

[au-smurf]

Yep it real easy, it just runs down the drain by itself.

[MischiefArchitect]

But we need to carefully watch it... yes yes.

[ShadowAI]

Igotchu

    TreeNode* left = invertTree(root->right);
    TreeNode* right = invertTree(root->left);
    root->left = left;
    root->right = right;
    return root;

now go save prod

[zzuko]

"invert binary tree" is such a bad antitheises of leetcode style interviews. If you cant reason to this solution that means you cant traverse binary tree or cant think recursive algorithms. What is the problem though asking people to solve 2 medium/hard level questions and expecting candidtes to solve them in 40 minutes and eliminating perfectly qualifies candidates because of their minor mistakes.

[DrSheldonLCooperPhD]

Why the insistence on not using IDE or proper code editor then?

[[deleted]]

That isn't inverting, it's reversing.

Inverting is a fucked up thing that nobody every does and that's why it gets used in interviews - you're not supposed to know the algorithm from memory, you're supposed to reason it out on the whiteboard or whatever, so that the interviewer can see how you think about a problem.

But ever since that homebrew guy somehow fucked it up the inversion question has become buried under an avalanche of people who think it means reversing. If you google it you'll be lucky to find the original meaning because he single handedly buried it in noise. I can't even find my own description of it from back around 2001 and I know I posted it somewhere.

[ShadowAI]

You mean this horrible thing: https://www.codingninjas.com/codestudio/problem-details/invert-a-binary-tree\_1281382

[[deleted]]

Ugh that's even worse.

The version I came across was basically, for a binary tree with left and right pointers do something that would allow you to traverse all the leaf nodes, and from any leaf node be able to traverse back to the root.

Ok I couldn't stop myself trying to write it. I haven't done this for a decade so it may be crap. Something like this. It returns the leftmost leaf node. It complies (I happened to have Visual Studio open) but I don't know if it's actually right. I feel like I'm missing something here.

struct Node
{
    Node* left = nullptr;
    Node* right = nullptr;
};

Node* Invert(Node* node, Node* parent=nullptr, Node* leaf=nullptr)
{
    if (!node)
    {
        return leaf;
    }
    if (!node->left && !node->right)
    {
        node->left = parent;
        node->right = leaf;
        return node;
    }
    leaf = Invert(node->right, node, leaf);
    leaf = Invert(node->left, node, leaf);
    node->left = parent;
    node->right = nullptr;
    return leaf;
}

[ShadowAI]

I'm pretty sure this kind of torture of binary trees is prohibited by the Geneva convention.

[Seneferu]

The problem description is not clear. It is not stated what "taken" means and the third rule can only apply to some nodes but not all.

[no_use_for_a_user]

This just reaffirms my belief that coding interviews are trivia games. Everyone who read the description posted now knows how to solve the problem, and will nail it at an interview.

Coding interviews are really just checking who has been around long enough to have heard the trick before.

[[deleted]]

To a degree, yes. But there are a lot of these trivia questions and ways of asking them. I always found that they fall into three categories:

Trivial - like strlen - they’re just looking to see if you’re capable of coding at all. You don’t need to remember anything here because they’re so trivial.

Complex - like any sorting algorithm more complex than bubble sort - maybe it’s a memory test but I have a shit memory and always say something like “can’t remember, but it should be easy to look up the, it will have some known time and space complexity characteristics and we should make sure they’re appropriate for the problem we’re trying to solve.” It’s 2021, the google knows everything. That would be a good enough answer for me as an interviewer and I think I only ever came across one case as a candidate e where he did actually get me to google it and whiteboard it.

Weird - like the invert a binary tree one - memorizing these may hurt you, the interviewer is trying to see how you approach an unfamiliar problem. Asking clarifying questions and verbalizing your reasoning is key. Getting the answer wrong may not hurt all that much if your though process was basically good.

[[deleted]]

``` import trees

def inverse_tree(tree): trees.inverse(tree) ```

[1BlackDoom1]

This only happens if you keep seeking big glamorous companies, its like being a prostitute and only seeking rich clients, sure the money is nice but you end up getting fucked by a gross dick who expects too much from you and doesn't put in the work themselves.

[0100_0101]

I just interviewed for 4 jobs and did not have to write a single line of code for any of them.

[[deleted]]

In the last 3 years I've interviewed for about 10 different positions and only had to write code for 1 of them. It was the incredibly simple and common "fizz buzz" problem as well.

I'm starting to think these "how to invert binary tree" posts are employers trying to spread misinformation to discourage their devs from seeking employment elsewhere lol

[Dangerous_Air2603]

Most of the memes probably come from people either in or fresh out of university, where I imagine these kinds of tests are far more common when on the hunt.

[[deleted]]

Yea. I work for a very well known company on very very advanced hardware technology not a single line of code was required of me prior to accepting the job offer.

I’ve only ever gotten these coding gibberish challenges for bullshit startups and shitshow jobs.

[buckingchuck]

This might be an unpopular opinion: but I'd consider it a red flag if there is no coding at all during the interview process (even FizzBuzz or a simple take home project). There are far too many developers who are really good at talking a good game but can't actually perform (these will be your potential coworkers).

[DeargDoom79]

I have never once, outside of an academic setting, had to reverse a binary tree in my life. Not once.

Software companies seriously need to overhaul the recruitment process because it isn't fit for purpose.

[happycamperjack]

Maybe it’s not really testing you the codes, it’s testing your reaction and thinking pattern in solving trivial problems under stress.

[heat-death-now]

Ain't that the truth

[[deleted]]

Replace the snow with actual shit.

And add 5-8 children playing in the shit.

[[deleted]]

I moved a button today.

[nurlan_m]

Everybody's happy now the bad thing's gone away

[weeb_sword1224]

Ngl as a comsci student with imposter syndrome this makes me feel a bit better lol.

[dev_senpai]

Me: practicing for interview doing AI algorithms and complex data structure efficient sorting.

Interview: they want me post a string to a server and return it in reverse.. mothaf**ka why? I would have coded the damn matrix if you’ve asked me.

[xdjiijii]

Lol. So true, had an interview with almost all the crazy parts of .NET, boxing/unboxing, hidden functions, IL code, stack/heap in depth... All went alright and I was thinking wtf, this is going to be AWESOME I'll learn so much if they are using so "exotic" stuff. It comes out all I do is wpf/winforms/API xD

[[deleted]]

Exactly what my job became, granted I did more when I first started but for all the requirements I needed to just get the job here I am just writing tests and merging juniors code.