Re: Offtopic: How to Design Programming Tests

[Shriram Krishnamurthi <sk@cs.brown.edu>]

Michael Bogomolny wrote:

> Another question I often ask: assume you have a(n unordered) set of
> numbers, and you know nothing about the range or distribution of the
> numbers. How would you go about finding if there exist two numbers in
> the set that add up to m?  This question tests their mastery of data
> structures. Everyone gets the dumb n^2 method first, the better ones
> upon more thought decide to do a sort first and get a n log n
> solution, and the occasional standout thinks about creating a hash
> table to get a near-linear solution.

I would think the real standout would ask you why you want to do this,
where the numbers are coming from, whether the problem is on-line or
off-line, how many numbers there are likely to be, who's expecting
them, how much space you have, whether an approximate solution is
acceptable and, if so, with what tolerance, and why this problem
matters.  Each answer affects which solution is most appropriate, and
some introduce many more solutions than the ones you list.

Problems without contexts are puzzles.  An interview that poses
puzzles rather than problems may not yield the most desirable results.
Remember Part 10 (Galileo was Right) of From the Earth to the Moon?

Shriram