Math/CompSci Interview Question - Thoughts?
in [Theory]
|
From: pete on 3 Mar 2010 07:15 Richard Heathfield wrote: > > 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. You are both correct. I misread what Mathew Francis had written. Some people say that reading is harder than writing. -- pete
From: Pascal J. Bourguignon on 3 Mar 2010 08:29 Richard Heathfield <rjh(a)see.sig.invalid> writes: > 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. It is not said that the other values are without repeatition! [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." So you could have: {1,1,2,2,2,2} with N=6. and your algorithm wouldn't work correctly. The minimum number of step possible (the best case), is N/2+1, if the wanted numbers x are all at the beginning of the vector. -- __Pascal Bourguignon__ http://www.informatimago.com
From: Richard Harter on 3 Mar 2010 09:21 On Wed, 03 Mar 2010 14:29:11 +0100, pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: >Richard Heathfield <rjh(a)see.sig.invalid> writes: > >> 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: [snip] >It is not said that the other values are without repeatition! > > [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." You ignored the beginning of the post that you commented upon. They aren't discussing the original post with the original problem. They are discussing the problem stated by Matthew Francis. > >So you could have: {1,1,2,2,2,2} with N=6. >and your algorithm wouldn't work correctly. Example does not fit the problem under discussion. > > >The minimum number of step possible (the best case), is N/2+1, >if the wanted numbers x are all at the beginning of the vector. In the problem currently being discussed the best case is 1; the worst case is N/2-1. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com It's not much to ask of the universe that it be fair; it's not much to ask but it just doesn't happen.
From: Richard Harter on 3 Mar 2010 10:55 On Wed, 03 Mar 2010 14:21:09 GMT, cri(a)tiac.net (Richard Harter) wrote: > >In the problem currently being discussed the best case is 1; the >worst case is N/2-1. Oops, best case is 2. Richard Harter, cri(a)tiac.net http://home.tiac.net/~cri, http://www.varinoma.com It's not much to ask of the universe that it be fair; it's not much to ask but it just doesn't happen.
From: Pascal J. Bourguignon on 4 Mar 2010 04:02
cri(a)tiac.net (Richard Harter) writes: > On Wed, 03 Mar 2010 14:29:11 +0100, pjb(a)informatimago.com (Pascal > J. Bourguignon) wrote: > >>Richard Heathfield <rjh(a)see.sig.invalid> writes: >> >>> 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: > [snip] > >>It is not said that the other values are without repeatition! >> >> [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." > > You ignored the beginning of the post that you commented upon. > They aren't discussing the original post with the original > problem. They are discussing the problem stated by Matthew > Francis. Oops! I must confess I didn't follow closely the thread after the initial burst. Sorry. -- __Pascal Bourguignon__ http://www.informatimago.com |