Lazy Lemmings
- Whiteboard
- Challenge
- Concepts
Loops, List, Binary Search
- Download
- Solution
Lemmings are small rodents that live in arctic biomes. Unlike many other creatures that live in such cold climates, they do not hibernate, but survive the winter by burrowing into holes and looking for food.
On a particular island, there are num_holes number of lemming holes, arranged in a line, each 1 meter apart. Some of these lemming holes have food (we’ll call these holes “cafes”)
You can imagine this like this:
The black-filled holes are cafes.
Imagine there’s a lemming currenly in each hole, and they’re all hungry. The lemmings in hole #3 and #5 don’t need to travel at all, but the other lemmings need to travel to find the nearest cafe:
the lemming in hole #1 needs to travel 2m to hole #3
the lemming in hole #2 needs to travel 1m to hole #3
the lemming in hole #4 needs to travel 1m to hole #3 (or 1m to hole #5)
the lemming in hole #6 needs to travel 1m to hole #5
In this problem, you want to calculate the longest amount, in meters, any lemming needs to travel to get food. For this example, the answer would 2, since lemming in hole #1 needs to travel 2m to get to the nearest cafe.
The Challenge
You’ll be given two pieces of information:
- num_holes
The number of holes
- cafes
The indexes of those holes with food in them (note that these indexes are zero-based). This list is sorted, and a single hole will only appear at most once in it.
You should return a single integer, for the maximum distance any of the lemmings need to travel.
Advanced
There’s an easy solution for this, but it has poor runtime.
Once you’ve found a solution, see if you can find a better solution for it (though this is more advanced, and would make this a very hard whiteboard problem, and an intermediate code challenge).