Math/CompSci Interview Question - Thoughts?
in [Theory]
|
From: Paul E. Black on 24 Nov 2009 12:54 On Monday 23 November 2009 21:27, tchow(a)lsa.umich.edu wrote: > 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? I think so. > If so, how is that *not* testing for specific knowledge? Because I didn't really care if they could write quicksort off the top of their head. I wanted to see if they would work with me or try to fake it. If they said, I don't remember, but I could look it up, I'd help them (or switch to simpler algorithm). I'd typically guide them through whatever they were writing. Did they think about correctness? Did they talk about testing or noting (documenting) what they were doing? What language should it be in? Did they think about alternatives? The type of input parameters? Should the input parameters be checked? Will they ask if they *don't* know something, or will they just guess and write garbage? It was the candidate's attitude of "I'm so far beyond that that I don't even bother remembering such trivia." When I tried to push to see what he *did* know, I could not get a feel of engagement. > 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? Excellent point. And I respect that answer. -paul- -- Paul E. Black (p.black(a)acm.org)
From: Ben Bacarisse on 24 Nov 2009 13:07 mohangupta13 <mohangupta13(a)gmail.com> writes: <snip> > But I still don't get how is it 3k -2 comparisons i just see a single > loop (of n) in which comparison is done just once. That bound was quoted in error. It is for a closely related but sightly different algorithm. The algorithm given here uses n-1 element comparisons. The paper from which the 3k - 2 comes describes a method to determine *if* there is a majority and, if so, what the majority element is. That needs 3n/2 - 2 element comparisons, but since we know there a majority, we can stop after what the authors call phase one: http://www.cs.yale.edu/publications/techreports/tr252.pdf A good overview of similar problems is given here: http://www2.research.att.com/~marioh/papers/cacm09.pdf -- Ben.
From: Ben Bacarisse on 24 Nov 2009 13:10 mohangupta13 <mohangupta13(a)gmail.com> writes: > On Nov 23, 2:52 am, mjc <mjco...(a)acm.org> wrote: >> I was also given this problem as part of an interview quiz. My answer >> was: Use one of the known O(n) median algorithms and use that value. > How do you use median algorithm ( as i get it .those refer to the > selection algorithm ,like (n+1)/2 th order statistic) to solve the > above problem?? Imagine the 1,000,000 items sorted. How can the middle item be anything but one of 500,001 that make up the majority? -- Ben.
From: mohangupta13 on 24 Nov 2009 15:39 On Nov 24, 11:10 pm, Ben Bacarisse <ben.use...(a)bsb.me.uk> wrote: > mohangupta13 <mohangupt...(a)gmail.com> writes: > > On Nov 23, 2:52 am, mjc <mjco...(a)acm.org> wrote: > >> I was also given this problem as part of an interview quiz. My answer > >> was: Use one of the known O(n) median algorithms and use that value. > > How do you use median algorithm ( as i get it .those refer to the > > selection algorithm ,like (n+1)/2 th order statistic) to solve the > > above problem?? > > Imagine the 1,000,000 items sorted. How can the middle item be > anything but one of 500,001 that make up the majority? > sorry for giving much thought before writing. Mohan > -- > Ben.
From: mike3 on 24 Nov 2009 20:32
On Nov 21, 10:24 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > Andrew Tomazos <and...(a)tomazos.com> writes: > > 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." > > > The assumption being extra points for efficiency. > > > I initially came up with a linear space, linear time solution. With > > some prompting and hints from the interviewer we worked our way to a > > smaller constant space and linear time algorithm. That being > > basically: > > > int findmode(int* p, int n) > > { > > int count[32]; > > for(int i = 0; i < 32; i++) > > count[i] = 0; > > > for (int i = 0; i < n; i++) > > for (int j = 0; j < 32; j++) > > if (p[i] & (1 << j)) // if bit j is on > > count[j]++; > > else > > count[j]--; > > > int x = 0; > > for (int i = 0; i < 32; i++) > > if (count[i] > 0) > > x = x | (1 << i); > > > return x; > > } > > > The idea here is to count the frequency of each of the 32 bits in the > > array separately, knowing that these bit counts will be dominated by > > the mode. > > > 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. > > > My question about this is as follows. I, perhaps boldly, claim to > > employers to have a "masters-equivalant" experience/knowledge of > > computer science and math. Should I have been able to come up with > > this solution without prompting or help? > > If what you're asking is whether anybody having a master in CS and > maths would have been able to come up with this solution in the > interview time, I guess we can answer that definitely no, otherwise > there would be no point in trying to select candidates with this test. > > Obviously, it's because some people (with or without a master diploma, > this really isn't relevant) get or don't get it, that this test is > useful for the recruiter. > > Now if you want this kind of jobs, yes you should better be able to > come up with smart solutions to little puzzles like this in > interviews. > You mean he should be able to come up with them without prompting, right? > > 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? > > Not a single one. You have to develop your knowledge of algorithms, > mathematics, your symbolic thinking and your imagination in these > matters. > You say not a "single" one, so does that mean no course would do it, or you'd need multiple ones? After all, courses and books (multiple) can be used to increase the first 2 areas (knowledge of algorithms and mathematics). > > 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"? > > That could help yes. I'd tend to think that imagination is the most > important ingredient here, to be able to come with a possible solution > fast enough. > And how does one develop that? More specifically, the "speed" of coming up with the solution, not just being able to come up with one. > Also, don't limit yourself to CS and maths, there are ideas to be > taken from other domains too. > What would that be? > > If so, what is a similar commonly known > > algorithm(s) on which the above solution could have been based? > > > Or, is the ability to invent such a solution simply a matter of IQ? > > CS IQ, yes, if such a IQ test exists. > Heh. > > Some people have the talent to solve the puzzle, see the pattern and > > come up with the solution - and some just don't? > > It seems so. At least, in a given time. > Hmm. |