Erect the Fence

Erect the Fence

What is this problem about?

The Erect the Fence interview question is a classic geometry problem known as finding the Convex Hull. You are given an array of points representing the locations of trees in a garden. You need to find the coordinates of the trees that should be used as fence posts to enclose all the trees with the minimum amount of fence. The fence must be a convex polygon.

Why is this asked in interviews?

Companies like Google and Amazon ask the Erect the Fence coding problem to test a candidate's knowledge of geometry interview pattern and computational geometry. It evaluates your ability to work with vectors, cross products, and sorting in 2D space. It’s a challenging problem that requires a systematic approach to handle collinear points and winding orders.

Algorithmic pattern used

The most common algorithms for this are Monotone Chain or Graham Scan.

1. Monotone Chain Algorithm:
   • Sort points by x-coordinate (and y-coordinate for ties).
   • Build the "lower hull" by iterating through points and using the cross product to ensure every turn is counter-clockwise.
   • Build the "upper hull" by iterating backwards and doing the same.
   • Combine the hulls and remove duplicates.
2. The cross product of vectors (p1, p2) and (p2, p3) tells you if the turn is left, right, or straight.

Example explanation

Suppose you have points: (1,1), (2,2), (2,0), (2,4), (3,3), (4,2).

1. Sort them.
2. Start building the hull.
3. If adding a point creates a "concave" turn (checked via vector cross product), the previous point is not part of the fence and is removed.
4. Eventually, you are left with the boundary points: (2,0), (4,2), (2,4), (1,1).

Common mistakes candidates make

• Collinear Points: Not including points that lie exactly on the line between two fence posts. The problem usually asks for all points on the boundary.
• Floating Point Issues: Using trigonometry when simple cross-product integer math is more accurate.
• Winding Order: Not being consistent with clockwise vs. counter-clockwise checks.

Interview preparation tip

Memorize the 2D cross product formula: (x2-x1)*(y3-y2) - (y2-y1)*(x3-x2). A positive result means a left turn, negative means a right turn, and zero means the points are collinear.