Math/CompSci Interview Question - Thoughts?
in [General Programming]
|
Prev: Unification Algorithm
Next: Software Configuration Management: Continuous Integration Widely Adopted
From: Richard Heathfield on 23 Nov 2009 23:00 In <heekp9025d4(a)news1.newsguy.com>, Paul E. Black wrote: <snip> > 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.) Just in case you're not yet sick of people saying "he gave the right answer", I'll add my own two pennorth: he gave the right answer. It may be that you failed to be impressed because he compressed his rationale too much. He should have said: 'The basic approach of quicksort is to pick one element of the data and use it as a fixed point, normally called a pivot. Then all the other elements are arranged to one side or the other of that pivot, depending on how their keys compare to its key. Recursion takes care of the rest. I could easily write quicksort from memory, and I will do so if you like. But it would be very arrogant of me to assume that I could write a *good* quicksort from memory, because it's regrettably easy to write a very inefficient quicksort, and the details for making it quick aren't needed very often, so there's no point in remembering them. It would be like you, a project manager or lead programmer, making a special point of remembering the serial number on the back of your router - why bother, when you know where to find it on the vanishingly rare occasions that you actually need it? Therefore, the right answer to this question is "I'd look it up".' <snip> > Did *I* solve the problem? hmm, uh, its been a coupla' decades, and > I'm, uh, kinda' busy ... Right. So you look it up, right? That's the correct answer. Well done. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within
From: Ben Pfaff on 23 Nov 2009 23:28 Richard Heathfield <rjh(a)see.sig.invalid> writes: > In <heekp9025d4(a)news1.newsguy.com>, Paul E. Black wrote: >> Did *I* solve the problem? hmm, uh, its been a coupla' decades, and >> I'm, uh, kinda' busy ... > > Right. So you look it up, right? That's the correct answer. Well done. I look forward to a job interview someday when someone asks me a question related to binary search trees and I get to tell them to look it up in my book. -- "doe not call up Any that you can not put downe." --H. P. Lovecraft
From: bill on 24 Nov 2009 02:06 On Nov 21, 8:12 am, Andrew Tomazos <and...(a)tomazos.com> 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." > > 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-equivilant" experience/knowledge of > computer science and math. Should I have been able to come up with > this solution without prompting or help? > > 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"? 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? > Some people have the talent to solve the puzzle, see the pattern and > come up with the solution - and some just don't? > > Thanks, > Andrew. Compare the number of 1's and 0's in each bit position. Which ever bit is in the majority is the bit in 'x' for that bit position. Creating an appropriate algorithm might be considerably more difficult than I suspect! But the approach works if x is something like 01111111111111111111111111111111. regards, Bill J.
From: mohangupta13 on 24 Nov 2009 12:22 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?? Mohan > This was accepted by the interviewer (but I didn't get the job).
From: mohangupta13 on 24 Nov 2009 12:26
On Nov 23, 3:27 pm, James Kanze <james.ka...(a)gmail.com> wrote: > On Nov 22, 4:51 pm, Chip Eastham <hardm...(a)gmail.com> wrote: > > > > > On Nov 21, 7:04 pm, Andrew Tomazos <and...(a)tomazos.com> wrote: > > > On Nov 22, 1:01 am, Andrew Tomazos <and...(a)tomazos.com> wrote: > > > > On Nov 21, 6:29 pm, gwo...(a)figipc78.tu-graz.ac.at (GJ Woeginger) > > > > wrote: > > > > > In comp.theory Andrew Tomazos <and...(a)tomazos.com> 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." > > > > > > The assumption being extra points for efficiency. > > > > > There is an old analysis of this problem by Fischer and Salzberg. > > > > > M.J. Fisher and S.L. Salzberg (1982) > > > > > Finding a majority among n votes. > > > > > Journal of Algorithms 3, pp 143-152. > > > > > If 2k elements contain a majority element (= an element > > > > > that occurs at least k+1 times), then you can find it > > > > > with 3k-2 element comparisons (and some small overhead). > > > > > The basic idea in their algorithm is that whenever you > > > > > find two distinct elements, then you can destroy both > > > > > without changing the majority element among the > > > > > remaining elements. This yields: > > > > > Run once through the array, and maintain a > > > > > majority-candidate and a counter. The > > > > > majority-candidate is initialized as the first element, > > > > > and the counter (counting how often you have seen the > > > > > candidate) is initialized at 1. > > > > > If you hit the current candidate again, increment the counter. > > > > > If you hit another element, decrement the counter. > > > > > If the counter becomes 0, drop the current candidate and start from > > > > > scratch with the remaining part of the array. > > > > > Fischer and Salzberg also show that this bound 3k-2 is > > > > > best possible in the worst case (and that's the main > > > > > part of their paper). > > > > If I understand your description than it would look like: > > > > int findmode(int* p, int n) > > > > { > > > > int x = p[0]; > > > > int c = 1; > > > > > for (int i = 1; i < n; i++) > > > > { > > > > if (c == 0) > > > > { > > > > x = p[i]; > > > > c = 1; > > > > } > > > > else if (p[i] == x) > > > > c++; > > > > else > > > > c--; > > > > } > > > > return x; > > > > } > > > > It seems that this could only produce at maximum (2k-1) > > > > comparisions in the worst case, not (3k-2) as you claim? > > > Oh wait... the (c==0) counts as a comparison. I see it now. > > > Ignore me. > > I don't think the (c==0) counts as a comparison. > > Of course it does. Why wouldn't it? Why should it count? Its just a simple instruction like c++ or c-- , it should count As comparison should refer to the comparison of input entities (with their satellite data's) . > > > I think the other k-1 comparisons are for the 2nd > > part of the algorithm, when you make one more pass > > through the array verifying the candidate found in > > the 1st part. [You already know the index i for > > one occurrence of the candidate, so only the other > > k-1 indices have to be checked.] 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. Mohan > > What second part? There is no second pass. > > -- > James Kanze |