"Let's try again," said Severus. "Potter, where would you look if I told you to find me a bezoar?"
"That's not in the textbook either," Harry said, "but in one Muggle book I read that a trichinobezoar is a mass of solidified hair found in a human stomach, and Muggles used to believe it would cure any poison -"
"Wrong," Severus said. "A bezoar is found in the stomach of a goat, it is not made of hair, and it will cure most poisons but not all."
"I didn't say it would, I said that was what I read in one Muggle book -"
"No one here is interested in your pathetic Muggle books. Final try. What is the difference, Potter, between monksblood and wolfsbane?"
That did it.
"You know," Harry said icily, "in one of my quite fascinating Muggle books, they describe a study in which people managed to make themselves look very smart by asking questions about random facts that only they knew. Apparently the onlookers only noticed that the askers knew and the answerers didn't, and failed to adjust for the unfairness of the underlying game. So, Professor, can you tell me how many electrons are in the outermost orbital of a carbon atom?"
Knowledge of folklore is not an accurate judge of a person's ability by any means. You are effectively ruling out anyone who learned to program in a language other than English, for instance.
But even if English is the language they learned to program in, expecting them to have read the same books as you is silly. There are so many programming books out that there that it boggles the mind to pick any one and expect them to have read it. Worse, to have read it and memorized every algorithm in it.
Programming is about completing tasks, not about memorizing everything in existence.
And this is coming from someone who finds memorization very, very easy, especially when the data to memorize is an algorithm.
It's an extra filtering mechanism for people who think they can afford to be picky.
I don't think it's meant to be universally applicable.
I'm only situationally in favor of this kind of thing, and I'd rather be a footnote/tilt factor than an actual bannable issue in a hiring process.
I've got a cursory familiarity with unix/hacker culture, but I don't think I would pass a Google-interview-esque history lesson even if I was able to ace that programming language test that went around earlier this week.
Edit:
I think it's worth mentioning here that there are no accurate methods of measuring competency in programming save for actually battle-testing them.
I do not know the name Bentley, and I have never heard the phrase "maximum sum subsequence", but given the context in the problem statement, I think I understand what was intended. Seems kinda silly to bring up this notion of "programming folklore".
I was once asked at a job about what OOP design patterns I knew. Design patterns are folklore (and mythology). At the time, I rattled off about three names to satisfy the interviewer, but nobody at my previous employer was busy memorizing names in a random popular book. I admitted as much. The employer hired me (probably not because of my lack of design pattern lingo). The term "design patterns" did not come up in my coursework because it was invented right after I graduated. ;) If a future employer asks me about design patterns, I will happily respond, "Design patterns reveal a language that lacks adequate abstraction features. I do not study design patterns, at least as defined by Fowler and company, because they have no justification in robust software design." Of course, folklore would have it that we should know this answer by now, so we see an example where even the accepted parts of "programming folklore" changes over time.
Design patterns, at least as defined by Fowler and company, ... have no justification in robust software design.
I don't particularly venerate the concept of design patterns, nor would I bother asking about them during an interview. But could you justify this statement?
Conversely, we can think of this as a rather poor filtering technique, because it grants an a nearly automatic pass to anyone who happens to have read any of the popular programming books (or blogs) where the "problem" is presented in easily digestible form, is presented as an "interesting" problem, and it's known that a tractable and optimal solution exists.
A much more important (and deeper) skill is to be able to solve (or reasonably approach) problems they have never seen. And an even more important and deeper skill than that is the ability to recognize algorithmic problems embedded "in the wild" (in naturally occurring business contexts), and to tell the interesting ones from the non-interesting ones (and the trivial from the hard... and among the hard, the plausibly solvable ones from the intractable rabbit holes) without the imprimatur of having someone from a place like Google or MIT telling you that they're "interesting" problems (let alone tractably solvable).
Of course, this kind of skill is much, much harder to test for -- if it can be tested for in the awkward setting of a tech interview at all.
Shipping is only valuable once: The first time they ship.
Every time after that, they could be boiling your code into a morass of blood, sweat and Jolt, weaving the Cthulhu pattern around your other Engineers' souls.
Ultimately, if you hire someone who ships, makes your code awful, pisses off your other engineers, doesn't document then chuffs off leaving you with a turd of an app and no-one to work on, their shipping only bought you N releases. A better engineer might have bought you <N releases... But prepared you for >N in the future.
programmingpraxis makes a comment in the latest post on Maximum Sum Subsequence:
"any programmer who doesn’t know about the solution will likely fail the interview, on the theory that if he isn’t at least interested enough in his profession to read Bentley [Programming Pearls], he isn’t interested enough in his profession to work for me."
In a follow-up comment:
"I still think a candidate not versed in the programming folklore will be less productive than one who is, and thus less suitable for hiring."
Is this a good or valid criteria for judging a programmer's abilities or future abilities?
It strikes me as a culture filter. You run in certain circles that I run in, read certain books that I read, therefor we will have a lot of the same prejudices and inclinations. As long as he isn't deluding himself into thinking it is an intelligence or competency filter, I can accept it.
I think the point is a reasonable one, if overly specific. A programmer who does no outside reading on his profession will be ill-equipped to do research when the need arises, and is more likely to want to be spoon-fed easy problems and cook up naive solutions.
While Programming Pearls is a reasonable test -- akin to checking whether someone has a classics background by asking a question about Moby Dick -- it should be acknowledged that everyone has some holes in their background, possibly even glaring and regrettable ones. A better question might be, "Describe a favorite clever hack and where you read about it."
Programming Pearls by Jon Bentley had a second edition with updated (for the time) C / C++ in 1999 with the original 14 years earlier. 11 years is a long time in computing and particularly for C++. I have a copy and remember reading it, but I don't remember the example (maybe I didn't find it terribly interesting at the time).
When I think folklore, I think of stories not example problems. I think "Fire in the Valley" not "C Quiz Book".
I may have spoken un-artfully, but there is an important point here that is being missed. I bet that every civil engineer, if asked at an interview, could explain the basic design of Galloping Gertie and the flaws that caused it to fail. I bet that every architect, if asked at an interview, could explain the basic design of the Twin Towers, and discuss why it was less resilient to heavy lateral impacts than other skyscrapers. I bet that every journalist, if asked at an interview, could quote some of the advice of Strunk and White.
As a broad statement, certainly not always true, computer programmers seem to be less knowledgeable of their professional culture than other professions. There is no equivalent to <em>Architectural Digest</em> or <em>Journal of Accountancy</em> or <em>Morbidity and Mortality</em> for programmers, so programmers have to work harder to keep up with their profession. If you can demonstrate that at an interview, you have a leg up on the candidate who can't.
Do you have to know the linear solution to the maximum sum subsequence problem to get hired? Of course not. But if you know it, and the other guy doesn't, then all other things being equal, you get hired, not him.
I should also have mentioned that there must be some context to the programming questions being asked at an interview. There are probably better questions to ask a PHP web developer.
Oofabz: Bentley recounts the history of the problem. Several experienced computer scientists believed for several weeks that the O(n log n) solution was optimal. If you think the linear solution is immediately obvious, you're special.
DannoHung: It may be that I have not fully specified the problem, but an empty sequence has a sum of zero, which is the maximal sum if all elements of the sequence are negative.
Abyssknight: I've never shipped anything. I've always worked in an internal support position, never on a shipping product. But I regularly develop and install new programs for my internal customers, in addition to supporting vendor code; I guess you could say I've shipped those programs.
Goombastic: I'm not a stupid HR guy. I'm a programmer who has stopped asking this kind of programming questions because I don't think they tell me much about the candidate. But it seems other folks do ask this kind of programming questions, so I put them on my blog from time to time.
I am not familiar with the book or with this problem, but I thought the O(n) solution was immediately obvious. It's not unreasonable to ask interviewees questions like this. I wouldn't want to hire someone who can't write an efficient algorithm.
This thread is the first time I've seen people consider these programming puzzles primarily as a test of memorization. The question is whether candidates can find a reasonable solution; it's a failure of the test if they already have seen the puzzle. Do people think nobody could possibly solve this puzzle on their own?
I wouldn't punish a candidate for not knowing the answer immediately, but I would expect a good programmer to be able to design algorithms with the requested performance characteristics given a reasonable amount of time.
Fair enough. An interviewer that filters on something as arbitrary as having read the same programming books is not someone I'd be interested in working with.
The linear solution looks like it depends on the maximum subsequence being greater than zero. Is there a similar solution that can produce Integer results?
Well it's linear time to find the maximum element of a sequence (which is equal to the maximum subsequence when all are non-positive), so you can by definition do both in linear time.
[+] [-] orangecat|15 years ago|reply
==============================================================
"Let's try again," said Severus. "Potter, where would you look if I told you to find me a bezoar?"
"That's not in the textbook either," Harry said, "but in one Muggle book I read that a trichinobezoar is a mass of solidified hair found in a human stomach, and Muggles used to believe it would cure any poison -"
"Wrong," Severus said. "A bezoar is found in the stomach of a goat, it is not made of hair, and it will cure most poisons but not all."
"I didn't say it would, I said that was what I read in one Muggle book -"
"No one here is interested in your pathetic Muggle books. Final try. What is the difference, Potter, between monksblood and wolfsbane?"
That did it.
"You know," Harry said icily, "in one of my quite fascinating Muggle books, they describe a study in which people managed to make themselves look very smart by asking questions about random facts that only they knew. Apparently the onlookers only noticed that the askers knew and the answerers didn't, and failed to adjust for the unfairness of the underlying game. So, Professor, can you tell me how many electrons are in the outermost orbital of a carbon atom?"
(Of course Snape knew, but the point stands).
[+] [-] wccrawford|15 years ago|reply
But even if English is the language they learned to program in, expecting them to have read the same books as you is silly. There are so many programming books out that there that it boggles the mind to pick any one and expect them to have read it. Worse, to have read it and memorized every algorithm in it.
Programming is about completing tasks, not about memorizing everything in existence.
And this is coming from someone who finds memorization very, very easy, especially when the data to memorize is an algorithm.
[+] [-] alnayyir|15 years ago|reply
I don't think it's meant to be universally applicable.
I'm only situationally in favor of this kind of thing, and I'd rather be a footnote/tilt factor than an actual bannable issue in a hiring process.
I've got a cursory familiarity with unix/hacker culture, but I don't think I would pass a Google-interview-esque history lesson even if I was able to ace that programming language test that went around earlier this week.
Edit:
I think it's worth mentioning here that there are no accurate methods of measuring competency in programming save for actually battle-testing them.
[+] [-] Xurinos|15 years ago|reply
I was once asked at a job about what OOP design patterns I knew. Design patterns are folklore (and mythology). At the time, I rattled off about three names to satisfy the interviewer, but nobody at my previous employer was busy memorizing names in a random popular book. I admitted as much. The employer hired me (probably not because of my lack of design pattern lingo). The term "design patterns" did not come up in my coursework because it was invented right after I graduated. ;) If a future employer asks me about design patterns, I will happily respond, "Design patterns reveal a language that lacks adequate abstraction features. I do not study design patterns, at least as defined by Fowler and company, because they have no justification in robust software design." Of course, folklore would have it that we should know this answer by now, so we see an example where even the accepted parts of "programming folklore" changes over time.
[+] [-] variety|15 years ago|reply
I don't particularly venerate the concept of design patterns, nor would I bother asking about them during an interview. But could you justify this statement?
[+] [-] variety|15 years ago|reply
A much more important (and deeper) skill is to be able to solve (or reasonably approach) problems they have never seen. And an even more important and deeper skill than that is the ability to recognize algorithmic problems embedded "in the wild" (in naturally occurring business contexts), and to tell the interesting ones from the non-interesting ones (and the trivial from the hard... and among the hard, the plausibly solvable ones from the intractable rabbit holes) without the imprimatur of having someone from a place like Google or MIT telling you that they're "interesting" problems (let alone tractably solvable).
Of course, this kind of skill is much, much harder to test for -- if it can be tested for in the awkward setting of a tech interview at all.
[+] [-] abyssknight|15 years ago|reply
[+] [-] Dylanlacey|15 years ago|reply
Every time after that, they could be boiling your code into a morass of blood, sweat and Jolt, weaving the Cthulhu pattern around your other Engineers' souls.
Ultimately, if you hire someone who ships, makes your code awful, pisses off your other engineers, doesn't document then chuffs off leaving you with a turd of an app and no-one to work on, their shipping only bought you N releases. A better engineer might have bought you <N releases... But prepared you for >N in the future.
[+] [-] mpmpmp|15 years ago|reply
"any programmer who doesn’t know about the solution will likely fail the interview, on the theory that if he isn’t at least interested enough in his profession to read Bentley [Programming Pearls], he isn’t interested enough in his profession to work for me."
In a follow-up comment:
"I still think a candidate not versed in the programming folklore will be less productive than one who is, and thus less suitable for hiring."
Is this a good or valid criteria for judging a programmer's abilities or future abilities?
[+] [-] acgourley|15 years ago|reply
[+] [-] Dove|15 years ago|reply
While Programming Pearls is a reasonable test -- akin to checking whether someone has a classics background by asking a question about Moby Dick -- it should be acknowledged that everyone has some holes in their background, possibly even glaring and regrettable ones. A better question might be, "Describe a favorite clever hack and where you read about it."
[+] [-] xentronium|15 years ago|reply
[+] [-] protomyth|15 years ago|reply
When I think folklore, I think of stories not example problems. I think "Fire in the Valley" not "C Quiz Book".
[+] [-] pbewig|15 years ago|reply
As a broad statement, certainly not always true, computer programmers seem to be less knowledgeable of their professional culture than other professions. There is no equivalent to <em>Architectural Digest</em> or <em>Journal of Accountancy</em> or <em>Morbidity and Mortality</em> for programmers, so programmers have to work harder to keep up with their profession. If you can demonstrate that at an interview, you have a leg up on the candidate who can't.
Do you have to know the linear solution to the maximum sum subsequence problem to get hired? Of course not. But if you know it, and the other guy doesn't, then all other things being equal, you get hired, not him.
I should also have mentioned that there must be some context to the programming questions being asked at an interview. There are probably better questions to ask a PHP web developer.
Oofabz: Bentley recounts the history of the problem. Several experienced computer scientists believed for several weeks that the O(n log n) solution was optimal. If you think the linear solution is immediately obvious, you're special.
DannoHung: It may be that I have not fully specified the problem, but an empty sequence has a sum of zero, which is the maximal sum if all elements of the sequence are negative.
Abyssknight: I've never shipped anything. I've always worked in an internal support position, never on a shipping product. But I regularly develop and install new programs for my internal customers, in addition to supporting vendor code; I guess you could say I've shipped those programs.
Goombastic: I'm not a stupid HR guy. I'm a programmer who has stopped asking this kind of programming questions because I don't think they tell me much about the candidate. But it seems other folks do ask this kind of programming questions, so I put them on my blog from time to time.
Everyone: Thanks for the discussion.
[+] [-] protomyth|15 years ago|reply
[+] [-] goombastic|15 years ago|reply
[+] [-] oofabz|15 years ago|reply
[+] [-] skew|15 years ago|reply
[+] [-] Zak|15 years ago|reply
[+] [-] ryandvm|15 years ago|reply
[+] [-] DannoHung|15 years ago|reply
[+] [-] aidenn0|15 years ago|reply