VoltInsider

The Line Intersection Interview Question

December 6th, 2009

Over the past 24 months or so I’ve noticed what seems to be a trend in hiring at technical companies like Microsoft and Google. It appears that jobs are becoming more specialized and that this is leading to sort of a two-tiered work force where employees are either on the relatively high-skill end (such as specialized systems developers) or on the relatively low-skill end (such as purely manual testers). Anyway, one effect is that interview questions are becoming increasingly technical in order to categorize potential employees. Recently I observed an interview. One of the questions ran along the lines of, “Suppose you have a collection of horizontal and vertical line segments in a plane. How can you determine which line segments intersect with each other?” As usual, the first step is to qualify the question because it has a lot of ambiguity. Next you’d draw the problem on the omni-present whiteboard and begin analyzing the question. It turns out that this is a standard problem you’d go over in a Intermediate Data Structures and Algorithms class in college and it has a pretty standard answer. The details are a bit complicated but basically you perform a virtual scan, using a horizontal line, from the bottom of the plane to the top. When you hit the bottom endpoint of a vertical line segment you add that line to a tree structure. When you hit any point on a horizontal line segment, you check to see if it intersects any of the lines currently in the tree structure. When you hit the top endpoint of a vertical line segment, you remove it from the tree. This is difficult to explain in words but combined with white-boarding you should satisfy your interviewer if you get this interview question.

Entry Filed under: Interviewing