4 ms·

Bfs is just one of examples. I can ask you a question you will not be able to answer without knowing the answer. There is a reason it took researchers years to

Bfs is just one of examples. I can ask you a question you will not be able to answer without knowing the answer. There is a reason it took researchers years to find those optimal solutions

cornellwright 8y ago
Sure, you can come up with an algorithm question hard and obscure enough that no one will be able to answer it in the time given and no one will have bothered to memorize it because it's so obscure. That doesn't mean all "implement X algorithm questions" are categorically bad.
joshuamorton 8y ago
This is such a cop out. It took millennia to invent 0. That doesn't mean that 0 is an exceedingly difficult concept to grasp.
- Aeolun 8y ago
  BFS as a name isn’t a difficult concept to grasp either.
  - joshuamorton 8y ago
    Neither BFS the concept, nor 0, the concept are particularly hard to understand. That's why I used the word "concept". If you disagree with that, I'd be interested in what you feel is exceedingly difficult about the breadth-first search algorithm to understand, or if you prefer, to explain why the time it takes to discover or first write down a concept is strongly correlated with its age. Consider that BFS was first published in 1945, while the turing machine was published almost 10 years prior. Is BFS an implicitly more complex concept than a turing machine? That seems like a strange argument to make, but I'm certainly interested.
- mehrdadn 8y ago
  I don't understand your comment. Was the parent suggesting BFS (or the like) is an exceedingly difficult concept to grasp? And if we're going to claim understanding BFS is like understanding zero, then wouldn't that just mean it's just as silly to complain about a question on BFS as it is to complain about a question on zero?
  - joshuamorton 8y ago
    Yes, my understanding is that the parent comment is complaining that since it took people with phds years to derive an algorithm for the first time, that we should never expect anyone to implement one in an interview. But, as with a concept like 0, making the cognitive leap to understanding that there should be a way to represent the lack of something is counterintuitive (indeed, consider Tony Hoare's billion dollar mistake. The "right" way to represent the absence of an object is a hard problem). However, once you've been exposed to it, it's not particularly challenging to rederive the necessary pieces. So yes, complaining about BFS is, imo, akin to complaining about being asked what the result of the arithmetic operation `35 - 12 - 23` is.
    - tzjmetron 8y ago
      Try and stop being an idiot. If you can.
    - SamReidHughes 8y ago
      And it's not like it took people with PhD's years to come up with BFS. You see people make a similar argument about Dijkstra's algorithm, when he picked it as an example of a particularly easy problem to solve.
- pishpash 8y ago
  I also use 0 every day. Do you use the BFS every day?
  - joshuamorton 8y ago
    Absolutely! I don't write the algorithm every day, but I interact graphs, trees, and other such structures on a daily basis in my job, and traversing them is something that I work on. Every time I run `rm -r` for example! I'm not asked to implement BFS every day, but the concept of a tree traversal is incredibly common. Even more explicitly, a lot of my recent work has been involving automated refactoring tooling, so there's lots of work with abstract syntax trees and control flow graphs, which are trees or graphs, and therefore need be traversed.
    - deleted 8y ago
      [deleted]
    - LaserToy 8y ago
      Ok, here is the question for you. I’m from gaming company, so it is relevant: given a matrix of 0s and 1s where 0 is a wall and 1 is an empty space, write function that finds path between provided coordinates. It should be suitable for real time game, no gooogling. Go
      - joshuamorton 8y ago
        I'm not clear what your point is. Sure you can come up with questions that are difficult or obscure. Yes I can probably implement a sufficiently fast maze solving algorithm, depending on exactly the environmental constraints (for ezple, given the problem as stated I'd assume something like a* using a precomputed mat heuristic would be fast for most mazes of reasonable size, I promise either didn't google that). But I wouldn't expect someone to answer that in an interview. Hell, I don't ask dynamic programming questions because I think they're too obscure and tricky (in the riddle way). My most common interview question involves a problem I've faced multiple times at work, has multiple valid solutions, and which I had to implement myself in various flavors before eventually coming across a relatively obscure standard library implemention. Although before I was able to identify that implementation, I had to solve the problem 2 or 3 times, see the different flavors, and identify the common themes and the theoretical underpinnings. I don't expect a candidate to do that without help, and most don't. But it sure sounds like you think that I'm somehow a bad engineer for asking a question that tests on the job skills I've needed, and the ability to break a problem down into component parts and implement them cleanly. But oh no, it uses an algorithm. It's a terrible question and I should just ask a question about software engineering that doesn't use any algorithms. Because obviously people will always be able to identify the standard library implemention (no candidate I've interviewed ever has, in fact). So colore dubious of this whole argument about whiteboarding questions being a bad test.
- fiblye 8y ago
  Cakes have existed for centuries and I'm sure most people on HN have made cakes at least once in their life. But put them in a room and say "Make us a 2 layer red velvet cake" with no access to a recipe, and you're not going to get a red velvet cake. It's an easy recipe that most people easily recognize with just a glance, and anyone could make it if they have a recipe on-hand or make red velvet cakes with abnormally high regularity. But most people, even if they're great chefs otherwise, will fail. Recognizing that a concept exists and implementing a relatively complex concept are different things.
  - dlp211 8y ago
    There are literally tv shows and contests where they do exactly this.
  - Godel_unicode 8y ago
    That's absolutely not the case. Many working pastry chefs (I just asked the two that I know) can do exactly what you're asking.
  - solipsism 8y ago
    This strikes me as an analogy that does not work in your favor. To know how to make a novel cake (not a recipe you've memorized), you need to have a good understanding of how the different ingredients interact. You probably even have a good sense of why they're there. Those seem like exactly the qualities you'd want to look for in a cake maker. Sure, they'll probably be going from recipes in their day to day job. But they'll be able to tweak them intelligently too.
    - fiblye 8y ago
      Most tech companies aren't looking for people to reimplement a dozen new variations of quicksort everyday. I mean, some companies really do need people who have countless algorithms ready to go in the back of their mind and the ability to apply them to new and interesting situations all the time, just like some people do need bakers who never need to consult a recipe and can devise new cakes for important events on a whim. But most restaurants are looking for someone who knows how to cook and use the tools in the kitchen. A chef who doesn't specialize in cakes will still probably be fine if you give them 5 minutes to look up a recipe and make one. In the same way, the overwhelming majority of tech job openings are in need of programmers with some degree of specialization and the ability to know how to look up what they don't know and the experience/knowledge to know how to put that info to use. The state of programming interviews for the past few decades has been to find people who've memorized all the "recipes" of CS. Most of the jobs, though, are about using some Javascript flavor of the month library and making it work with some other popular library and writing a bunch of interface code. Someone on the team might have to write an implementation of breadth-first search in their toy language, in which case they look up "bfs" on wikipedia and just rewrite the algo given. Companies are testing employees on how to make cakes when their job will be all about making burgers to order.
- LaserToy 8y ago
  I hope you are not going to be asked to implement consensus alg on the whiteboard. Took less time to invent than 0, but good luck writing it.
mrburkins 8y ago
That always struck me as odd, testing aptitude by memorizing others hard won knowledge. Who could really solve these problems, error free, on the spot with no prior exposure to underlying concepts?!?

Bfs is just one of examples. I can ask you a question you will not be able to answer without knowing the answer. There is a reason it took researchers years to find those optimal solutions

cornellwright 8y ago

Sure, you can come up with an algorithm question hard and obscure enough that no one will be able to answer it in the time given and no one will have bothered to memorize it because it's so obscure. That doesn't mean all "implement X algorithm questions" are categorically bad.

joshuamorton 8y ago

This is such a cop out. It took millennia to invent 0. That doesn't mean that 0 is an exceedingly difficult concept to grasp.

Aeolun 8y ago
BFS as a name isn’t a difficult concept to grasp either.
- joshuamorton 8y ago
  Neither BFS the concept, nor 0, the concept are particularly hard to understand. That's why I used the word "concept". If you disagree with that, I'd be interested in what you feel is exceedingly difficult about the breadth-first search algorithm to understand, or if you prefer, to explain why the time it takes to discover or first write down a concept is strongly correlated with its age. Consider that BFS was first published in 1945, while the turing machine was published almost 10 years prior. Is BFS an implicitly more complex concept than a turing machine? That seems like a strange argument to make, but I'm certainly interested.
mehrdadn 8y ago
I don't understand your comment. Was the parent suggesting BFS (or the like) is an exceedingly difficult concept to grasp? And if we're going to claim understanding BFS is like understanding zero, then wouldn't that just mean it's just as silly to complain about a question on BFS as it is to complain about a question on zero?
- joshuamorton 8y ago
  Yes, my understanding is that the parent comment is complaining that since it took people with phds years to derive an algorithm for the first time, that we should never expect anyone to implement one in an interview. But, as with a concept like 0, making the cognitive leap to understanding that there should be a way to represent the lack of something is counterintuitive (indeed, consider Tony Hoare's billion dollar mistake. The "right" way to represent the absence of an object is a hard problem). However, once you've been exposed to it, it's not particularly challenging to rederive the necessary pieces. So yes, complaining about BFS is, imo, akin to complaining about being asked what the result of the arithmetic operation `35 - 12 - 23` is.
  - tzjmetron 8y ago
    Try and stop being an idiot. If you can.
  - SamReidHughes 8y ago
    And it's not like it took people with PhD's years to come up with BFS. You see people make a similar argument about Dijkstra's algorithm, when he picked it as an example of a particularly easy problem to solve.
pishpash 8y ago
I also use 0 every day. Do you use the BFS every day?
- joshuamorton 8y ago
  Absolutely! I don't write the algorithm every day, but I interact graphs, trees, and other such structures on a daily basis in my job, and traversing them is something that I work on. Every time I run `rm -r` for example! I'm not asked to implement BFS every day, but the concept of a tree traversal is incredibly common. Even more explicitly, a lot of my recent work has been involving automated refactoring tooling, so there's lots of work with abstract syntax trees and control flow graphs, which are trees or graphs, and therefore need be traversed.
  - deleted 8y ago
    [deleted]
  - LaserToy 8y ago
    Ok, here is the question for you. I’m from gaming company, so it is relevant: given a matrix of 0s and 1s where 0 is a wall and 1 is an empty space, write function that finds path between provided coordinates. It should be suitable for real time game, no gooogling. Go
    - joshuamorton 8y ago
      I'm not clear what your point is. Sure you can come up with questions that are difficult or obscure. Yes I can probably implement a sufficiently fast maze solving algorithm, depending on exactly the environmental constraints (for ezple, given the problem as stated I'd assume something like a* using a precomputed mat heuristic would be fast for most mazes of reasonable size, I promise either didn't google that). But I wouldn't expect someone to answer that in an interview. Hell, I don't ask dynamic programming questions because I think they're too obscure and tricky (in the riddle way). My most common interview question involves a problem I've faced multiple times at work, has multiple valid solutions, and which I had to implement myself in various flavors before eventually coming across a relatively obscure standard library implemention. Although before I was able to identify that implementation, I had to solve the problem 2 or 3 times, see the different flavors, and identify the common themes and the theoretical underpinnings. I don't expect a candidate to do that without help, and most don't. But it sure sounds like you think that I'm somehow a bad engineer for asking a question that tests on the job skills I've needed, and the ability to break a problem down into component parts and implement them cleanly. But oh no, it uses an algorithm. It's a terrible question and I should just ask a question about software engineering that doesn't use any algorithms. Because obviously people will always be able to identify the standard library implemention (no candidate I've interviewed ever has, in fact). So colore dubious of this whole argument about whiteboarding questions being a bad test.
fiblye 8y ago
Cakes have existed for centuries and I'm sure most people on HN have made cakes at least once in their life. But put them in a room and say "Make us a 2 layer red velvet cake" with no access to a recipe, and you're not going to get a red velvet cake. It's an easy recipe that most people easily recognize with just a glance, and anyone could make it if they have a recipe on-hand or make red velvet cakes with abnormally high regularity. But most people, even if they're great chefs otherwise, will fail. Recognizing that a concept exists and implementing a relatively complex concept are different things.
- dlp211 8y ago
  There are literally tv shows and contests where they do exactly this.
- Godel_unicode 8y ago
  That's absolutely not the case. Many working pastry chefs (I just asked the two that I know) can do exactly what you're asking.
- solipsism 8y ago
  This strikes me as an analogy that does not work in your favor. To know how to make a novel cake (not a recipe you've memorized), you need to have a good understanding of how the different ingredients interact. You probably even have a good sense of why they're there. Those seem like exactly the qualities you'd want to look for in a cake maker. Sure, they'll probably be going from recipes in their day to day job. But they'll be able to tweak them intelligently too.
  - fiblye 8y ago
    Most tech companies aren't looking for people to reimplement a dozen new variations of quicksort everyday. I mean, some companies really do need people who have countless algorithms ready to go in the back of their mind and the ability to apply them to new and interesting situations all the time, just like some people do need bakers who never need to consult a recipe and can devise new cakes for important events on a whim. But most restaurants are looking for someone who knows how to cook and use the tools in the kitchen. A chef who doesn't specialize in cakes will still probably be fine if you give them 5 minutes to look up a recipe and make one. In the same way, the overwhelming majority of tech job openings are in need of programmers with some degree of specialization and the ability to know how to look up what they don't know and the experience/knowledge to know how to put that info to use. The state of programming interviews for the past few decades has been to find people who've memorized all the "recipes" of CS. Most of the jobs, though, are about using some Javascript flavor of the month library and making it work with some other popular library and writing a bunch of interface code. Someone on the team might have to write an implementation of breadth-first search in their toy language, in which case they look up "bfs" on wikipedia and just rewrite the algo given. Companies are testing employees on how to make cakes when their job will be all about making burgers to order.
LaserToy 8y ago
I hope you are not going to be asked to implement consensus alg on the whiteboard. Took less time to invent than 0, but good luck writing it.

mrburkins 8y ago

That always struck me as odd, testing aptitude by memorizing others hard won knowledge. Who could really solve these problems, error free, on the spot with no prior exposure to underlying concepts?!?