Heaters

Heaters

What is this problem about?

The Heaters interview question is an optimization problem involving two sets of coordinates: houses and heaters. You need to find the minimum possible "radius" for the heaters such that every house is covered by at least one heater. All heaters will have the same radius. A house at position $x$ is covered by a heater at position $y$ if the distance $|x - y|$ is less than or equal to the radius.

Why is this asked in interviews?

Companies like Google, Amazon, and Microsoft ask this to evaluate a candidate's ability to search through large coordinate spaces efficiently. It tests your knowledge of Binary Search interview patterns and Two Pointers interview patterns. The problem can be solved in multiple ways, allowing the interviewer to see how you weigh different time-space trade-offs. It also requires careful handling of sorted vs. unsorted input data.

Algorithmic pattern used

There are three main ways to approach the Heaters coding problem:

1. Binary Search on Heaters: Sort the heaters array. For each house, find the two closest heaters using binary search (one to the left, one to the right). The required radius for that house is the minimum of those two distances. The global answer is the maximum of these individual radii.
2. Binary Search on Answer: Binary search for the radius value itself (from 0 to the max coordinate). For each radius, check if all houses are covered.
3. Two Pointers: Sort both houses and heaters. Use two pointers to find the closest heater for each house in a single pass.

Example explanation

Houses: [1, 5], Heaters: [2]

1. House 1 is at distance 1 from Heater 2.
2. House 5 is at distance 3 from Heater 2.
3. To cover both, the radius must be at least 3. Result: 3.

Common mistakes candidates make

• Not Sorting: Failing to sort the arrays before applying binary search or two pointers, leading to incorrect results or $O(N^2)$ complexity.
• Incorrect Closest-Heater Logic: Only checking the heater to the left of a house and forgetting the one to the right.
• Complexity: Implementing an $O(N imes M)$ solution which will time out for large inputs.

Interview preparation tip

When you need to find the "closest" element in a collection for many queries, sorting and binary search are your best friends. Practice the bisect module in Python or Arrays.binarySearch in Java to efficiently find "insertion points" in sorted data.