On 26 Jun 2008, at 8:14 am, Andrew Wagner wrote:
6.) You have a [(WeatherStationId, Latitude, Longitude)]. Similar to #3, write a function which will, off-line, turn this into a data structure from which you can easily determine the nearest Weather Station, given an arbitrary Latitude and Longitude.
I actually set something not entirely unlike this as a problem in a 4th year OO class. Despite telling them over and over and over again that the Earth is not flat, and despite telling them how to convert (Latitude, Longitude) to 3-dimensional coordinates on the unit sphere, and despite telling them that greatest circle distance between two points on the surface of the Earth is a monotone function of Euclidean distance between points on the unit sphere, so that all they had to do was to glue these pieces together, EVERY SINGLE ONE used Euclidean distance between (Latitude, Longitude) pairs as if they were co-ordinates on a flat 2-d plane. And we even live near the International Date Line, which is where this mistake goes horribly wrong. Did they score you on coding or on geometry? For what it's worth, a 3-dimensional kd tree really flew on this problem.