A
Andrew Tomazos
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 = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 32; j++)
if (p & (1 << j)) // if bit j is on
count[j]++;
else
count[j]--;
int x = 0;
for (int i = 0; i < 32; i++)
if (count > 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?
Would you expect someone with a CompSci Masters or PhD from some major
ivy league university to be able to come up with this solution without
help?
If so in what course or from which book would you expect to learn the
required knowledge to come up with the above solution?
Is the skill to be able to come up with such an algorithm something
that is learned by studying lots of algorithms and being able to mix
and match the "tricks"? If so, what is a similar commonly known
algorithm(s) on which the above solution could have been based?
Or, is the ability to invent such a solution simply a matter of IQ?
Some people have the talent to solve the puzzle, see the pattern and
come up with the solution - and some just don't?
Thanks,
Andrew.
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 = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < 32; j++)
if (p & (1 << j)) // if bit j is on
count[j]++;
else
count[j]--;
int x = 0;
for (int i = 0; i < 32; i++)
if (count > 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?
Would you expect someone with a CompSci Masters or PhD from some major
ivy league university to be able to come up with this solution without
help?
If so in what course or from which book would you expect to learn the
required knowledge to come up with the above solution?
Is the skill to be able to come up with such an algorithm something
that is learned by studying lots of algorithms and being able to mix
and match the "tricks"? If so, what is a similar commonly known
algorithm(s) on which the above solution could have been based?
Or, is the ability to invent such a solution simply a matter of IQ?
Some people have the talent to solve the puzzle, see the pattern and
come up with the solution - and some just don't?
Thanks,
Andrew.