Edit: for context, wasn't meant to be "zomg how you so dumb" so much as "everyone should also read, cause is relevant".
Totally happy to believe I'm wrong about that, though :)
The Python version seems to do DFS using function calls, and I could imagine this isn't the most performant way to do it. Also, the description implies that their DFS implementation retains state; not sure what to make of it, and not a Python reader:
> Depth-First should be a bit kinder to system memory, though it'll still chew up quite a bit remembering which game states we've seen before.
I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least.
EDIT: read your reply to the other user. Fair enough :)
You might see some interesting effects using a bloom filter and an IDDFS. It would turn the whole search probabilistic but might be fast enough that you could run it enough times to remove reasonable doubt.
The author probably spent some time writing the code, modifying and extending the algorithm. He wrote deduplication code, memory mapping etc. Wouldn't it be interesting to know how iterative deepening performs?
There are literally problems that were 1) once covered in freshman year, 2) could once be recognized and solved by CS grads in seconds, 3) stump recent CS graduates, 4) prompt HN commenters to say how they could solve it if given a few days, and 5) come up in conversation if you go to meetups and talk to people doing actual work.
How does this relate to BFS? It used to be that someone trained as a computer scientist would look at a data structure or a graph and start running some quick gedankenexperiments: What would happen if I tried to find that with DFS? What would happen if I tried to find that with BFS? Those aren't going to be suitable solutions for all problems, but it's a good place to start thinking. There seem to be a large number of recent grads who can't even get that far.
Ah, one of the pain points with companies in the Bay Area.
For the longest time one obvious, if not necessarily exclusive, problem with students who can achieve a 3.75 or higher GPA is that they tend to be much better at the rote memorization of concepts, but because they didn't necessarily "slog" through stuff, have some troubles, not try to just memorize formulas and algorithms, they don't have the ability to think through problems.
What about students in the 3.0 to 3.75 GPA range? Or are they considered "too dumb" to pass the resume filter you're using?
I think recruiting around here is targeted at "best and brightest" too much, and over-simplifies just the kind of people fit that qualifier.
I remember applying for internships while I was going to SJSU and many of the top companies in the area would have a drop down selection list of "which university did you attend?" and the list would only consist of the usual top UC's and top private schools.
I'm not saying actually smart people can't come from those universities, but when you're doing things like limiting a candidate search to 3.75 or greater GPAs, or filtering based on only "top" schools, then I think the issues you're describing are going to be much more immediate than otherwise.
Interestingly, to me, it seems our industry was dominated by people that got good at gluing things together. To a very large degree. We bemoan this when we talk about how much more responsive machines used to be, but I think there can be very little denying that computers do more.
Granted, I suspect I am at best one of the bad graduates you are referencing. :(
The fact that you are classifying actually learned something when we covered BFS/DFS Freshman year as being equivalent to "the best of the best" speaks volumes.
My claim is that some of these optimizations on BFS/DFS style questions were never something most people could effortlessly solve in a few seconds. Which is how I took the claim of the OP.
If it was only the identification that was supposed to be seconds, with solutions taking time, that is one thing. But even binary search was infamous for not having a bug free solution for many many years. (Unless I took an urban legend too literally, of course.)
Not to mention, most solutions people give in seconds are at best a good starting position. Just go look at how a typical sort is actually implemented. Much more involved than what you would want someone to do in a few seconds.
I've literally seen folks that think someone should be able to write algorithms such as Knuth-Morris-Pratt in a standup interview. Which is just bonkers to me.
I've also grown annoyed with interviews that are effectively, "how would you design google maps today?" Which really just comes down to have I already done that. At the least, studied it fairly in depth. Worse, the answer is almost certainly not much different than how it was built.
The idea that "computers are fast, my code just needs to work" is a really really horrible way to treat your users' devices. A whole host of similar ideas are now popular, and it's pretty obvious that it's because the industry is now dominated by people that are (just) good at gluing things together. This is a bad thing.
So, seriously, do you have data showing that the bar is lower? Or are you just performing selection and survivor bias to get such a negative view? (Similarly, am I doing the same to get a positive view?)
My main qualm is people that seem to hold incoming folks to the bar that they have today, without acknowledging the growth that was necessary for some of that. As a parent, I fully know my children will be better at most everything than I am. In time. Same for most of the younger generation coming out of college into the industry. Most are or will be better than I am. Pretty much full stop.
Interviewing people does not tell you the capabilities of people - interviews are very artificial processes.
I'm not exactly a computer scientist (or a recent graduate), but I work with tradeoffs every day, most of which are data derived, not problem derived & that is only visible from experiments on the data (sometimes across millions of ops).
However, what I really end up doing is actually different from just running experiments - I run the scale tests and go running while it runs.
I do my best thinking when I'm running - about a 10 minute mile pace in sunshine gives me my best ideas, perhaps it is a heart-rate thing.
And even when I have an idea, I will dig through researchgate for a couple of hours before I actually start pulling it apart (often, I find people have described the math which helps me think better) - like HyperLogLog used for IN() estimations.
Nobody's going to allow me to do any of those things in an interview.
Interviews are really about selecting people to hire, not about their abilities.
I don't think I'd know how to interview someone for your position.
I do my best thinking when I'm running
I've had similar experiences. Of course I'm not possessed by the idea that interviews are very good as a general mechanism. I've given allowances for nervousness and pressure. I certainly know what it's like to be on the other side of the table. Even allowing for all of those things, it leaves me wondering.
There may be some grads that have the problems that you describe but there are also many that have those skills. Look at the ICPC regional contests. Many students competing are very highly skilled in algorithms and hacking things together quickly. That does not always make them good employees.
https://www.pbs.org/newshour/economy/column-how-an-epidemic-...
There's a serious problem in the industry being driven by coding bootcamps; it's really sad to see universities being forced to stoop to compete.
Is that really the case, universities are trying to compete with bootcamps? I don't see much in the way of signs of that.
I hope this is a joke, although it's a little scary totalling up how much Chrome is chewing right now, with just one window and seven tabs open...
