Balancing a binary tree is just an algorithm, like there are so many. As a programmer, you have to design algorithms on the fly, quite a few of which may actually be harder than just balancing a binary tree. Algorithms emerge automatically from designing data structures; when you end up manipulating these data structures. In turn, data structures emerge naturally from trying to model particular problems. There are too many branches in mathematics modeling too many types of problems than anybody could know them all.

In that sense, asking a developer about how to balance a binary tree, is a dumb interview question.

He should only know, if he happened to have worked on exactly that type of problem, only yesterday or so.

The question is rather: If the following is the description of the algorithm to balance binary trees, show that you understand it by dealing with the details in the following examples.

I like your post and just wanted to add on top of this that some algorithms including those sometimes asked in interview questions take/took months or years of effort to come up with. You chase down blind alleys and have insights along the way that come from being deeply immersed in a problem. Which is why interview candidates change these "tests of problem solving skill" into tests of knowledge by cramming.

Often times the right answer is (and should be) "show me you can find and use a use license-compatible library that typically has orders of magnitude more testing in the real world than something you feel the need to re-implement from scratch right now".

The dirty secret is 90% of what happens in the real world (and on HN) is a solved problem that needs to be applied or re-applied. Someone has done it before and they've done it better than you will.

There's a difference between "I know how to do this but it would be a buggy mess and require a week or two of effort, therefore I shall use a library," and "I don't know how to do this but this library seems roughly applicable so maybe it will work."

The former is a healthy and pragmatic use of your most valuable resource -- time. The latter is a cop-out. If no one actually understands what is going on at a deep level in the library, the result is likely to be an over-engineered mess. It might be that you're doing the most efficacious and appropriate thing for the task, but it might not. And with many such decisions made over the course of a project, some of them are bound to be wrong unless someone can reason about them and explain their purpose.

I find this is most important when refactoring or updating code. Some junior engineer down the line will encounter some code he doesn't understand, and track down the guy who wrote it, and at this point there is a world of difference between that guy saying, "Yeah, we needed a data structure that does X and Y so we used that library," and "Uhhh, not sure why we used that library, does anything break if you remove it?"

Followed by "show me you can debug and fix said library when we find it it's slightly broken for our use case"

I benefit from my degrees but I would find it annoying if I would get asked questions like that. I design (among other things) crypto algorithms for banking purposes and implement them in a plethora of languages including ARM asm. But balancing a tree? I did that in an exam on paper 22 years or something ago. I would be able to do it given enough time but I probably would just walk out. 20 odd years ago when I was a cocky and already quite experienced coder, I would have done it easily but, although already having done many real life projects, I was a crap coder. And, due to the strangeness of the market and the scarcity back then, my current freelance salary in Europe, is not too different from what it was then. My feeling is still that those questions are pointless unless you want people straight out of uni. And then they already did their exams with those questions, so again pretty pointless...

I use my CS knowledge all the time when building webapps. Not directly of course, but as a general feel for things.

Stuff like "Oh hey, this problem fits a state machine approach" and "I can reduce the complexity of this sprawling if statement by making a truth table and minifying stuff"

And the good old "What you're asking for maps onto so and so problem and is fundamentally unsolvable. Can we tweak the requirements?"

Sure, you're not inverting binary trees every day, but it's useful to be able to see where a binary tree would help you solve the problem.

Agreed overall--I find that there's a real lack of appreciation of the sort of structural, high-level knowledge that I (at least) learned while getting a CS degree. And not a particularly good one, either, just something at a middling state school.

Just being able to look at a problem and go "hey, this is pretty simple graph traversal, I know the rules for this" has saved my bacon. Or the type theory that I picked up along the way that made type-heavy programming in Scala and Rust make sense. Or the set theory (math, but required for my CS degree, so I count it) that does bounce through my brain when I'm thinking about databases. Or even, like--"hmm, I think I can bang out a quick and dirty parser," and knowing what that parser should look like because I've studied how programming languages work and I get that for free.

I'm not the best programmer ever to walk the earth by a long shot, but I'm pretty good, and I'm pretty good because I can approach problems both bottom-up and top-down. Couldn't do both, flexibly, without a strong academic background.

> Can you give some examples where you hid road blocks because of your lack of education?

Not a veteran, but I've noticed something very odd about entry level jobs - they're not challenging. And that is no accident someone hiring you is actually doing that with a clear expectation that the complexity you're about to encounter will fit into their schedules.

Higher education is very different - the professors are intentionally trying to push you, hopefully bit-by-bit out of the existing skill range into unknowns. At least mine weren't trying to teach me, they were trying to get me to learn, mostly by making my own stupid mistakes without a huge penalty attached to it.

When I moved out of my CS course (and my open-source work building compilers) into my first job, the skill required to do my job satisfactorily was trivial.

No more hard problems, just hard timelines.

Took a couple of years and changing jobs before again landing up with a problem I didn't know how to solve ("Uh, make PHP5 fast ... Go!"), which helped me grow and learn.

That was a lucky break, but I succeeded because my professors had pushed me into the deep end against my wishes (i.e more sleep) before.

>Can you give some examples where you hid road blocks because of your lack of education?

At a certain point I was working on an iOS app attempting to do some really advanced animations with Core Animation/Core Graphics and my total lack of geometry and basic algebra knowledge started to show. One of my colleagues started talking about the movement of an animation in terms of radians and pi and I felt completely lost. He was speaking a totally different language to me. Up to that point I had felt somehow "proud" of being a self taught developer with no formal schooling. But when that happened I just felt completely embarrassed at my lack of fundamental knowledge and context. Now I'm struggling through undergrad mathematics classes and hoping to get to that point some day. The greatest overall takeaway I had from that experience is that math and science open a completely different world to you that most people don't even know exists. It changed my life.

A lot of the hardcore game developers (which use way more math and advanced CS concepts that most other devs) didn't go to college. This stuff is totally learnable on your own. I recommend for example "Essential mathematics for games" by Bishop and Van Verth.

Thanks for the recommendation. As someone pursuing gamedev who also knows their math background is lacking, I'm always looking for tailored stuff like this.

To be honest though, that stuff confuses the hell out of me too and I have an MSc in CS from a highly regarded German engineering university. So while I agree with your general sentiment about depth of knowledge, basic computer graphics linear algebra stuff is just another skill that you learn in a similar way to a new language, for example.

Good to hear that you are learning some practical applied mathematics. It will be useful. You might find that the mathematics taught as part of a CS course is much less useful for 90% of programming jobs and not much use in the rest of your life either.

You need it if you don't want to work on cookie cutter applications.

Cookie-cutter isn't a bad thing. If it solves a real problem or addresses a real need, it will be successful.

I mean Facebook started out as a cookie cutter app. Heck, it was a basic CRUD app. Look at where it is today.

Outside of such unicorns there are also many examples of reasonably successful products that can be categorized as cookie-cutter. Basecamp. Trello. Snapchat. These apps don't do anything groundbreaking or operate on the bleeding edge of technology. But they are well-known and profitable.

Cookie-cutter is also what 99% of programmers work on. Yes, it's nice that you were on the team at facebook that built the first react prototype, or that you were the first software engineer at oculus. The rest of us are building apps, adding an endpoint to an api, figuring out what the new database schema should look like, etc. And there are a hell of a lot more jobs openings for "blue-collar coders" than there are for geniuses.

I mean, it's great you're working on the latest computer vision algo to make the billboards in Minority Report a reality. I just spent the day wrestling with Google's client API registration and authentication nonsense so I could get per-page bounce rates.

I agree. All of us outside of military hear about pilots and Navy SEAL at work most of the time. But 99% of men/women in military work doing none of that stuff. But that 99% are still gainfully employed doing essential work.

Am not military and especially I'm not American, but IMHO wars on the field are not won with Navy SEALs but with logistics and I'd add artillery. Those sound boring compared to any special forces, but they're not, quite the contrary.

I was talking about the amount of media attention given to pilots/SEAL/etc. But yes wars are won with artillery. But luckily, we haven't had a war like that in awhile, especially for US.

I agree except for Snapchat, the real time computer vision they (or at least the startup they bought) put out I would have to say was on the cutting edge. Real time facial recognition was standard, but the facial transformations and 3d modelling in real time stood (and still stand) alone

I don't use Snapchat, so correct me if I'm wrong, but aren't those relatively new developments? From a quick Google search, it seems that the acquisition of Looksery and the launch of "Snapchat Lens" didn't occur until September 2015. By then, Snapchat already had at least 80 million daily active users. While their current real time computer vision stuff is definitely not something the average engineer could make, it does seem like they started out as a cookie cutter app.

I may need it, but I don't necessarily need to keep it in my head.

That's why I own copies of Knuth, and Sedgewick, and Cormen, Leiserson, Rivest, and Stein.

Now, the ability to understand and make intelligent use of those resources is something that requires education (formal or self). But oddly no one (that I've heard of) ever tests for that ability in job interviews.

Weirdly they seem to ask the CS fundamentals that aren't as relevant (algorithms) and skip those that are (e.g. the relational model, data structures (uses of), type theory, formal grammar).

I wouldn't say that you don't need it, but I would say that most companies ask about the wrong bits.

It always baffles me when people say that algorithms aren't relevant to software development. It's like saying thermodynamics isn't relevant to engine design.

Knowing specific algorithms is irrelevant to most modern software development because for any algorithm that's common enough for a "standard" developer to remember you'd be expected to use a pre-existing implementation.

If you want to sort a list, balance a tree, multiply a matrix or find the shortest/cheapest path in a graph, you should use a library that already does that and is reasonably tested and optimized, certainly more than whatever you'd write today. Most likely you shouldn't even get to choose which algorithm to use for that, and if you need to then the choice should be based not on the O() measures you might remember but on benchmarking, since the constant factor often dominates.

I have seen quite a few very large systems in which the most complicated algorithm actually implemented in the system is a set of branching if-then conditionals for some business logic. There's no custom data structure traversal - yes, it needs some data processed, but all the algorithms for that are in the DB implementation and "do X for all selected items" is literally the deepest level of iteration anywhere in the system. There's cryptography, but that's in a separate library made by someone else. There's network algorithms with state in them, but that's managed by a separate layer.

In such data processing systems all the development does is glue code that specifies what exactly should be done, but all the how part (e.g. the algorithms) is already implemented by someone else and is reused.

There are fields and apps (parts of them) that are algorithm-heavy; for example, even simple games tend to pack a lot of interesting algorithms (but even there much of that is now handled by standard libraries/frameworks). But most developers don't work on that, the majority of software dev work is cookie-cutter data processing apps where all the algorithms are out of your scope.

How often do you actually implement algos? Unless you're coding libraries for a brand new language, you're just going to pick out someone else's implementation of it. Why redo that work?

It's more like saying that the detail of the thermodynamics cycle of the specific rotary piston engine of that plane that had one (nah, won't search it) is not relevant to "engine design" stated generally without any modifier.

Those interview questions aren't about "algorithms", they are about details of specific ones chosen by their complexity and that are rarely used in practice.

It doesn't seem that baffling to me. The majority of software applications could only moderately be improved by CS algorithms.

More like saying that knowing the atomic crystalline structures of metals isn't relevant to engine design.

Well, somebody better know the structure of the metals in use, or else you get turbine disks shattering jet engines and landing 1,000 yards away [1]. Just because it's not important to know every day doesn't mean you won't find challenging and important applications of undergraduate-level algorithm design.

[1]: http://www.seattletimes.com/business/boeing-aerospace/dramat...

"Well, somebody better know the structure of the metals in use"

Somebody needs to know how to implement sorting algorithms too. It's just highly unlikely to be you.

Which it completely is, if you want to design a modern engine.

If you want to have an engine with 60s power, weight and fuel economy, then sure you don't need to know the science behind it. Just throw some parts together, and you'll get something that works.

Metal crystalline structures are taught in many metalworking trade schools, even if briefly. It has direct implications for things like heat treatment.

They are controversial because they frequently don't let you look anything up and most developers are used to being able to do that as part of their normal process.

The actual algorithm is irrelevant, so looking it up wouldn't be helpful. The point is to find out if the developer understands complexity well enough that they won't build bad things, that they'll know how to avoid nested loop if they can, that they'll know what the cost of one approach is compared to another.

If you look something up and the interviewer asks you what the O() of your approach is and you don't know, how can they feel assured you grasp these fundamentals?

I understand why these are contentious, but I find people tend to miss the forest for the trees when criticizing the practice.

> The actual algorithm is irrelevant, so looking it up wouldn't be helpful.

It isn't irrelevant if you are attempting to implement it correctly.

> If you look something up and the interviewer asks you what the O() of your approach is and you don't know, how can they feel assured you grasp these fundamentals?

That wasn't the original question in the comment I responded to and your attempt to re-phrase it as X when it was a question related to a specific algorithm is disingenuous.

> Why would an iOS developer need to able to balance a binary tree?

---

<removed a bunch of RL-related stuff that is pointless bitching about ppl we've fired>

> It isn't irrelevant if you are attempting to implement it correctly.

Exactly my point. Rarely is there one "correct" implementation. Understanding the choice you make and can support is the point of coding interviews. That's why they're so often done in pseudocode and/or on the whiteboard.

If you can look stuff up you're not demonstrating a knowledge of the fundamentals. If you don't understand complexity and optimization, you will make mistakes even if you can look stuff up later.

That's why these companies do these.

> Exactly my point. Rarely is there one "correct" implementation.

For any given problem asked in such interviews there is certainly one correct implementation and if you believe otherwise you are not providing sufficient information to answer such a question.

> Understanding the choice you make and can support is the point of coding interviews. That's why they're so often done in pseudocode and/or on the whiteboard. > If you can look stuff up you're not demonstrating a knowledge of the fundamentals. If you don't understand complexity and optimization, you will make mistakes even if you can look stuff up later. > That's why these companies do these.

Honestly? This is part of the rant I was trying to avoid.

1) I've met developers that claim SHA-1 is a secure choice in 2017 and make other facepalm worthy claims that 5 minutes of research would have told them was a bad idea.

2) We've fired quite a few people who believe as you do precisely because they are so convinced they understand the fundamentals they don't look things up and make costly mistakes.

3) I've met accountants who can't correctly handle a 4-4-5 calendar that is integral to their jobs without looking things up. Similarly, I've met ones like you that genuinely believe they've memorized the "fundamentals" and repeatedly failed waste thousands of dollars.

4) I honestly believe anyone who refuses to look things up to double check is fundamentally incompetent. We all make mistakes and the only way to appropriately minimize them is to double check (i.e look things up) before hand and have someone else review it afterward.

5) I genuinely do not want to work with anyone who does not do #4. Ever. The sheer number of times they've attempted to shift blame onto other people before they were fired is simply not worth the hassle.

2) and 4) and 5) are strawmen. It is -in fact- possible to understand the fundamentals and look things up.

As to your assertion that there is one "true algorithm," the merits of that stand for itself, but regardless being able to explain WHY is what an interviewer should look for.

"Go Google and implement some algorithm" does not provide a useful metric other than "can use a computer."

All of this also ignores a more pressing issue: that looking something up often means getting bad results. Can the applicant draw on knowledge of complexity to distill their Google search? Without that types of test your answer is "hopefully."

That's why Google, FB, etc start with whiteboard tests. Anyone can search and implement.

> Can the applicant draw on knowledge of complexity to distill their Google search? Without that types of test your answer is "hopefully."

It isn't difficult to structure a complex question that requires research and have the answer you claim is impossible to find.

> That's why Google, FB, etc start with whiteboard tests. Anyone can search and implement.

I'm sure that is what you believe but that doesn't make it true.

> 2) and 4) and 5) are strawmen. It is -in fact- possible to understand the fundamentals and look things up.

I've never met an engineer (or any professional implementing complex processes) who simultaneously grasped the fundamentals of all areas where they needed to possess competence from memory. (Yes, that includes myself in case you are wondering.)

> It isn't difficult to structure a complex question that requires research and have the answer you claim is impossible to find.

An answer? Sure. THE answer? No. Too much subjective reasoning in that; something that performs well with clock time may be far worse in some other metric. It always depends. You need to be able to explain it, and that's what complexity is about. Fundamental comprehension of the tradeoffs of approaches.

> I'm sure that is what you believe but that doesn't make it true.

Great. Same with you. Unfortunately, those companies agree with me and do fairly well filtering candidates.

> I've never met an engineer (or any professional implementing complex processes) who simultaneously grasped the fundamentals of all areas where they needed to possess competence from memory.

Me neither. But then again that's not what we're talking about.

You do need to know there is such a thing as a b-tree, and when you might want one, and that balancing is a thing that you might want to do, and when to do it - even if you never actually implement one from scratch yourself, you absolutely do need the vocabulary to refer to it and a general understanding of the concept. That's what a lot of self-taught coders are missing - the knowledge of the theory that makes it easy to communicate with others.

Web developers who churn out crud apps think that.

clustering points on a map in iOS needs a good amount of data structures hint* Quad tree and a map like data structure