Math/CompSci Interview Question - Thoughts?

[Ilmari Karonen]

["Followup-To:" header set to sci.math.]

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.

 

[Mathew Francis]

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.

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

 

[Pascal J. Bourguignon]

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 == lastval)
{
done = 1;
}
else
{
lastval = arr;
}
}
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 J. Bourguignon]

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.