5 ms·

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 trave

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 8y ago
> 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.
- calcifer 8y ago
  > 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 8y ago
    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 8y ago
      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/ https://blog.codinghorror.com/why-cant-programmers-program/ [2] https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-...
- throwawaymath 8y ago
  > 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 8y ago
tptacek 8y ago
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.
- deleted 8y ago
  [deleted]
- 0xFACEFEED 8y ago
  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 8y ago
  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 8y ago
    > 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.
Jach 8y ago
> 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/ 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...

0xFACEFEED 8y ago

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

calcifer 8y ago
> 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 8y ago
  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 8y ago
    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/ https://blog.codinghorror.com/why-cant-programmers-program/ [2] https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-first-tree.svg https://upload.wikimedia.org/wikipedia/commons/3/33/Breadth-...
throwawaymath 8y ago
> 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 8y ago

tptacek 8y ago

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.

deleted 8y ago
[deleted]
0xFACEFEED 8y ago
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 8y ago
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 8y ago
  > 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.

Jach 8y ago

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