Optimizing a breadth-first search • Hacker News Board

Re: Optimizing a breadth-first search

#31

Post by gopalv » Mon, Jul 23, 2018, 8:42 PM UTC

stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

> (the graduates I've been interviewing in SF) ... can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms.

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.

Re: Optimizing a breadth-first search

#32

Post by stcredzero » Mon, Jul 23, 2018, 8:55 PM UTC

gopalv wrote: post #31

stcredzero wrote: post #15

Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name…

> (the graduates I've been interviewing in SF) ... can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than name-drop algorithms, and fall far short of being able to implement those algorithms. 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…

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

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.

Re: Optimizing a breadth-first search

#33

Post by taeric » Mon, Jul 23, 2018, 9:48 PM UTC

stcredzero wrote: post #24

taeric wrote: post #18

Earlier quoted context omitted.

I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. However, few could ever do things in seconds. Nor is there really any benefit in being able to solve something in seconds. 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 res…

I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. 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.

I get the impression my claim is getting distorted. And I don't know how to make it clear. :(

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.

Re: Optimizing a breadth-first search

#34

Post by taeric » Mon, Jul 23, 2018, 9:51 PM UTC

stcredzero wrote: post #26

taeric wrote: post #21

Earlier quoted context omitted.

I'd wager the bar wasn't as high back then as you think. Most people still wrote inefficient things. Lots of it. There is a hope that most of the inefficient things flat out stalled out due to needing to be much more frugal of resources, but I don't know of any data backing that. 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 negativ…

I'd wager the bar wasn't as high back then as you think. Most people still wrote inefficient things. Lots of it. Lots of those people who wrote inefficient things were the C students in Comp Sci. A lot of those people writing bad code were home-grown programmers who were completely missing pieces of knowledge. From what I saw as an undergrad, it wasn't the 3.75 GPA CS students who were doing those things. So, serious…

More assertions that I just don't know that I buy. I don't ultimately think you have to take my assertions as valid counterpoints, but as things currently stand, I don't think either of us have actually presented any data. I'm just not asking anyone to believe that things are truly different than they used to be.

I've similarly been doing interviews for upwards of 20 years now. There are some particularly bad interviews I've done recently, but there were some particularly bad ones I did towards the beginning of my career, as well. Worse, some of the senior engineers I used to be under were quite bad, all told. (Which does not take away from many of the ones I was with that were bloody amazing.)

Re: Optimizing a breadth-first search

#35

Post by spike021 » Mon, Jul 23, 2018, 11:57 PM UTC

stcredzero wrote: post #27

spike021 wrote: post #20

Earlier quoted context omitted.

>Something has happened to Comp Sci programs over the past 3 decades. Based on what's too small a sample size (the graduates I've been interviewing in SF) it seems like a very large number of graduates from CS programs with 3.75 GPAs or above, can't do much more than glue together libraries, can't practically design a system on their own, and if ever confronted with a graph theory problem, can't do much more than nam…

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 http://v.cx/2010/04/feynman-brazil-education

Wow, this article tells a pretty incredible story. Thanks for sharing! It definitely echoes exactly what I was thinking about.

Re: Optimizing a breadth-first search

#36

Post by stcredzero » Tue, Jul 24, 2018, 12:58 AM UTC

taeric wrote: post #33

stcredzero wrote: post #24

Earlier quoted context omitted.

I think you are using very rose colored glasses looking at the past. The best of the best could do that, likely. 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.

I get the impression my claim is getting distorted. And I don't know how to make it clear. :( 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…

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.

Incorrect. My point is that some high GPA undergrads don't seem to have the habit/ability to even think along those lines. Of course we aren't going to ask for a difficult and polished algorithm in an interview. We throw simple stuff at them, to see if they know how to approach a problem. There are some common problems which are trivially solvable by imply throwing BFS/DFS at them. These 3.75+ GPA wunderkinds will flub those! At least one HN commenter replied to one by saying they could solve it in a couple of days.

Not to mention, most solutions people give in seconds are at best a good starting position.

Too many of these supposed A students can't even get to that starting position.

I've literally seen folks that think someone should be able to write algorithms such as Knuth-Morris-Pratt in a standup interview.

No. What we ask is more along the lines of: Would this candidate be able to think through what would happen if they used DFS on this graph? And that is just about the hardest thing we'd ask.

Re: Optimizing a breadth-first search

#37

Post by stcredzero » Tue, Jul 24, 2018, 1:20 AM UTC

taeric wrote: post #34

stcredzero wrote: post #26

Earlier quoted context omitted.

I'd wager the bar wasn't as high back then as you think. Most people still wrote inefficient things. Lots of it. Lots of those people who wrote inefficient things were the C students in Comp Sci. A lot of those people writing bad code were home-grown programmers who were completely missing pieces of knowledge. From what I saw as an undergrad, it wasn't the 3.75 GPA CS students who were doing those things. So, serious…

More assertions that I just don't know that I buy. I don't ultimately think you have to take my assertions as valid counterpoints, but as things currently stand, I don't think either of us have actually presented any data. I'm just not asking anyone to believe that things are truly different than they used to be. I've similarly been doing interviews for upwards of 20 years now. There are some particularly bad intervi…

I don't ultimately think you have to take my assertions as valid counterpoints

Many of your supposed counterpoints are straw-man. No one is expecting someone to have memorized or to reinvent KMP or this algorithm or that. What we're looking at is basic understanding and conceptual tools.

I'm just not asking anyone to believe that things are truly different than they used to be.

But things are clearly different than they were years ago. The number of CS grads has fluctuated a lot, in response to increased investment and industry bubbles bursting. Things are clearly very different today than they were in the early 90's.

https://nces.ed.gov/programs/digest/d12/tables/dt12_349.asp

We also covered "gluing things together" in the early 90's. The concept was already very well worn even when I was a newly minted CS grad, with Jon Bentley discussing it in Programming Pearls using awk. The thing is this: We would also glue libraries together, but we did that while applying our generalist knowledge. It seems to me that there are a whole lot of CS grads who get through their entire undergrad education pretty much only doing that. Maybe that's all well and good, and they can accomplish many great things this way. However, it seems to me that much of the basic generalist knowledge is now mistakenly labeled as "specialist" and is needlessly missing from the general population.

Re: Optimizing a breadth-first search

#38

Post by taeric » Tue, Jul 24, 2018, 5:21 AM UTC

stcredzero wrote: post #36

taeric wrote: post #33

Earlier quoted context omitted.

I get the impression my claim is getting distorted. And I don't know how to make it clear. :( 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…

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. Incorrect. My point is that some high GPA undergrads don't seem to have the habit/ability to even think along those lines. Of course we aren't going to ask for a difficult and polished algorithm in an interview. We throw simple stu…

So I'm taking your point, at the moment, to be that you are getting exposed to more folks that seem less capable in basic interviews. Even at the higher education levels.

My priors would label this as just you getting more exposure to what is out there. Previously, you were likely mainly exposed to your peers. Did you personally perform more of the interviews in the past, or more in the present? At an absolute level, I would tend to agree that increasing the volume increases both good and bad. Where the contention seems to be, is if there is truly a lowering of the bar across the board, or if you are just personally exposed to more of the folks that can't make it?

And I confess I have no numbers. I am terribly optimistic and generally forgiving of interview gaffes.

Don't get me wrong, now that I do interviews, it has been somewhat baffling just how wrong some folks can be. The most troubling are the folks that seem genuinely clueless that they have done a poor job.

However, the "strawmen" I'm asking are not hypothetical. I've literally been asked some of those. My favorite was when I was asked what I knew was a de Bruijn cycle, but confessed I would be unable to code without reference. And even then it would take time. Interviewer insisted I try, and seemed to get frustrated that I didn't succeed. The very next interviewer basically asked me to do A*. Something I feel like I should be able to do, but quite frankly it has been a long time since I did those and I have grown used to reference material.

Similarly, I have been asked "how would you build snapchat/instagram" and "how would you build maps?" Both of which, I feel like I could have better answers for, but the truth is that I would start by trying to understand exactly how they are built today.

Re: Optimizing a breadth-first search

#39

Post by taeric » Tue, Jul 24, 2018, 5:22 AM UTC

stcredzero wrote: post #37

taeric wrote: post #34

Earlier quoted context omitted.

More assertions that I just don't know that I buy. I don't ultimately think you have to take my assertions as valid counterpoints, but as things currently stand, I don't think either of us have actually presented any data. I'm just not asking anyone to believe that things are truly different than they used to be. I've similarly been doing interviews for upwards of 20 years now. There are some particularly bad intervi…

I don't ultimately think you have to take my assertions as valid counterpoints Many of your supposed counterpoints are straw-man. No one is expecting someone to have memorized or to reinvent KMP or this algorithm or that. What we're looking at is basic understanding and conceptual tools . I'm just not asking anyone to believe that things are truly different than they used to be. But things are clearly different than…

(Just so it isn't completely lost, I basically merged my answer for this in the above branch. Realized it was both of us on both of these out croppings, didn't see the point in pretending it was two discussions. :) )

Re: Optimizing a breadth-first search

#40

Post by rrobukef » Tue, Jul 24, 2018, 7:59 AM UTC

jsnell wrote: post #12

frankmcsherry wrote: post #11

Earlier quoted context omitted.

It's a super interesting post, and I've no reason to think that iterative deepening would be better, just that it is designed to deal with exactly this problem. The lack of growth in novel states may invalidate its main hypothesis though (tree-like growth). 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…

Fair enough, and it's easy to test :) I made a non-iterative DFS, but hardcoded the maximum depth to the optimal solution. On a trivial puzzle that should take This is obviously not fully optimized code (whee, std::unordered_set). But fixing that won't help when we're off by 3-4 orders of magnitude. I think the shape of the search graph of this game just isn't well suited to any form of DFS, there are far too many al…

Thank you. It's interesting to see the explosion of states. You could add a cache (per search depth) to deduplicate states again. It will reduce small cycles and the used memory is easier to control.

Kudos for the encoding. 0.7 bits per state is dense.