Math/CompSci Interview Question - Thoughts?
in [Theory]
|
From: Rob Johnson on 28 Jan 2010 07:15 In article <Pine.LNX.4.64.1001281224100.19779(a)lxserv1.kfki.hu>, FOLDY Lajos <foldy(a)rmki.kfki.hu> wrote: >On Wed, 27 Jan 2010, websnarf wrote: > >> I missed your original post, but dug up the following that might be of >> interest: >> >> http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html > >Probably I miss something, but this algorithm gives D as the majority >element in the sequence AAAABCBCD. ??? The majority element has to account for more than 50% of the sample. In the example above, there is no majority element (A is 4/9 of the sample), so the algorithm does not guarantee anything. Rob Johnson <rob(a)trash.whim.org> take out the trash before replying to view any ASCII art, display article in a monospaced font
From: Ilmari Karonen on 28 Jan 2010 07:45 ["Followup-To:" header set to sci.math.] On 2010-01-28, F�LDY Lajos <foldy(a)rmki.kfki.hu> wrote: > On Wed, 27 Jan 2010, websnarf wrote: > >> I missed your original post, but dug up the following that might be of >> interest: >> >> http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html > > Probably I miss something, but this algorithm gives D as the majority > element in the sequence AAAABCBCD. ??? Like the original puzzle that started this thread, the linked paper is using "majority element" to mean an element that occurs more than n/2 times in a list of n elements. By that definition, your list does not have a majority element. -- Ilmari Karonen To reply by e-mail, please replace ".invalid" with ".net" in address.
From: Mathew Francis on 3 Mar 2010 04:08 If the question is "one value occurs 500,001 times or more and the rest of the values occur exactly once in the array", then it can be done by simply checking for a value that occurs in two consecutive positions. On Wed, 27 Jan 2010, websnarf wrote: > 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." > > I missed your original post, but dug up the following that might be of > interest: > > http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html > > -- > Paul Hsieh > http://www.pobox.com/~qed/ > http://bstring.sf.net/ >
From: pete on 3 Mar 2010 06:32 Mathew Francis wrote: > > If the question is "one value occurs 500,001 > times or more and the rest of > the values occur exactly once in the array", then it can be done by > simply checking for a value that occurs in two consecutive positions. That seems to be an O(N*N) solution, while a O(N) solution is claimed in the below URL. > On Wed, 27 Jan 2010, websnarf wrote: > > > 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." > > > > I missed your original post, > > but dug up the following that might be of > > interest: > > > > http://www.cs.utexas.edu/users/moore/best-ideas/mjrty/index.html -- pete
From: Richard Heathfield on 3 Mar 2010 06:55
pete wrote: > Mathew Francis wrote: >> If the question is "one value occurs 500,001 >> times or more and the rest of >> the values occur exactly once in the array", then it can be done by >> simply checking for a value that occurs in two consecutive positions. > > That seems to be an O(N*N) solution, I don't think so. With Mathew's change to the spec, we have: #include <stdio.h> /* handwaving the O(n) array population step */ extern int populate(unsigned long *n, size_t len); int main(void) { int done = 0; static unsigned long arr[1000000]; size_t max = sizeof arr / sizeof arr[0]; unsigned long lastval; size_t i; populate(arr, max); lastval = arr[0]; for(i = 1; !done && i < max; i++) { if(arr[i] == lastval) { done = 1; } else { lastval = arr[i]; } } if(done) { printf("%lu\n", lastval); } else { printf("No consecutives found\n"); } return 0; } which looks pretty O(n) to me. <snip> -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ "Usenet is a strange place" - dmr 29 July 1999 Sig line vacant - apply within |