8 ms·

Funny, I use this kind of thing all the time when I'm programming. I wrote a comment citing the pigeonhole principal to justify a test case not thirty minutes a

by saulrh 8y ago

Funny, I use this kind of thing all the time when I'm programming. I wrote a comment citing the pigeonhole principal to justify a test case not thirty minutes ago. And I'm not even doing anything wizardly or revolutionary, just improving some concurrency code in a random worker binary. As for your comment about "diversity of thought": These problems seem sterile when they're presented in the most general possible form with all the formal trappings. The subsequence problem is at the core of diff(1), for example, and it feels more interesting in some way to dig into that past reading and applying your diffs like usual. But if you try to present it as "it's diff(1)" you will only get people that already know what that means. "It's a simple spellchecker", "reassembling DNA", "disentangling two books that have been mixed together", etc, these specializations all introduce additional dependencies and restrict the availability of the lesson. Anyone can read "a string S and a set of words D". It may not be optimized for you, but who cares about what you think is boring or not? You already know this math. Personally, I gleefully soaked up everything my undergraduate algorithms classes offered, even the AVL trees and all that other random circles-on-a-whiteboard stuff, because I was learning something in its purest form. And if I needed more meat? Whatever I was learning from would have mentioned, as an aside, that it was also diff and DNA and spell-checking, and I could pick and choose from those as appropriate. Finally, would you have reacted anything like this if the page had been spat out by your favorite Ruby super hacker wizard greybeard man? If it'd been an artisan webpage hand-crafted in the hipsterest coffee shop in oregon? If it's been on microsoft's recruiting page?

SmirkingRevenge 8y ago
It would be interesting to know how much time and practice it took the inventors of many of these algorithms, to actually create them. When you think about it... that's basically what candidates are being asked to accomplish in these kinds of interviews, unless they have the algorithm (or a very similar one) memorized already. Would we be surprised to learn that most of the smart guys behind these algorithms probably didn't come up with them in 40-ish minutes on a chalk/white board?
- Alex3917 8y ago
  As an anecdote, Dr. Krebs had no idea what the Krebs cycle was without looking it up, even though students are expected to memorize it.
- keyanp 8y ago
  Good point! I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution. Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]: > Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute. The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :) [1]: http://cricca.disi.unitn.it/montresor/wp-content/uploads/2018/09/programmingpearls.pdf http://cricca.disi.unitn.it/montresor/wp-content/uploads/201... [2]: https://en.wikipedia.org/wiki/Maximum_subarray_problem https://en.wikipedia.org/wiki/Maximum_subarray_problem
  - Smaug123 8y ago
    Counteroffer: if you know that it's being asked in an interview, it's much easier to come up with a neat and elegant answer. The test-taker within me pattern-matches this problem to "interview question with a single-pass linear-time constant-space algorithm". Single-pass constant-space algorithms are so heavily constrained that they're much easier to find. The big hurdle for the maximum subarray problem is knowing that a single-pass constant-space algorithm exists; finding it under those conditions is not that hard. The original inventors of the algorithms you mention had a much harder job than an interview candidate does: they did not know what optimum to aim for.
  - 8y ago
seanmcdirmid 8y ago
What does the above problem have to do with the pigeon hole principle? I’m all for CS foundations, I learned the pigeon hole principle as an undergrad, I never used it (in work or during my phd) and have since forgotten it, but I’m glad I did that. But the above problem....just feels like a Googly interview question, whether it is just diff or not. What really gets me riled up is that these companies don’t care about my specialty or actual experience at all during the interview even if this is why they want to hire me at all in the first place. Nope, it’s all brain teaser coding questions that have nothing to do with what they would actually want me to do if hired. I get why they do it (one size fit all interview process), but I don’t think it is at all better. There are now whole undergrad courses at universities like Stanford devoted to gaming the interview process at google and Facebook and other big techs. I don't think this is desirable or sustainable.
- nradov 8y ago
  This seems related to Goodhart's law: "When a measure becomes a target, it ceases to be a good measure." If the hiring process for some tech companies has become so dysfunctional that they actually consider brain teaser coding questions to be meaningful then we should expect that competitors with more results oriented hiring processes will eventually beat them in the market.
  - seanmcdirmid 8y ago
    Perhaps the tenacity and work ethic needed to study a couple of months for an interview selects for people who would do the job well anyways? Maybe that is what it means to be Googly as a culture fit? Anyways, practicing solving clever small programming problems at least isn’t boring (though I’m beginning to burn out on it), it reminds me of prepping for a high school or ACM programming contest. As long as it eliminates enough false positives, they’ll keep up with it. It isn’t just if you can solve these problems, but can you also write straight lines of text on a white board? Also, do it while talking and and standing on one foot at the same time.
    - SmirkingRevenge 8y ago
intern4tional 8y ago
You should include the fact that you work at Google (cause you do, and your response is not completely honest without that disclaimer). The parent's concern was that this is Google focused, and your response doesn't seem to disprove it in any way.
- cmrdporcupine 8y ago
  FWIW I work at Google and despise these kind of interview questions and think they have 0 relevancy to my job -- until they do, and then I look them up and research them -- which BTW is not a skill that this interview style tests for. It's to the point where I've done interview training here twice and both times thrown up my hands and chosen not to interview, because I can't imagine giving an interview that I myself would just walk out of.
  - jsolson 8y ago
    So don't give that sort of interview; give one you wouldn't walk out of where, if it goes well, you'll be able to write a compelling argument about why the candidate should work at Google, and if it doesn't go well you'll be able to write about where the gaps are. Feel free to ping me on IM (username is in my profile) if you'd like to talk about how to do this in a way that helps hiring committee make informed decisions.
    - cmrdporcupine 8y ago
      That simply wouldn't be permitted at Google. There's an accepted and normative form of interview and everything has to be documented meticulously.
      - jsolson 8y ago
        This conversation would be better continued over corp hangouts or e-mail -- as I said, my username is in my profile.
  - webmaven 8y ago
nilkn 8y ago
To offer an alternative viewpoint: I have a degree in pure mathematics from a highly ranked institution. I published research as an undergraduate. I went to multiple REUs. I participated in the Putnam and similar competitions. I read CLRS in 9th grade and didn't even bother taking an algorithms course in college. But even I find that these sorts of questions are more gatekeeping than anything else. That's not a perspective that I had when I was coming straight out of college. The revelation for me came from working at a successful company that manages to hire great developers and build great teams without needing to ask these sorts of questions. It turns out that these sorts of problems are relatively rare in real software development work, and many developers who wouldn't necessarily ace them in 40 minutes under tightly controlled conditions can nevertheless come up with perfect solutions in a normal work context, should the problem actually arise. The reality is this sort of question selects for personality just as much as it does programming ability. It selects for the sort of person who likes puzzles and brainteasers and spends a lot of time immersing themselves in that culture. It reinforces a lot of cultural stereotypes deeply embedded in the programming world. There's also a lot of perspective to be gained by working outside of a major technology hub. If developers are rarer to come by, if you're in any sort of hiring position you realize just how careless it would be for you to throw away a candidate because they didn't ace this sort of question. It'd sort of be like a family without much food throwing out all their bread because they saw a fly land on it. Relying 100% on this sort of question reflects an overabundance of applicants more than it does any underlying universal quality in the interviewing strategy. Beyond this, I think there's a little irony in your comment. You mention diff(1), but who's to say the author(s) of that tool would've necessarily solved this problem on the spot? You're actually making that assumption, which I find to be unjustified. There's an entire class of thinker and problem solver you're ignoring -- the deep thinkers, the great ponderers who soak their mind so thoroughly in a problem that they come out with something wonderful. But you might need to give them some space and a day or two.
- EnderWT 8y ago
  I interview for my company, too, and don't ask these kinds of algorithm questions because the reality is these problems aren't typical of day-to-day work for the positions we are hiring for. I'm interested to know what your interview process is. If you wouldn't mind sharing, how does the interview process work at your company?
pathseeker 8y ago
>Finally, would you have reacted anything like this if the page had been spat out by your favorite Ruby super hacker wizard greybeard man? If it'd been an artisan webpage hand-crafted in the hipsterest coffee shop in oregon? If it's been on microsoft's recruiting page? You work for Google and you want to defend the org, we get it. Get over yourself. This really detracts from the rest of your post so I would consider removing it if you can still edit. The entire point was that testing for these low-level fundamentals really has nothing to do with software engineering. It would be like hiring civil engineers based on being able to do some equations from memory that they would normally reference a book (or the Internet) for in real life. Not only is it not measuring their ability to engineer so it lets terrible engineers in, but it also rejects amazing engineers who don't have optimal solutions to things memorized that you would almost never be using in day-to-day engineering.
- saulrh 8y ago
  I got pissed off at the "Google this, Google that" sentence because it's bad faith debate technique. The point could have been made just as well with a comment about company towns or cyberpunk megacorporations. The hysterical repetition contributes nothing to the part of the argument that matters in real life and serves solely to incite unthinking, involuntary anger. And, yeah, the complaint probably should have gone in its own post, and had some more explanation. Double-posting still feels wrong somehow. > The entire point was that testing for these low-level fundamentals really has nothing to do with software engineering. It would be like hiring civil engineers based on being able to do some equations from memory that they would normally reference a book (or the Internet) for in real life. You don't ask those questions when interviewing a civil engineer because a licensed civil engineer has passed the FE and PE, eight-hour open-note tests that permit only basic scientific calculators. So not only are civil engineers tested on their ability to handle the basics from memory - you know as well as I do that writing the notes for a serious-business open-notes test is half the difficulty all by itself - they're tested in conditions which impose far more constraints and pressure. I don't think I've done a single interview where I didn't go back and forth with the interviewer to get hints and clarify requirements. Eight hours locked in a room with pencil and paper, fuck that. I agree that Google's interview is stupid, but I've gotten into this argument dozens of times over the last decade and every time I try to think of an alternative I come up with something that has its own weaknesses. For example, one of the reasons I went for a CS degree instead of a software engineering degree is that it's absurdly difficult to pick up formal CS theory on the job but you'll be learning software engineering every day. Take-home tests are unscalable and derided as insulting wastes of applicants' time. Contract-to-hire is too easy for employers to abuse. I can't even imagine how badly a licensing test for CS/software engineering would go. The best I can come up with is to do the same style of interview but on a computer. Which I think Google might even do these days, but I went with the whiteboard one because I don't want that much riding on my laptop working that day and I run at a greater disadvantage coding on a loaner laptop than I do on the whiteboard.

by saulrh 8y ago

SmirkingRevenge 8y ago

It would be interesting to know how much time and practice it took the inventors of many of these algorithms, to actually create them. When you think about it... that's basically what candidates are being asked to accomplish in these kinds of interviews, unless they have the algorithm (or a very similar one) memorized already. Would we be surprised to learn that most of the smart guys behind these algorithms probably didn't come up with them in 40-ish minutes on a chalk/white board?

Alex3917 8y ago
As an anecdote, Dr. Krebs had no idea what the Krebs cycle was without looking it up, even though students are expected to memorize it.
keyanp 8y ago
Good point! I ran into this case studying for interviews a while ago. The "maximum subarray problem"[1] is a common interview question, you are generally expected to be able to come up with the O(n) solution. Well has a great passage about the origins of the problem and how multiple excellent algorithmists could not improve on a O(n^2) run time[2]: > Grenander observed that the cubic time of Algorithm 1 was prohibitively slow, and derived Algorithm 2. In 1977 he described the problem to Michael Shamos of UNILOGIC, Ltd. (then of Carnegie-Mellon University) who overnight designed Algorithm 3. When Shamos showed me the problem shortly thereafter, we thought that it was probably the best possible; researchers had just shown that several similar problems require time proportional to N log N. A few days later Shamos described the problem and its history at a seminar attended by Jay Kadane (a statistician at Carnegie-Mellon University), who designed the linear-time Algorithm 4 within a minute. The solution is elegant and seemingly "obvious" after looking at it, but good luck coming up with it yourself :) [1]: http://cricca.disi.unitn.it/montresor/wp-content/uploads/2018/09/programmingpearls.pdf http://cricca.disi.unitn.it/montresor/wp-content/uploads/201... [2]: https://en.wikipedia.org/wiki/Maximum_subarray_problem https://en.wikipedia.org/wiki/Maximum_subarray_problem
- Smaug123 8y ago
  Counteroffer: if you know that it's being asked in an interview, it's much easier to come up with a neat and elegant answer. The test-taker within me pattern-matches this problem to "interview question with a single-pass linear-time constant-space algorithm". Single-pass constant-space algorithms are so heavily constrained that they're much easier to find. The big hurdle for the maximum subarray problem is knowing that a single-pass constant-space algorithm exists; finding it under those conditions is not that hard. The original inventors of the algorithms you mention had a much harder job than an interview candidate does: they did not know what optimum to aim for.
- 8y ago

seanmcdirmid 8y ago

What does the above problem have to do with the pigeon hole principle? I’m all for CS foundations, I learned the pigeon hole principle as an undergrad, I never used it (in work or during my phd) and have since forgotten it, but I’m glad I did that. But the above problem....just feels like a Googly interview question, whether it is just diff or not. What really gets me riled up is that these companies don’t care about my specialty or actual experience at all during the interview even if this is why they want to hire me at all in the first place. Nope, it’s all brain teaser coding questions that have nothing to do with what they would actually want me to do if hired. I get why they do it (one size fit all interview process), but I don’t think it is at all better. There are now whole undergrad courses at universities like Stanford devoted to gaming the interview process at google and Facebook and other big techs. I don't think this is desirable or sustainable.

nradov 8y ago
This seems related to Goodhart's law: "When a measure becomes a target, it ceases to be a good measure." If the hiring process for some tech companies has become so dysfunctional that they actually consider brain teaser coding questions to be meaningful then we should expect that competitors with more results oriented hiring processes will eventually beat them in the market.
- seanmcdirmid 8y ago
  Perhaps the tenacity and work ethic needed to study a couple of months for an interview selects for people who would do the job well anyways? Maybe that is what it means to be Googly as a culture fit? Anyways, practicing solving clever small programming problems at least isn’t boring (though I’m beginning to burn out on it), it reminds me of prepping for a high school or ACM programming contest. As long as it eliminates enough false positives, they’ll keep up with it. It isn’t just if you can solve these problems, but can you also write straight lines of text on a white board? Also, do it while talking and and standing on one foot at the same time.
  - SmirkingRevenge 8y ago

intern4tional 8y ago

You should include the fact that you work at Google (cause you do, and your response is not completely honest without that disclaimer). The parent's concern was that this is Google focused, and your response doesn't seem to disprove it in any way.

cmrdporcupine 8y ago
FWIW I work at Google and despise these kind of interview questions and think they have 0 relevancy to my job -- until they do, and then I look them up and research them -- which BTW is not a skill that this interview style tests for. It's to the point where I've done interview training here twice and both times thrown up my hands and chosen not to interview, because I can't imagine giving an interview that I myself would just walk out of.
- jsolson 8y ago
  So don't give that sort of interview; give one you wouldn't walk out of where, if it goes well, you'll be able to write a compelling argument about why the candidate should work at Google, and if it doesn't go well you'll be able to write about where the gaps are. Feel free to ping me on IM (username is in my profile) if you'd like to talk about how to do this in a way that helps hiring committee make informed decisions.
  - cmrdporcupine 8y ago
    That simply wouldn't be permitted at Google. There's an accepted and normative form of interview and everything has to be documented meticulously.
    - jsolson 8y ago
      This conversation would be better continued over corp hangouts or e-mail -- as I said, my username is in my profile.
- webmaven 8y ago

nilkn 8y ago

To offer an alternative viewpoint: I have a degree in pure mathematics from a highly ranked institution. I published research as an undergraduate. I went to multiple REUs. I participated in the Putnam and similar competitions. I read CLRS in 9th grade and didn't even bother taking an algorithms course in college. But even I find that these sorts of questions are more gatekeeping than anything else. That's not a perspective that I had when I was coming straight out of college. The revelation for me came from working at a successful company that manages to hire great developers and build great teams without needing to ask these sorts of questions. It turns out that these sorts of problems are relatively rare in real software development work, and many developers who wouldn't necessarily ace them in 40 minutes under tightly controlled conditions can nevertheless come up with perfect solutions in a normal work context, should the problem actually arise. The reality is this sort of question selects for personality just as much as it does programming ability. It selects for the sort of person who likes puzzles and brainteasers and spends a lot of time immersing themselves in that culture. It reinforces a lot of cultural stereotypes deeply embedded in the programming world. There's also a lot of perspective to be gained by working outside of a major technology hub. If developers are rarer to come by, if you're in any sort of hiring position you realize just how careless it would be for you to throw away a candidate because they didn't ace this sort of question. It'd sort of be like a family without much food throwing out all their bread because they saw a fly land on it. Relying 100% on this sort of question reflects an overabundance of applicants more than it does any underlying universal quality in the interviewing strategy. Beyond this, I think there's a little irony in your comment. You mention diff(1), but who's to say the author(s) of that tool would've necessarily solved this problem on the spot? You're actually making that assumption, which I find to be unjustified. There's an entire class of thinker and problem solver you're ignoring -- the deep thinkers, the great ponderers who soak their mind so thoroughly in a problem that they come out with something wonderful. But you might need to give them some space and a day or two.

EnderWT 8y ago
I interview for my company, too, and don't ask these kinds of algorithm questions because the reality is these problems aren't typical of day-to-day work for the positions we are hiring for. I'm interested to know what your interview process is. If you wouldn't mind sharing, how does the interview process work at your company?

pathseeker 8y ago

>Finally, would you have reacted anything like this if the page had been spat out by your favorite Ruby super hacker wizard greybeard man? If it'd been an artisan webpage hand-crafted in the hipsterest coffee shop in oregon? If it's been on microsoft's recruiting page? You work for Google and you want to defend the org, we get it. Get over yourself. This really detracts from the rest of your post so I would consider removing it if you can still edit. The entire point was that testing for these low-level fundamentals really has nothing to do with software engineering. It would be like hiring civil engineers based on being able to do some equations from memory that they would normally reference a book (or the Internet) for in real life. Not only is it not measuring their ability to engineer so it lets terrible engineers in, but it also rejects amazing engineers who don't have optimal solutions to things memorized that you would almost never be using in day-to-day engineering.

saulrh 8y ago
I got pissed off at the "Google this, Google that" sentence because it's bad faith debate technique. The point could have been made just as well with a comment about company towns or cyberpunk megacorporations. The hysterical repetition contributes nothing to the part of the argument that matters in real life and serves solely to incite unthinking, involuntary anger. And, yeah, the complaint probably should have gone in its own post, and had some more explanation. Double-posting still feels wrong somehow. > The entire point was that testing for these low-level fundamentals really has nothing to do with software engineering. It would be like hiring civil engineers based on being able to do some equations from memory that they would normally reference a book (or the Internet) for in real life. You don't ask those questions when interviewing a civil engineer because a licensed civil engineer has passed the FE and PE, eight-hour open-note tests that permit only basic scientific calculators. So not only are civil engineers tested on their ability to handle the basics from memory - you know as well as I do that writing the notes for a serious-business open-notes test is half the difficulty all by itself - they're tested in conditions which impose far more constraints and pressure. I don't think I've done a single interview where I didn't go back and forth with the interviewer to get hints and clarify requirements. Eight hours locked in a room with pencil and paper, fuck that. I agree that Google's interview is stupid, but I've gotten into this argument dozens of times over the last decade and every time I try to think of an alternative I come up with something that has its own weaknesses. For example, one of the reasons I went for a CS degree instead of a software engineering degree is that it's absurdly difficult to pick up formal CS theory on the job but you'll be learning software engineering every day. Take-home tests are unscalable and derided as insulting wastes of applicants' time. Contract-to-hire is too easy for employers to abuse. I can't even imagine how badly a licensing test for CS/software engineering would go. The best I can come up with is to do the same style of interview but on a computer. Which I think Google might even do these days, but I went with the whiteboard one because I don't want that much riding on my laptop working that day and I run at a greater disadvantage coding on a loaner laptop than I do on the whiteboard.