[cynicalkane]

A breadth-first search is a pretty basic algorithm, but even if you don't have it "memorized", the question is simply: here's a data structure, we need to traverse it in a certain order. Traversing data structures is so common that, even without a formal CS education, 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.

A candidate who freaks out upon being asked that question is not a candidate whom I'd trust to be a good problem solver. Solving a problem with simple constraints is something that happens all the time. 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?

[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-...

[tptacek]

What drives me a little nuts is all the people on this thread saying BFS is simple, as simple as counting, as if that somehow strengthened their argument. It does the opposite: BFS is indeed simple, so simple that you can simply explain it to a candidate and ask them to implement it, just like you would do with an actual developer (or, more likely, that they'd just do for themselves based solely on the Wikipedia page).

I'll go a little further and say that if you've qualified a candidate as capable of busting out the routine Javascript required to wire up typical front-end code, if you can't teach that developer how to implement BFS within the confines of a single interview, you the interviewer share some of the incompetence. Certainly that would be the case for a manager or team lead!

The reality is that BFS is for most jobs (frontend AND backend) a trivia question, and a status-seeking mechanism for interviewers.

[0xFACEFEED]

THANK YOU. 16 years I've been writing code and I can count on one hand the people I've met who realize this. I get a little emotional about it because I've seen so many exceptional programmers crumble in interviews with trivia questions.

If an interviewer wants to test problem solving skills with a BFS, no problem:

- Draw a tree on the whiteboard (interviewers writing the whiteboard is highly undervalued; it calms the candidate)

- Explain what a BFS is. It's easy to draw out each step in a BFS algorithm.

- Ask the candidate to write some pseudo code that implements it.

[theamk]

I do, every time! I even drew a little diagram a couple of times and traced the path!

And they still failed it! It is not about trivia or what BFS is, it is all about can you reason about algorithms.

(Disclaimer: our actual interview problem is slightly different, but it it still a very basic CS one)

[Twirrim]

> And they still failed it! It is not about trivia or what BFS is, it is all about can you reason about algorithms.

Okay.. so now this is about you and a bad candidate rather than the person pointing out that interviewing is broken. Got it.

[theamk]

Well, if at least one person reads the discussion, and then starts inventing the algorithms instead of giving up right away, I'd be happy :)

Because someone saying "How would I know? If, and when, I need to know how tree-shaking is implemented, I will go look it up." makes me sad. The tree-shaking algorithm was not given to us by ancient gods. As a programmer, you job it is to solve problems no one has solved before. Interviewing may be indeed broken, but the original article was not showing any evidence of this.

[Jach]

> the question is simply: here's a data structure, we need to traverse it in a certain order

Because BFS/DFS are so easy to interchange, I'd strip ordering out entirely: here's a collection of stuff where each element may also point to other stuff in the collection, starting with this element search through the stuff to see if you can find a certain element.

If I was going to ask this problem, I'd help a nervous-looking candidate by contrasting the problem (or leading with) a simpler still one: here's a collection of stuff where each element can point to at most one other thing, starting with this element see if you can find a certain one in the collection.

Linear search is, technically, an algorithm. Graph search just extends it. All these people railing against algorithms in interview problems as non-applicable surely have at least written a for loop over an array and had an if statement somewhere inside, right? Linear search. When I've given interviews I don't try to make them based on "algorithmic knowledge"[0] but at the same time I really don't like the trend of thinking of algorithms in general as "oh, that's someone else's job, I never use those" or "I can only implement algorithms by memorizing them."

[0] When I was just starting to get asked to give some I lazily asked a colleague for a reference problem, they sent me https://leetcode.com/problems/jump-game/description/ and I read the problem, immediately recognized that the general approach of graph searching would solve it[1], and coded up the 12-15 lines or so it took, made some tests, fixed some minor mistakes... Total start-finish time was 10-15 minutes, not the fastest. There's also a solution to that problem that doesn't require thinking of it as a graph, too, but I think it's harder to get the insight. Anyway, nice problem, I thought, I'll only give a problem if the candidate has 2x the time it takes me to solve it as a buffer for interview nervousness/whatever, but after giving it to a few people only one of them managed to solve it in like 50 minutes after creating a pretty verbose and pseudo-coded BFS system. (My initial approach used DFS, but it doesn't matter here -- though for the jump game 2 sequel problem which asks to find the shortest number of jumps, BFS makes sense, and it's easy to take the solution for the first problem and make minor alterations. General algorithms like "search" are great and widely applicable.)

[1] In retrospect, before I saw the problem I was writing a simple game of go client as a side project, and had recently implemented a function to, given a point on the board, determine if there's a stone there and if so determine if it's part of a larger group of stones and return their coordinates. So in some sense the problem was already 'primed', and I've written a lot of graph search skeletons for both fun and profit. It's interesting to hear that some people go decades without doing so...

[emmanueloga_]

This problem can be solved with my favorite algorithm in the whole world, union-find [1], yaaay! :-p

It is hard to say if U/F would be more efficient for this problem. U/F can perform two `union(a, b)` and `find(a, b)` operations in O(lg n) runtime complexity, or, with some more effort (path compression), nearly constant time (a, b representing node indexes). But for this problem a first pass over all indexes would be required to build the disjoint set from the input.

I think for small inputs DFS or BFS would be more efficient, and have the plus of not needing extras storage (U/F would require a second array the same size than the input). For large arrays, probably U/F would win since the input array may encode potentially a lot of edges (say, if each index contains a number large enough) and DFS runtime complexity is O(Edges + Nodes).

Anyway, I think U/F can be really useful in the context of job interviews, there are many problems that can be reduced to connected components, after some massaging.

Here's an implementation I did a while ago [2]. Even though I love the algo, I don't really remember the details about path compression... time to refresh my memory I guess :-D

[1]: https://algs4.cs.princeton.edu/15uf/

[2]: https://gist.github.com/EmmanuelOga/bcafad14715a3f584e97

[Jach]

Neat structure! I consulted my copy of Skiena's Algorithm Design Manual. He says: "Union-find is a fast, simple data structure that every programmer should know about." Well... Now I do. :) It is simple, a 'backwards' tree with pointers from a node to its parent, which lets you union two separate trees together by just taking the shorter one's root and pointing it at the taller one's (or vice versa, but this way preserves log behavior). The path compression optimization seems to just be an extra pass in find(), after you have the result, to re-parent each item along the path to the found root parent so that any future finds() of any of those items will only have one lookup to reach the component root.

For the jump game problem, I'd expect DFS would still win almost all the time even when there are many branches because it doesn't have to explore every element of the input array except in the worst case (and you can greedily explore a neighbor without having to discover your other neighbors first), whereas to build a complete union-find structure would. Still, the fastest solution in general is probably just the single pass: if you have the insight that you can keep track of a 'max reachable index' and update it at each step to max(current-max, i + A[i]), bailing with failure if you hit an index > the current max and having no more jumps, or bailing with success if your max becomes >= the final index. (I never had this insight myself.) It could be slower of course, e.g. if the array was something like [bigNum/2, lots of 0s, bigNum/2 again in the middle, lots of 0s, end at index bigNum].