Math/CompSci Interview Question - Thoughts?
in [General Programming]
|
Prev: Unification Algorithm
Next: Software Configuration Management: Continuous Integration Widely Adopted
From: Paul E. Black on 23 Nov 2009 13:39 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.) > 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- -- Paul E. Black (p.black(a)acm.org)
From: Ben Pfaff on 23 Nov 2009 13:47 "Paul E. Black" <p.black(a)acm.org> writes: > (I asked one candidate to write a quicksort, and he replied he > would look it up. I was not impressed.) "Look it up" is the only sensible way to write a quicksort. Otherwise you'll either waste your time reinventing important refinements of the basic algorithms, or you'll write a quicksort that performs badly in important special cases. Here's the classic paper on quicksort (I suppose you've seen it): http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/09/bentley93engineering.pdf -- Ben Pfaff http://benpfaff.org
From: Patricia Shanahan on 23 Nov 2009 14:31 Paul E. Black wrote: .... > 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. .... Your algorithms professor was kinder than mine. He set problems of the form "Write an algorithm for ..." with standing instructions that we had to state a claimed time complexity, prove correctness, and prove the claimed time complexity. Given correct proofs, he gave better grades for lower complexity algorithms. That was more realistic, because someone starting on designing an algorithm does not usually know in advance what complexity is achievable. However, it had the unpleasant consequence that I could rarely be sure I had finished my homework, even after I had written an algorithm and the required proofs. Patricia
From: Balog Pal on 23 Nov 2009 17:11 "Paul E. Black" <p.black(a)acm.org> > 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.) Sounds like a contradiction. Knowing the specifics what is titled 'quicksort' is definitely "specific knowledge" and has little to do with approach. And the approach of "I look it up" is one with great benefit, if the man can really get it effectively. Why would you want to clogger memory with quicksort? We have qsort in C lib, std::sort, all ready to call, need to implement it from scratch comes up in what circumstances? And who in right mind would start just writing the code instead of inspecting the existing implementations first? > 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. And what is the percentage of time you spent in work that you spent inventing algo or using that knowledge? And what would be IYO the figure for the general case? > So yes, studying how to come up with algorithms should help people in > similar circumstances. Similar to what? IMO being *able* to use such stuff, to understand and learn it as need comes is indeed important. But otherwise it is just a special area. Like say the internals of the 6502 processors, or to tweak oracle, or being fluent in prolog -- applicability tied to some niche.
From: James Kanze on 23 Nov 2009 17:23
On Nov 23, 7:39 pm, "Paul E. Black" <p.bl...(a)acm.org> wrote: > On Saturday 21 November 2009 11:12, Andrew Tomazos 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. [...] > Did *I* solve the problem? hmm, uh, its been a coupla' > decades, and I'm, uh, kinda' busy ... Exactly:-). But if the problem really occured in your work, you could no doubt look it up very quickly (and implement correctly the algorithme that you found). -- James Kanze |