Loops, List, Binary Search
A simple solution for this iterates over the holes, and, for each hole, iterates over the cafes. It then finds the minimum travel distance between that hole and each cafe. It keeps track of the worst-minimum-difference it finds.
def furthest(num_holes, cafes):
"""Find longest distance between a hole and a cafe."""
# START SOLUTION
worst = 0
for hole in range(num_holes):
# Looking at all cafes, find distance to this hole,
# and choose the smallest distance.
dist = min([abs(hole - cafe) for cafe in cafes])
# Keep track of the longest distance we've seen
worst = max(worst, dist)
return worst
That solution works fine, but the runtime is O(num_holes * num_cafes), since we scan each cafe for each hole. If you had a large number of holes and cafes, this would perform very badly.
STOP. Think about ways you could improve this. Is there a way to search a list for a value quickly?
A better solution would let us find the nearest hole for a cafe quickly. We can use binary search for this.
In this approach, we’ll use binary search to find the location where we’d insert each hole into the cafes list. We have four cases to consider:
this hole is after all cafes, so find the distance to the last cafe
this hole is before all cafes, so find the distance to the first cafe
this hole is a cafe (so distance is zero)
this hole is between two cafes, so find the smallest travel distance between them
This search is done for each hole, so the runtime is O(num_holes * log num_cafes). (Binary search is logarithmic, and we do that num_holes number of times.)
We could write our own binary search, but Python includes one the standard library, bisect. We’ll use this.
def furthest_optimized(num_holes, cafes):
"""Find longest distance between a hole and a cafe.
This solution uses binary search to quickly find the one or two cafes
closest to the hole. This makes problem O(n log n), rather than O(n**2).
"""
from bisect import bisect_left
worst = 0
for hole in range(num_holes):
# Find the place we'd insert this hole into the
# sorted cafes list.
idx = bisect_left(cafes, hole)
if idx == len(cafes):
# This hole is after all the cafes, so the distance
# is from this hole to the cafe before it
dist = hole - cafes[idx - 1]
elif idx == 0:
# This hole is before all the cafes, so the distance
# is from this hole to the cafe after it
dist = cafes[idx] - hole
elif cafes[idx] == hole:
# This hole is a cafe, so no travel is needed!
dist = 0
else:
# This hole is between two cafes, so use the smaller
# distance between them
dist = min(hole - cafes[idx - 1], cafes[idx] - hole)
# Keep track of the longest distance we've seen
worst = max(worst, dist)
return worst
There’s an even better solution — but it requires some clever recognition about the problem.
We can simply measure the distance between cafes in a single loop:
find the distance from the left edge to the first cafe; this is the distance a lemming in the first hole would have to travel.
find the distance from the right edge to the last cafe; this is the distance a lemming in the last hole would have to travel.
find the distance from every cafe (except the first) to the cafe to its left; a lemming in this gap would have to travel half that distance (half since it has a choice of whether to go left or right)
This code is simple and linear.
def furthest_best(num_holes, cafes):
"""Find longest distance between a hole and a cafe.
This solution looks at the cafes, finding the two that are furthest
apart, and then determining which lemming hole would have to travel
the furthest between them.
"""
# Start with the distance from first hole to the first cafe, and from
# the last hole to the last cafe:
distances = [cafes[0],
num_holes - cafes[-1] - 1]
for i in range(1, len(cafes)):
# between cafes: distance is half the distance to leftward cafe
distances.append((cafes[i] - cafes[i - 1]) // 2)
return max(distances)
An Engineering Parable
This challenge was written by a Hackbright developer with decades of experience in computer programming. He found the original solution and the binary-search solution.
A Hackbright student found the best, O(n), solution!
The author of this problem was suitably chastised, but also realized that in writing this problem, he had googled for images of lemmings, written paragraphs about them, and was pretty focused on lemmings as the heroes of the story.
The student didn’t arrive with that mindset, and she saw much more clearly that the problem is more about the cafes, and scanning that list, than it is about scanning the list of lemmings.
This is a good lesson about stepping back from a problem and thinking carefully about whether you arrive with a bias about what you think it’s about: is this really a recursion problem, just because the most recent problem you did was about recursion?
Letting go of preconceptions and being able to think creatively about problems is a core skill for developers.