This post originated from an RSS feed registered with Java Buzz
by Paul Brown.
Original Post: Great Interview Question - Part II
Feed Title: mult.ifario.us
Feed URL: http://feeds.feedburner.com/MultifariousCategoryJava
Feed Description: Software. Business. Java. XML. Web Services.
Here's the question that I posted earlier:Given a set of random points in the plane, how many of them are colinear?There are two kinds of answers.
The first kind answer is on the path that I think most people would follow. Given the random set of points S={(x1,y1),(x2,y2), ...}, there is a corresponding set of lines of the form ax+by=c that are defined by the points taken two at a time. The question is then how many of the unit vectors that correspond to the 3-tuples (a,b,c) are equal up to sign, and it is a computational problem. This then brings up the more software-relevant question of efficiently computing the highest multiplicity element in a multiset.
The second kind of answer is on the more interesting path. For all intents and purposes, the answer is 2, since the probability that any three randomly-selected points are colinear is zero. (This assumes that the points are truly random, and the question of the probability that three of the points are colinear if their coordinates are rounded to the nearest machine-precision number is a much more challenging question.)
Sometimes having the answer isn't as valuable as knowing how much good the answer actually does you.As for the manholes, that one's played-out, I'm afraid.
Previous Topic
