Math/CompSci Interview Question - Thoughts?
in [Math]
|
Prev: Engineering Mechanics: Dynamics 6th Edition Solutions Manual Meriam & Kraige
Next: Multinational business finance Solution manual please???
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
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 |