Is BFS really that hard, especially if the interviewer is willing to talk it out with you and doesn't care a lot about finding the most efficient solution possible?
I've been out of college more than 10 years now, do a mix of hardware and software (so am not coding all day everyday) and I can hack together algorithms like BFS if I spend a couple of minutes thinking about it.
I get that there are many awful interviewers out there and that hiring is pretty broken, but BFS seems like a pretty reasonable interview question, so long as the interviewer talks through what it actually needs to do and isn't only looking for a memorized answer. The question is well contained, doesn't require the candidate to know any specific API or framework, and can be implemented in pretty much any language. Probably the biggest downside to it is it's such a common question that many candidates study it ahead of time which makes it a worse filter.
You and a lot of other commenters are getting hung up on the BFS example. It's just that - an example. There are dozens of algorithms that are "common" enough to be asked about and diminishing returns to having them all memorized.
Except all of these questions can be grouped into a category of the same kinds of problem and it is in fact spending time to find out that pattern and which category from sliding window, nested intervals, recursion and dynamic programming it belongs to
Sure, but that's my point. So long as the interviewer is telling you what they'd actually like you to do, you should be able to just derive the algorithm you need to do it. At some point the algorithms become difficult enough (particularly if you add lots of constraints like efficiency) that it's pretty unreasonable to expect that in an interview though, and at that point it's a bad question.
Rather than memorizing a thousand algorithms, I generally focus on being able to solve problems simply, quickly, and elegantly, which will help in actually doing most jobs.
You're still not getting it. Even for BFS, which is not a hard problem, the current state of the market is that enough people have memorized the BFS recipe so that the interview doesn't allocate much of any time to it. You're not going to have/be given time to "just derive the algorithm" or "solve problems simply, quickly, and elegantly." You're competing against rote speed, which, if you don't implement BFS all day or haven't recently done interview prep, you don't have and you're definitely going to fail.
I've heard people actually defend these useless interviews on correlation grounds, like people who are docile, follow the herd, and "prepare" are good hard-working workers who also tend to have done well in school or look polished in other aspects of life. That's what these interviews are really looking for. So, if you're not a well known expert, suck it up, be a servile cog and follow the script.
It seems like there might be a middle ground, like being willing to play the game, that doesn't imply being "a servile cog?"
The trick seems to be knowing when the game is worth playing. There are certainly situations where competition is too fierce and requires too much preparation, so it's not worth doing if you don't really enjoy the game.
I'm not sure getting hired at a large tech firm is quite that competitive, though? They do hire lots of people all the time.
My first reaction when inplementing anything more than a very simple algorithm is to google the best way to do it.
Of course, I could probably come up with a way to do it by myself. I could probably even come up with an efficient way if I spent an afternoon/day on it.
But why do that when I can google it, and get 3 blog posts and 2 stack overflow answers detailing the different options and the trade offs between them, most likely even with an implementation I can base mine off of?
That's why these interview situations are stupid. They're like school where copying is cheating, whereas in real-world situations copying is a great way of doing something.
> But why do that when I can google it, and get 3 blog posts and 2 stack overflow answers detailing the different options and the trade offs between them, most likely even with an implementation I can base mine off of?
A lot of resources out there are wrong, inaccurate, or not reasonable for your particular context, and it requires a reasonable amount of algorithmic intelligence to be able to sniff out what's appropriate.
If I had a dollar for every high-upvoted SO post that misstates a problem or doesn't offer proper caveats... but I can make that judgment because I've already thought about a related problem in the past.
It's like asking why one should learn how to write properly when Grammarly and spell checkers exist, or why mental arithmetic is useful when we have calculators—at some point those your tools will be inappropriate or unavailable. Search tools are force multipliers, not replacements for personal knowledge and intuition.
> A lot of resources out there are wrong, inaccurate, or not reasonable for your particular context, and it requires a reasonable amount of algorithmic intelligence to be able to sniff out what's appropriate.
Right, and having that algorithmic intelligence is key part of me being a good developer. But testing how someone implements an algorithm in time-scarce circumstances is not a good test of that kind of intelligence because it is likely to favour people who have been exposed to that particular algorithm before (even if they only rote-learnt information about it - as many interviewees seem to do in practice) over people who have the capability to think deeply and reason correctly about it, but have not previously been exposed to that problem.
I'm a data scientist, and google asked me to sum all values of nodes at each height of a tree. I had to implement the tree, bfs, and the algo (which was easy once you have bfs) in a 25 minutes, minus any talky time.
BFS is not something I thought about much in the last 5 years, and quite frankly could care less about. I got stuck when I knew I needed 'something' to finish implementing BFS, but couldn't remember and the google interviewer offered no help. What I couldn't remember was the queue.
>I'm a data scientist, and google asked me to sum all values of nodes at each height of a tree. I had to implement the tree, bfs, and the algo (which was easy once you have bfs) in a 25 minutes, minus any talky time.
THIS is the problem. The (unreasonably) timed nature of the exercise means that the only people that will do well are the people that prep heavily for this specific skill, in much the same way that people about to take the LSAT are likely to do better than it than actual fucking lawyers with proven experience.
Now take this analogy one step further: why aren't lawyers asked stupid timed LSAT questions at every job interview? Because they take a really challenging professional exam called the bar, which is a strong base level guarantee of actual knowledge and competence. Software Eng. have been fighting this kind of credentialing because somehow tech is "top innovative" for such standards. Hence the status quo, and why companies like TripleByte see opprtunity.
> Now take this analogy one step further: why aren't lawyers asked stupid timed LSAT questions at every job interview?
Because which law school they went to is on their resumé and the average LSAT scores for each school are trivially available, tracking very, very closely with school prestige.
Time (and being watched) do make it very unrealistic, but the other thing missing is that programming now is not like in the 1970's, you don't need to memorize much of anything. If you forget something, you look it up, it takes 30 seconds to remind yourself, "oh, yeah, the queue", and then you go. Testing if you can do it without looking it up is not testing the skills you actually need in order to code well.
you are right about any tree traversal would have done, but its not a lot of time and if you end up stuck you dont have a lot of time to backtrack.
a lot of great data scientists dont even know how to use python, let alone implement a tree and tree traversal. there is so much more interesting and pertinent stuff I spend my cycles on learning / keeping in my head than undergrad cs bs.
If the interviewer is willing to talk it out with you, then it is totally a different situation. But, it came up in a recent other HN discussion on tech interviews, and it is an example of something that, if you memorized it, would have a vanishingly small improvement in your ability to get the job done.
But, if you explain what it is in words, and have them whiteboard how to turn those words into pseudocode or somesuch, then it could be a appropriate, sure.
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
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.
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.
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.
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.
But an algorithm or more generally algorithmic thinking is not a collection of rote memories. It's concepts that can be applied broadly. Much in the same way that I'd expect a pastry chef to be able to cook a 2 layer red velvet cake because they know that a red velvet cake is just chocolate, and a 2 later cake is just 2 one layer sheets with icing between. Someone who understands a relatively small set of fundamentals well will be able to perform as well or better than someone who spends weeks memorizing every cake in the dictionary.
I disagree. I don’t know based on what you are making claims, but based on my anecdotical experience knowing fundamentals help low level coders to pass interview but has little to do with performing well. Based on my experience (currently responsible for a huge chunk of a major gaming platform, with hundreds millions users), inflexibility, emotional immaturity, inability to think outside of the box, inability to listen and admit failures, lack of emphaty, not understanding basics of sales(to sell own ideas) are major things that contribute to a bad performance reviews.
Our strongest engineers will not pass google interview without preparation (me included) and it is telling. Especially given the fact that we have higher profits per employee than google (we know what we are doing)
>Especially given the fact that we have higher profits per employee than google (we know what we are doing)
I'm dubious of this claim. Google/Alphabet has a PPE of ~$150,000. Activision-Blizzard has a PPE of ~$33,000, EA had ~$95,000, and Ubisoft ~$15000. I think the only possible major game studios who could meet your claim are Epic or maybe Valve. Unfortunately, those numbers aren't public. So I'm going to assume you work on Steam, since Epic's new platform is likely too recent to have lots of users, and also I don't think it was competently designed.
(the other thing is that this metric isn't particularly meaningful. Google invests a huge amount in unprofitable things with the goal of profits 5 or 10 years down the line. Google devotes thousands of engineers and billions of dollars to things it knows aren't profitable. That doesn't make Google more or less competent, it just implies different priorities than one that's entirely driven by immediate returns).
>Based on my experience (currently responsible for a huge chunk of a major gaming platform, with hundreds millions users), inflexibility, emotional immaturity, inability to think outside of the box, inability to listen and admit failures, lack of emphaty, not understanding basics of sales(to sell own ideas) are major things that contribute to a bad performance reviews.
All of these are important, but they only become important once you have the baseline level of competence. If you have two equally competent people, then yes indeed the softer skills like flexibility, creativity, humility, and communication skills start to matter, and eventually they matter a lot. But those are only good things if you assume a baseline level of competence.
Consider two options. One is that you screen solely for competence. You get only competent engineers along a wide range of interpersonal/soft skills. Some can grow into leadership roles, some can't (or at least it takes longer). But even the most convincing, best "salesperson" has great engineering talent. Then the alternative: that great salesperson is a bad engineer. The ideas they promote aren't always good ones, sometimes they're bad. That's not just "not good", its actively harmful.
>Our strongest engineers will not pass google interview without preparation (me included) and it is telling.
What does it tell? You seem to be suggesting that Google is optimizing badly, and that's possible. But that is by no means the only conclusion. Here's an alternative: "The most profitable things are not always the most technically challenging". Every once in a while you'll see people on HN commenting about how they wired up a shopify store that provides some significant passive income. That's not challenging. It would take an average engineer a week to do, if that. It's still profitable. But that doesn't make you qualified to work at Google (or Valve).
Maybe there’s a problem with which computer science is being taught if it’s so difficult for so many people to derive those solutions from fundamentals, and instead have to resort to brute force pattern memorization through Cracking the Coding Interview and Leetcoding.
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?
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.
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.
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.
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
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.
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.
I've been out of college more than 10 years now, do a mix of hardware and software (so am not coding all day everyday) and I can hack together algorithms like BFS if I spend a couple of minutes thinking about it.
I get that there are many awful interviewers out there and that hiring is pretty broken, but BFS seems like a pretty reasonable interview question, so long as the interviewer talks through what it actually needs to do and isn't only looking for a memorized answer. The question is well contained, doesn't require the candidate to know any specific API or framework, and can be implemented in pretty much any language. Probably the biggest downside to it is it's such a common question that many candidates study it ahead of time which makes it a worse filter.