[0xFACEFEED]

> Solving a problem with simple constraints is something that happens all the time.

I disagree. My experience has been that these problems are exceptionally rare.

They're so uncommon that programmers get excited when presented with such a problem. It feels like "real programming" as opposed to fixing bugs, writing prototypes, or writing business logic.

> I'd expect an engineer with years of experience to have the strategies in a sort of unconscious memory, like a rock guitarist who plays the right chord progressions without knowing what they're called

This is fantasy. You're comparing the average programmer to musical savants? What?

You happen to have memorized a bunch of algorithms for traversing data structures. That's great, but nothing about that is "unconscious memory". The fallacy is expecting everyone else to have memorized the same thing you have memorized.

> If you don't know how to approach that, you could just "look it up", but how would you even know what to look up?

Google for "tree traversal" and spend 10 minutes researching common algorithms. Pick one that fits. Spend 20-30 minutes writing it (hopefully with some tests). Worst case you've spent an hour.

Someone who memorized the algorithm could probably write it (with tests) in half the time. And that's okay because how often are you doing tree traversal? And even if you're doing tree traversal all the time then you'll have memorized all these techniques in 1 month anyway.

[throwawaymath]

> This is fantasy. You're comparing the average programmer to musical savants? What?

They didn't describe a musical savant. They described someone who learned to play the guitar without any background in music theory. The analogy was not someone playing a chord without knowing the name of the chord, it was someone playing a chord progression without knowing the formal musical basis for that progression.

That kind of intuition is very common in guitarists, and I thought the analogy was rather apt.

[0xFACEFEED]

> They described someone who learned to play the guitar without any background in music theory.

I have no idea what guitarists and other musicians you know. I know quite a few and they've had to put in serious work on music theory (most from a young age). Many also started out with instruments like early piano lessons and transitioned to guitar.

It's quite literally a language you need to learn (memorize); kinda like maths actually. Some things may seems intuitive but only savants can compose actual music without training in music theory.

[agentwiggles]

I would guess that the _vast_ majority of guitarists learn that "G D Em C" sounds good _long_ before they understand that it's an I V vi IV progression. I started off playing guitar with three open string power chords, and I didn't have any understanding of theory for years of playing.

[throwawaymath]

No one is talking about composing music without a classical background. We're talking about playing music without the background.

Composing music is to playing a chord progression as writing a naive algorithm implementation is to designing an optimal algorithm.

[shkkmo]

> The fallacy is expecting everyone else to have memorized the same thing you have memorized.

I don't see why any memorization should be necessary. I have never written a BFS algorithim. Yet I can immediately think to two different ways of implementing it. In fact, when reading the article I googled BFS to make sure it wasn't referring to something else because BFS seemed so simple to implement. All you have to do is place every node's children in a FIFO que and process the nodes in the order they are added. You could also use two arrays, one for the current level of nodes and one for the next one. It is only slightly more complicated if you are traversing a graph, rather than a tree, as you need to track visited nodes to avoid repeats.

Also, the utility of BFS and DFS in frontend seems hard to ignore, the majority of the data structures are trees (html, xml and json) and these are the two ways to traverse them.

> They're so uncommon that programmers get excited when presented with such a problem.

What about "process these things in this order" is uncommon? If anything, the constraints are far simpler and easier to understand than most of the business logic I implement.

[0xFACEFEED]

> I don't see why any memorization should be necessary. I have never written a BFS algorithim.

Neither have I, but we both have prior knowledge that accounts for solving most of the problem. We know how trees are implemented. We clearly know what BFS is and what's "tricky" about it.

Someone hasn't dabbled with tree traversal has to grok a lot of information in the heat of an interview.

> Also, the utility of BFS and DFS in frontend seems hard to ignore, the majority of the data structures are trees (html, xml and json) and these are the two ways to traverse them.

I'm not 100% sure about frontend, but I haven't heard of anyone writing tree traversal algorithms for a DOM tree. That's all handled by either browser APIs (document.querySelectorAll?) or lower level libraries (ReactDOM?).

> What about "process these things in this order" is uncommon? If anything, the constraints are far simpler and easier to understand than most of the business logic I implement.

That's exactly the point. Think about it... there are literally dozens of ways to implement a BFS. The currently accepted standard way of writing a BFS is the most concise and efficient.

A minuscule amount of your business logic is as concise/efficient. Most of the time your business logic will balance finding the best solution with meeting milestones (milestones usually win).

So let's say someone doesn't have any experience traversing trees (why would they? you rarely have to, if ever). Let's also say that they haven't memorized what BFS is and what the constraints are. You're presenting them with a new problem and expecting them to come up with the most efficient/concise solution to that problem. The only people who get rewarded here are people that simply memorized the solution or the solution space. In effect you've validated nothing.

[theamk]

> So let's say someone doesn't have any experience traversing trees (why would they? you rarely have to, if ever). [...] You're presenting them with a new problem and expecting them to come up with the most efficient/concise solution to that problem.

I did the some of those interviews (not specifically with BFS, but with similar problems) and my answer to that is: Nope, I do not care about "most efficient/concise solution to that problem". I just need some evidence that you are trying to solve this problem. I am here to help them -- after all, for the interview to be useful, I need to see your work.

So I'd formulate the problem (if the person forgot what those 3 letters mean), draw a diagram if candidate is having difficulty, give increasing hints for the solution ('How would you do it manually? Which node would you visit first? What about next one?' and so on...)

Even then, a surprising number of people would just give up. It is kinda weird -- it looks like when they hear some words they just think "OH NO THIS IS DIFFICULT" and stop even trying.

Those get rejected. We have often have difficult problems. If you stop at one thought of algorithms, you get 0%.

And if you have not memorized what BFS was, and I had to draw a diagram of the tree and trace the path, and give you a hint about maybe using some sort of queue for unprocessed problems and you did not even finish the solution at the end -- you'd still get 80% and might very well get an offer.

[shkkmo]

> So let's say someone doesn't have any experience traversing trees (why would they? you rarely have to, if ever).

Ummm... what? Basic DFS of trees with nested foreach loops is incredibly common. It is not a generic, depth blind traversal, but it most certainly is tree traversal.

> You're presenting them with a new problem and expecting them to come up with the most efficient/concise solution to that problem. The only people who get rewarded here are people that simply memorized the solution or the solution space. In effect you've validated nothing.

If somebody gives up on solving such a simple problem, why would I ever want to hire them?

> The only people who get rewarded here are people that simply memorized the solution or the solution space

Says who? You are making a bunch of assumptions about why the question is being asked.

[jenscow]

I think the point was, the algorithm is so basic that a moderately experienced software engineer could invent it - it doesn't need to be researched.

> as opposed to fixing bugs

bug: "takes too long to find a <file / json field / html node>"

It's a real problem.

[0xFACEFEED]

> I think the point was, the algorithm is so basic that a moderately experienced software engineer could invent it - it doesn't need to be researched.

Right. My point was the problem is perceived as "basic" because the commenter memorized solutions in the problem space. If it's not something you deal with regularly (or have interest in) then it isn't as basic as it seems.

People that haven't memorized the most efficient/concise solution also freak out because they know that their whiteboard solution is going to be judged on the merits of the industry standard solution.

> bug: "takes too long to find a <file / json field / html node>"

This is almost always an issue with an underlying library. The better question is why your programmers are wasting time writing slow BFS code when they should be using well tested solutions.

Example: I recently needed to write some AST transformation code. Did I write my own AST node traversal code? Hell no! I picked a library that did the job. I spent about 20 minutes catching up on state of the art AST traversal (so I'm not blindly importing a bad solution) and let the library do the work.

[calcifer]

> Google for "tree traversal" and spend 10 minutes researching common algorithms.

The point is you wouldn't know what to search for. If you don't know anything about cars, you wouldn't be able to search for "alternator fault". The best you could do is "engine problems" which won't help you solve the actual problem.

[0xFACEFEED]

You're implying that someone who can't invent a BFS on the spot also doesn't know what tree traversal is. That's not true at all.

[calcifer]

If you can program [1], you can do BFS - no need to "invent" anything. Given a tree like this [2], asking you to "print the numbers in order" is not a difficult question, it's a trivial one.

I would expect any interviewee that calls themselves a programmer to talk me through a reasonable answer to that question. Forget about what BFS means - you don't even need to know what a tree is. Looking at the image is all you need.

[1] https://blog.codinghorror.com/why-cant-programmers-program/

[2] https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-...