[Haskell-cafe] Haskell, Microsoft, and interview questions

[Richard A. O'Keefe]

On 27 Jun 2008, at 3:11 am, Andrew Wagner wrote:
For what it's worth, a 3-dimensional kd tree really flew on this  
problem.
>>
> I did some reading up on this, and it seems interesting. It would be
> need to implement something like this in Haskell, but I can't seem to
> find any detailed specs on the data-structure. Got any
> recommendations?

http://en.wikipedia.org/wiki/K-d_tree
is perhaps the obvious place to start.
There's a link there to Jon L. Bentley's original (1975) paper,
which is really very clear.  The key to getting an efficient
version in C was to specialise the code to the particular k that
I wanted (k=3).

Of course there are much newer data structures that can do all sorts
of things, but for simply finding the closest point in 1, 2, 3, or
4-dimensional space k-d trees are darned good.  There isn't much that
works well for high dimensions.  Last year I marked a 4th year project
that studied/evaluated a comparatively recent data structure that was
said to be good for high dimensions.  I had difficulty understanding
it, because I couldn't see where the recursive step was.  The answer
was that there wasn't one:  the algorithm worked better for high
dimensions than other trees because it turned into a simple linear
search after one partitioning step.  In effect, it was too dumb to
keep tripping over its own feet.  So _really_ don't expect k-d trees
to work well for large k.


>