[Solution]Problem 84: Discover minimum transmission range [Spotify]
Arrays, Problem Solving, Reframing
Hey, it’s your favorite cult leader here 🐱👤
On Thursdays, I will send you a problem + its solution. These solutions will help you reinforce your fundamental concepts, improve your problem-solving, and kill those coding/tech/software engineering Interviews. 🔥🔥💹💹
To get access to all my articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!
p.s. you can learn more about the paid plan here.
How did you do?
I’d love to hear it.
Problem
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. This is important because rushing ahead can lead to missing crucial details that would otherwise make your solution process smooth sailing. Rushing ahead saves you seconds, but comes with the risk of wasting minutes.
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. This might seem trivial but will be very important when we get to the optimization.
For now, let’s get back to the problem. There aren’t many plans of attack here. Nothing too obvious. So we go to one of the tried and tested techniques for solving such problems- figuring out the brute force solution and then optimizing that.
Step 2: The Brute Force
If costs were not a constraint, what would our code look like? What would the easiest way to proceed?
One 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? Let’s identify inefficiencies in our current solution and we see what we can do.
Notice that currently, we have a lot of wasted effort. Every new user goes through the entire tower list. This compounds our costs very quickly. What we want to do is minimize this search for the closest tower for any given user. This leads to a next point of action-
Step 3: Sorting
What if we chose to sort the towers? Then we can find where each listener lies along this sorted list, and determine the distance of their closest tower. The expensive process- sorting - happens only once and it will pay dividends throughout. 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_rangeFor 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).
Where do we go from here? Technically you’re done, but for a problem like this- you can go into a bonus step in your interviews, to really blow them away.
Step 4: Going back to the problem
You remember how I always say that optimizations can be found in going back to the problem and looking for key details (at least I say this all the time in my head)? This is one such case, where we have to think about the problem statement given to us and look into it with more focus.
Given the detail, of this problem, the arrays given to us are likely to be sorted. In your interview, make sure you ask your interviewer if they are sorted before you dive into the solution. If they say yes, you have saved a lot of time (and your interviewer will not be turned off by your haste). If the interviewer says n0, you still win for a simple reason- you show your interviewer that you’re someone who can think outside the box and create solutions specific to the context of your challenges. This is a very attractive trait, and one that helped this rockstar engineer get promoted very quickly. I picked this problem to drill this point home.
Assuming they are sorted, 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_rangeTime Complexity- O(M+N)
Space Complexity- O(1), since you aren’t using an extra array (towers is already given to you). O(N) overall
Loved the post? Hate it? Want to talk to me about your crypto portfolio? Get my predictions on the UCL or MMA PPVs? Want an in-depth analysis of the best chocolate milk brands? Reach out to me by replying to this email, in the comments, or using the links below.
Stay Woke,
Go kill all,
Devansh <3
Reach out to me on:
Small Snippets about Tech, AI and Machine Learning over here
Instagram: https://www.instagram.com/iseethings404/
Message me on Twitter: https://twitter.com/Machine01776819
My LinkedIn: https://www.linkedin.com/in/devansh-devansh-516004168/
My content:
Read my articles: https://rb.gy/zn1aiu
My YouTube: https://rb.gy/88iwdd