Math/CompSci Interview Question - Thoughts?
in [General Programming]
|
Prev: Unification Algorithm
Next: Software Configuration Management: Continuous Integration Widely Adopted
From: mike3 on 25 Nov 2009 22:28 On Nov 25, 2:33 am, p...(a)informatimago.com (Pascal J. Bourguignon) wrote: > mike3 <mike4...(a)yahoo.com> writes: > > On Nov 25, 12:06 am, "John W. Krahn" <some...(a)example.com> wrote: > >> Richard Heathfield wrote: > >> > In > >> > <805a7a21-f99b-4eb9-abb0-fbde47cb9...(a)k19g2000yqc.googlegroups.com>, > >> > mike3 wrote: > > >> > <snip> > > >> >> Oh yes, and I forgot to add: how does one train the "symbolic" > >> >> thinking? > > >> > Step 1: obtain a pointy stick. > > >> Or some fresh fruit. > > > What's the point here? > > http://www.leftinthedark.org.uk/ > So what's the pointy stick for, then?
From: mike3 on 25 Nov 2009 22:36 On Nov 25, 8:28 pm, mike3 <mike4...(a)yahoo.com> wrote: > On Nov 25, 2:33 am, p...(a)informatimago.com (Pascal J. Bourguignon) > wrote: > > > > > mike3 <mike4...(a)yahoo.com> writes: > > > On Nov 25, 12:06 am, "John W. Krahn" <some...(a)example.com> wrote: > > >> Richard Heathfield wrote: > > >> > In > > >> > <805a7a21-f99b-4eb9-abb0-fbde47cb9...(a)k19g2000yqc.googlegroups.com>, > > >> > mike3 wrote: > > > >> > <snip> > > > >> >> Oh yes, and I forgot to add: how does one train the "symbolic" > > >> >> thinking? > > > >> > Step 1: obtain a pointy stick. > > > >> Or some fresh fruit. > > > > What's the point here? > > >http://www.leftinthedark.org.uk/ > > So what's the pointy stick for, then? To get fruit off the trees? What? Hmm.
From: Anders Karlsson on 26 Nov 2009 08:43 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: > <snip> >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? > I think as an interviewer I would be more interested in see your line of reasoning and how well you work with and accept other peoples ideas. The solution is not so important but the road there is. It is much more difficult to find a developer who has the right attitude then there is find some closet nerd who doesn't know how to interact.. I personally wouldn't expect somebody to solve any particular non-trivial complex algorithm in an interview for the simple reason that most people are quite nervous when being interviewed. Just my 2c
From: Nick Keighley on 27 Nov 2009 05:05 On 25 Nov, 07:11, mike3 <mike4...(a)yahoo.com> wrote: > On Nov 25, 12:06 am, "John W. Krahn" <some...(a)example.com> wrote: > > > Richard Heathfield wrote: > > > In > > > <805a7a21-f99b-4eb9-abb0-fbde47cb9...(a)k19g2000yqc.googlegroups.com>, > > > mike3 wrote: > > > > <snip> > > > >> Oh yes, and I forgot to add: how does one train the "symbolic" > > >> thinking? > > > > Step 1: obtain a pointy stick. I think that's supposed to mean "there's no easy way". Practice maybe. > > > Or some fresh fruit. > > What's the point here? google Monty Python
From: Phil Carmody on 27 Nov 2009 22:07
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-equivilant" experience/knowledge of > computer science and math. Should I have been able to come up with > this solution without prompting or help? What solution? The above exhibits undefined behaviour. Phil -- Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1 |