Math/CompSci Interview Question - Thoughts?
in [Theory]
|
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: Torben =?iso-8859-1?Q?=C6gidius?= Mogensen on 26 Nov 2009 03:52 "bartc" <bartc(a)freeuk.com> writes: > "Andrew Tomazos" <andrew(a)tomazos.com> wrote in message > news:6a8340b8-19b0-4fda-96d5-e744aead1bd7(a)m26g2000yqb.googlegroups.com... >>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." > > How was it determined that one value occurs 500001 or more times? I interpret this as a given fact. > I quite liked Malcolm's idea of taking a small but random sample, > choosing a handful of likely candidates, then counting occurrences of > those. If no counts reach 500001, then repeat a few more times While this is quite fast on average, it can have a _really_ bad worst case time. > or until you know you've been given dud information. I think you can assume you haven't been given "dud" information. The bitcount method is quite elegant, but I'm not sure I would have thought of it during a short interview. My first thought would be to sort the array and take the middle element, then refine this into using a modified sort algorithm to find the median (in shorter time than sorting). Torben
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 |