Saturday, December 31, 2011

Line segment intersection

It looks like an easy problem, it has a trove of information on it and Bryce Boe even has a two line solution for it. However, his program does not handle improper intersections, i.e. when one end of one of the segments lies on the other line. Since a point lying on the line does not make triangles with different orientations (since it has zero area), his program does not count it as an intersection.

The highest voted answer on the stack overflow question needs special care while handling vertical lines (And it is general outline for a solution, not actual code).

Now there are multiple methods of correcting these problems, and this is one of them:


Use this function to test the implementation:





Tuesday, December 20, 2011

Numerically stable standard deviation calculation and code perforation

How would you implement a class which has an append(double x) function to collect values, and a get_std_dev() function which returns the standard deviation of the values collected?

Sounds like an easy problem, here is my guess at what your code would look like:


This looks like an standard implementation, but it contains some subtle bugs. These bugs do not show up in regular usage, but they lie patiently in wait. Remember the tricky binary search implementation bug which escaped detection in the JDK for about a decade and is now staple fodder of all technical interviews?