Math/CompSci Interview Question - Thoughts?
in [Theory]
|
From: Andrew Tomazos on 21 Nov 2009 11:12 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.
From: Pascal J. Bourguignon on 21 Nov 2009 12:24 Andrew Tomazos <andrew(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. > 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. > 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. Also, don't limit yourself to CS and maths, there are ideas to be taken from other domains too. > 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. > 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. -- __Pascal Bourguignon__
From: GJ Woeginger on 21 Nov 2009 12:29 In comp.theory Andrew Tomazos <andrew(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). --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Richard Harter on 21 Nov 2009 13:33 On Sat, 21 Nov 2009 08:12:53 -0800 (PST), Andrew Tomazos <andrew(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. [snip code] > >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? I hope "masters-equivilant" isn't on your resume. > >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? Probably not, but that is not necessarily a good thing. > >If so in what course or from which book would you expect to learn the >required knowledge to come up with the above solution? That's an interesting question with an interesting presupposition. The first thing to understand is that this is a puzzle rather than a programming problem. The presupposition is that you need required knowledge to come up with a solution. The essence of a good puzzle is that you need to step outside the box to see the solution; that is, there is a trick that involves an unexpected way of looking at things. Creating good puzzles is tricky. Once you've come up with a good trick it is easy to come with many more similar tricks; unfortunately the puzzle solver will have learned the trick too. Perhaps the best way to learn how to solve puzzles like this is try to solve puzzles like this. I don't know of any courses, though I think the MIT AI group used to have a course like that. As far as books and web sites are concerned, google is your friend. Do a search on Programming puzzles and tricks. > >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? Partly it is a matter of talent - some people are inately better at solving puzzles than others. Partly it is a matter of intellectual personality - some people don't like solving puzzles. Partly it is a matter of experience; exposure to lots of puzzle solving makes it easier to solve puzzles. One point of using puzzles in interviews is that it tests the preparedness of interviewees. These things are chestnuts. If you are serious about getting the job, you go through the chestnuts in advance. It's similar to finding what a company does before you interview with it. The hope of the interviewer is that you've never seen that kind of puzzle before and they get to see how agile you are on your mental feet. Speaking from the interviewers side of the fence those sort of tests are mostly good for checking out bright young puppies who are short on hard experience. When one is dealing with more experienced people the important thing is to discover if they know what they are supposed to know and how alive their intellectual curiosity is. Oh yes, the most important thing to discover whether they are BS artists giving you a snow job. BS artists are deadly in the technical world. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com Infinity is one of those things that keep philosophers busy when they could be more profitably spending their time weeding their garden.
From: A.G.McDowell on 21 Nov 2009 13:46
In article <6a8340b8-19b0-4fda-96d5-e744aead1bd7(a)m26g2000yqb.googlegroup s.com>, Andrew Tomazos <andrew(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: > This sort of problem is covered by articles on Data Stream Processing in CACM Oct 2009. (CACM is a lot more interesting these days than it was some years ago). There are some very neat ideas in there, of which the algorithm "MAJORITY" matches the question reasonably well. Proving that it works under interview conditions would be extremely impressive, though. This is not the first time that I have heard of interview questions that discuss issues recently covered in the computing literature. I am unable to tell whether these come from a desire to know if the candidate keeps themselves abreast of the subject, or from the interviewer grasping the first thing that comes to hand when they are trying to think up a question. The few times that I have posed interview questions, I have tried to find evidence in the candidate of a knowledge of basic theory or mathematics that I could show was relevant to the job for which we were trying to recruit. -- A.G.McDowell |