http://www.velocityreviews.com/forums/(E-Mail Removed) (Richard Harter) wrote:

>Andrew Tomazos <(E-Mail Removed)> 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."

>>

>>The assumption being extra points for efficiency. [snip code] The idea

>>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. [...]

>>

>>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?

>

> That's an interesting question with an interesting presupposition.

> The first thing to understand is that this is a puzzle rather than

> a programming problem.
I disagree. Saying that it's a puzzle rather than a programming problem

seems to imply that the solution is ad-hoc, rather than a special case

of some more universal technique. But that is not true here. Namely,

the proposed solution follows immediately from the obvious fact that

majority elts on product sets are preserved by component projections.

So the solution is simply an instance of well-known divide-and-conquer

techniques for product objects. Such reductions are ubiquitous in both

mathematics and computer science. So I would expect a good student

to find this solution given enough time. I'd also expect a student

from a top-tier school to discover the more optimal solution, viz.

bi != a => Maj({a^k b1 b2... bk} \/ S) = Maj(S)

via m/n > 1/2 => (m-k)/(n-2k) > 1/2 via mediants/arithmetic

again, assuming enough time. But that assumption is highly problematic

when it comes to designing tests that quickly measure various skills.

It's impossible to test such in the short time span of an interview.

It remains difficult even in much longer timed tests. For example

many of the most successful mathematicians did not perform well on

the Putnam competition, and some of those who did well didn't turn

out to be exceptional mathematicians. Thus there isn't necessarily

much correlation between intelligence and random test scores.

Marilyn vos Savant is a prime example. The woman who supposedly

has the "world's highest IQ" published a Parade magazine column [1]

and book [2] on Wiles proof of FLT. Her nonsensical arguments proved

beyond a doubt that she has absolutely no clue about higher math

and, worse, doesn't have the intelligence to know that (even after

many experts pointed out gaping flaws in her very naive arguments).

So much for IQ tests.

--Bill Dubuque

[1] sci.math, 11/29/1993, Full Text of Savant FLT Parade Article

http://google.com/group/sci.math/msg/8cb44534c63372ad
http://google.com/groups?selm=WGD.93...gny.ai.mit.edu
[2] Boston, Nigel; Granville, Andrew.

Review of: The World's Most Famous Math Problem (The Proof

of Fermat's Last Theorem and Other Mathematical Mysteries)

by Marilyn vos Savant

The American Mathematical Monthly, 102, 5, 1995, 470-473

http://www.dms.umontreal.ca/~andrew/PDF/VS.pdf
http://www.jstor.org/stable/2975048