[Solution]Problem 10: Discover minimum transmission range [Spotify]

Hard

Problem

This problem was asked by Spotify.

You are the technical director of WSPT radio, serving listeners nationwide. For simplicity's sake, we can consider each listener to live along a horizontal line stretching from 0 (west) to 1000 (east).

Given a list of N listeners, and a list of M radio towers, each placed at various locations along this line, determine what the minimum broadcast range would have to be in order for each listener's home to be covered.

For example, suppose listeners = [1, 5, 11, 20], and towers = [4, 8, 15]. In this case, the minimum range would be 5, since that would be required for the tower at position 15 to reach the listener at position 20.

Step 1: Framing

We need to approach such problems by first understanding the framing/setup of the problem. Unlike most problems, we are not dealing with location as points (2D) but a single index. We also know that people will live at most within a certain bound. Thus we can set up the solution with these bounds in mind.

The easy approach would be to go through the users. For every user iterate through the towers find the closest one, and calculate the range. The maximum from tower-user pair will be the minimum range we need to reach out to customers.

The problem with this approach is that will be O(n^2). Can we cut it down further?

The easy approach is to simply sort the towers. Then we can find where each listener lies along this sorted list, and determine the distance of their closest tower. The distance that suffices for the worst-case listener will be the overall solution.

To make things more convenient, we can add an imaginary tower at negative infinity on the left, and at positive infinity on the right, so that there will always be two towers to choose from for each listener.

def search(listener, towers):
    start = 0; end = len(towers) - 1

    while start < end:
        mid = start + (end - start) // 2

        if towers[mid] < listener:
            start = mid + 1
        elif towers[mid] > listener:
            end = mid
        else:
            return mid

    return start

def find_broadcast_range(listeners, towers):
    min_range = 0
    towers = [-float('inf')] + sorted(towers) + [float('inf')]

    for listener in listeners:
        idx = search(listener, towers)

        left = listener - towers[idx - 1]
        right = towers[idx] - listener

        min_range = max(min_range, min(left, right))

    return min_range

For such a solution we have two parts: sorting the towers and searching from users. For M towers, the sorting is M log M. Searching along users is N log M (each search is log M repeated N times). Thus the total complexity is O( (M+N) log M).

Step 2: Context

Now we think of the context of the problems. Since we are dealing with addresses along a single index, they are likely to be sorted. In your interview, make sure you ask your interviewer if they are sorted.

Assuming they are, we don’t need to follow the sorting. What happens if listeners are also sorted? We can slide along both arrays to find the towers to either side of the listener. We just compare the distance, and the minimum will be the range required for that specific user. Once again, the maximum of these values will be the range we need.

def find_broadcast_range(listeners, towers):
    min_range = 0; i = 0
    towers = [-float('inf')] + towers + [float('inf')]

    for listener in listeners:
        while listener > towers[i + 1]:
            i += 1

        curr = min(listener - towers[i], towers[i + 1] - listener)
        min_range = max(min_range, curr)

    return min_range

This approach will take O(M+N) time.

Bonuses/Promotion (Get Free Stuff)

Have anything to say to me? Use the links below.

To learn how to interview better DM me. Let’s set up mock interviews and go over different interview techniques. In addition to focused questions, and a detailed personalized plan, we will go over the right questions to ask during your interviews.

To share interesting problems/solutions with me, reach out to me. Different social media of mine also have other content from me. Good problems and/or solutions receive a free shoutout + 2 months of the paid newsletter:

Reach out to me on Instagram: https://www.instagram.com/iseethings404/

Message me on Twitter: https://twitter.com/Machine01776819

My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/