"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.
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 are essentially code that you have to repeat because the language is incapable of generically representing the process that the pattern codifies. For example, I believe pg once observed that most of the classical design patterns didn't exist in any recognizable form in Common Lisp because their functionality could be factored out into higher order functions and macros.
Ah, I found it. It was in his Revenge of the Nerds essay, and he was actually citing Norvig, though he goes into more detail than just that. http://www.paulgraham.com/icad.html
Design patterns are essentially code that you have to repeat because the language is incapable of generically representing the process that the pattern codifies.
In the specific case of the twenty canonical design patterns from the GoF book, some are rendered trivial by better languages, but the principle of a design pattern remains valid. I'm confident that Lisp has design patterns, I own a book full of them:
A design pattern in the abstract is a systemized form of folklore. Problem Statement, Forces Acting on the Solution, Template for Implementing the Solution. Until we have a language where every problem to be solved can be done so with a single atomic element of the language, there will be design patterns that programmers use to share their experience.
Now that we have established that we can choose several different colours for the bike shed, I will say that if you gave me that answer in an interview, I wouldn't hold it against you in any way. It demonstrates intelligence and experience. I imagine that if we were talking face to face we could have an interesting conversation about languages and abstractions and templates and problems and communicating folklore.
So my meta-observation is that the important thing about a question is whether it helps provoke an interesting and useful conversation, not whether the person parrots out some answer you are seeking.
I agree vehemently. If I am a candidate, the employer's reaction to my answer is part of my employer test. I would experience a certain measure of glee if the employer -- who is testing my technical skills -- had enough technical know-how to ask those kinds of follow-ups.
Yes, in that the presence of design patterns indicates that the paradigm or language used is not sophisticated enough (for example, many if not most of the GoF patterns are unnecessary in Ruby/Python).
On the other hand, some people still have to work in such environments so it is good for them to know the patterns, and it may be beneficial for others to understand them as well (as foundational structures).
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.
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".
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.
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?
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."
A programmer who does no outside reading on his profession will be ill-equipped to do research when the need arises
I do outside reading, but I would be hard-pressed to make this claim. How is outside reading correlated to research ability? This is like saying, "If programmers are not playing a musical instrument outside of work, then it is obvious they do not have what it takes to think in patterns and perfect their skills."
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 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.
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?