Coordinate With Maximum Network Quality

Coordinate With Maximum Network Quality

What is this problem about?

In the Coordinate With Maximum Network Quality coding problem, you are given an array of tower locations and their signal strengths, along with a radius. The network quality at any coordinate (x, y) is the sum of the floor of (strength / (1 + distance)) for all towers within the given radius. You need to find the integer coordinate within a bounded area (0 to 50 for both x and y) that has the maximum network quality. If there's a tie, return the lexicographically smallest coordinate.

Why is this asked in interviews?

Lyft uses the Coordinate With Maximum Network Quality interview question to test your ability to implement a simulation based on specific rules. Since the search space is small (51x51 points), it evaluates whether you can correctly translate a mathematical formula into code and handle tie-breaking conditions. It’s a "Medium" problem that focuses on accuracy and enumeration.

Algorithmic pattern used

The pattern is Brute Force / Enumeration.

1. Iterate through every integer coordinate (x, y) where 0 <= x, y <= 50.
2. For each coordinate, calculate the distance to every tower.
3. If distance <= radius, calculate the signal contribution: floor(q / (1 + d)).
4. Sum these contributions to find the total quality at (x, y).
5. Keep track of the (x, y) that yields the maximum sum, following the tie-breaker rule.

Example explanation

Tower at (1, 2) with strength 5, Radius 2. Check coordinate (1, 1):

1. Distance d = sqrt((1-1)^2 + (2-1)^2) = 1.
2. 1 <= 2 (within radius).
3. Contribution: floor(5 / (1 + 1)) = floor(2.5) = 2. Check coordinate (5, 5):
4. Distance d = sqrt((5-1)^2 + (5-2)^2) = 5.
5. 5 > 2 (outside radius).
6. Contribution: 0.

Common mistakes candidates make

• Radius Check: Forgetting to check if the tower is within the radius before adding its signal.
• Tie-breaker: Not returning the lexicographically smallest (x, y) in case of multiple maximums.
• Integer Division: Not taking the floor of the signal strength correctly.
• Floating Point Precision: Using sqrt unnecessarily when comparing distances (it's better to compare d^2 with radius^2 to avoid precision issues).

Interview preparation tip

When the constraints are small (like 0 to 50), don't look for a complex mathematical optimization. A clean, bug-free brute force is exactly what the interviewer is looking for.