Andrew Tomazos <andrew@tomazos.com> writes:
> 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[i] = 0;
>
> for (int i = 0; i < n; i++)
> for (int j = 0; j < 32; j++)
> if (p[i] & (1 << j)) // if bit j is on
> count[j]++;
> else
> count[j]--;
>
> int x = 0;
> for (int i = 0; i < 32; i++)
> if (count[i] > 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-equivalant" experience/knowledge of
> computer science and math. Should I have been able to come up with
> this solution without prompting or help?
If what you're asking is whether anybody having a master in CS and
maths would have been able to come up with this solution in the
interview time, I guess we can answer that definitely no, otherwise
there would be no point in trying to select candidates with this test.
Obviously, it's because some people (with or without a master diploma,
this really isn't relevant) get or don't get it, that this test is
useful for the recruiter.
Now if you want this kind of jobs, yes you should better be able to
come up with smart solutions to little puzzles like this in
interviews.
> 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?
Not a single one. You have to develop your knowledge of algorithms,
mathematics, your symbolic thinking and your imagination in these
matters.
> 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"?
That could help yes. I'd tend to think that imagination is the most
important ingredient here, to be able to come with a possible solution
fast enough.
Also, don't limit yourself to CS and maths, there are ideas to be
taken from other domains too.
> 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?
CS IQ, yes, if such a IQ test exists.
> Some people have the talent to solve the puzzle, see the pattern and
> come up with the solution - and some just don't?
It seems so. At least, in a given time.
--
__Pascal Bourguignon__