Math/CompSci Interview Question - Thoughts?
in [General Programming]
|
Prev: Unification Algorithm
Next: Software Configuration Management: Continuous Integration Widely Adopted
From: Patricia Shanahan on 23 Nov 2009 17:54 James Kanze wrote: > On Nov 23, 7:39 pm, "Paul E. Black" <p.bl...(a)acm.org> wrote: > [...] >> I often ask questions to understand an applicant's approach, >> not for their specific knowledge. (I asked one candidate to >> write a quicksort, and he replied he would look it up. I was >> not impressed.) > > And yet, it's the only answer a professional should give. You > don't reinvent what's already been invented, and it would be > really a bit of a chance that a candidate happened to have a > good implementation of quicksort in his head. .... I agree that the first response should definitely be "I'd look it up.". I know the basic concept of quicksort but if I really had to write one I would first do some reading, for example about pivot selection. There is a legitimate follow-on question of the form "I'd like to see how you think and talk about algorithm design questions. Please explain what you know about quicksort implementation.". Unfortunately, many of these interview questions miss out on the really important practical skill, seeing mappings from a programming problem to standard problems for which there are well-known algorithms. Patricia
From: Stuart Golodetz on 23 Nov 2009 18:05 Paul E. Black wrote: > On Saturday 21 November 2009 11:12, Andrew Tomazos wrote: >> I was posed the following question in a technical interview for a >> Software Engineering position by a major multinational NASDAQ company: >> >> [Paraphrasing] "You are given an array of 1,000,000 32-bit integers. >> One int value x occurs 500,001 times or more in the array. Specify an >> algorithm to determine x." >> >> ... [PEB] >> >> The interviewer already knew the answer, so I can only assume the test >> was based on how much help he had to give me to arrive at it. > > I often ask questions to understand an applicant's approach, not for > their specific knowledge. (I asked one candidate to write a > quicksort, and he replied he would look it up. I was not impressed.) :) If you explicitly asked him to write it, then that is slightly underwhelming. On the other hand, if you asked him how he *would* write it (i.e. were he not in an interview), then I'm not sure it's such a bad answer. The fact that I can concoct a quicksort routine off the top of my head doesn't mean that I wouldn't dig out CLR to sanity check myself in practice - so I'd probably give you the same answer (implementing common algorithms from books saves time and is actually about working smart). Regards, Stu >> Would you expect someone with a CompSci Masters or PhD from some major >> ivy league university to be able to come up with this solution without >> help? >> >> If so in what course or from which book would you expect to learn the >> required knowledge to come up with the above solution? >> >> Is the skill to be able to come up with such an algorithm something >> that is learned by studying lots of algorithms and being able to mix >> and match the "tricks"? > > I took an algorithms or analysis of algorithms class. We solved a ton > of problems like "design an O(n^2) algorithm for ..." (or n log n or > whatever). After a semester of this, we were pretty good at coming up > with stuff. Note: just "knowing" the complexity of a solution went a > long way as a hint to how it might be solved. > > So yes, studying how to come up with algorithms should help people in > similar circumstances. > > Did *I* solve the problem? hmm, uh, its been a coupla' decades, and > I'm, uh, kinda' busy ... > > -paul-
From: Beej Jorgensen on 23 Nov 2009 18:14 Patricia Shanahan <pats(a)acm.org> wrote: >There is a legitimate follow-on question of the form "I'd like to see >how you think and talk about algorithm design questions. Please explain >what you know about quicksort implementation.". If it were me being interviewed, I'd just go ahead and assume that's what the interviewer meant (they barely ever mean for you to look it up any more than your prof meant for you to write "I'd look it up" as an answer on a test.) Then, after describing the algorithm, I'd add that in real life I'd use an existing library or algorithm description. -Beej
From: Tim Little on 23 Nov 2009 19:16 On 2009-11-23, Paul E. Black <p.black(a)acm.org> wrote: > I often ask questions to understand an applicant's approach, not for > their specific knowledge. (I asked one candidate to write a > quicksort, and he replied he would look it up. I was not impressed.) I'd probably not impress you either. I've seen so many variants on average-case O(n log n) sorting algorithms that I occasionally forget which one has which label. Mergesort I know and have implemented numerous times. For others: Quicksort? Heapsort? Treesort? Smoothsort? I'd probably have to look up a reference to confirm which were which. Though after consulting a reference, it looks like I did recall which one Quicksort was. As I thought, it was one of those that has O(n^2) worst-case performance (and not an uncommon case at that), which often makes it unsuitable as a general sorting algorithm. I've only ever implemented it once, as a "toy" exercise in school. - Tim
From: tchow on 23 Nov 2009 21:27
In article <heekp9025d4(a)news1.newsguy.com>, Paul E. Black <p.black(a)acm.org> wrote: >I often ask questions to understand an applicant's approach, not for >their specific knowledge. (I asked one candidate to write a >quicksort, and he replied he would look it up. I was not impressed.) To be fair to the candidate, your question was a poor choice if your intention was to "understand an applicant's approach, not for their specific knowledge." Did you really ask for *quicksort* specifically? If so, how is that *not* testing for specific knowledge? In real life, if for some reason I really needed to write a *quicksort*, guess what? I would look it up. Not in a book, of course; I'd find a library routine that somebody had already written. Why reinvent the wheel? -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences |