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: 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: 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
From: Andrew Tomazos on 20 Dec 2009 18:08
On Nov 28, 4:07 am, Phil Carmody <thefatphil_demun...(a)yahoo.co.uk> wrote: > > 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. > > What solution? The above exhibits undefined behaviour. If you spot a bug you might bother saying what it is. I wrote this quickly and haven't tested it. Are you referring to the assumption that int is 32 bit, or is there a typo or some other problem? -Andrew. |