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: 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: FÖLDY Lajos on 28 Jan 2010 11:01 On Thu, 28 Jan 2010, Ilmari Karonen wrote: > ["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. > Ahh, definitions :-) Thanks, lajos
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 |