Return a minimum number of ranges from a collection of ranges

Question

I'm new to Python and SWE in general so excuse the simple questions. I was given the following coding challenge by an interviewer. And I came up with the following solution. But I was passed over because it didn't meet their performance criteria. I was wondering if anyone could give me pointers on how I can do better on this question and in general for questions like this. I've found other answers solving the question, but I wanted specific answers to my implementation.

Here is the feedback I received:

1. The while (zip_range_list):line sticks out: you don't see a lot of while loops in Python, you don't have to put parentheses around the test expression, and solving this problem with a while loop is a weird thing to do. Why are while loops a bad idea?
2. Adding a range to reduced_zip_ranges before it's reduced, and then continually referring to the element you just added as reduced_zip_ranges[-1] instead of having a separate binding for it reads awkwardly. Why is this awkward?
3. The construct range_check = range(low-1, high+2) may be correct, but it's both strange to look at and ridiculously space-wasteful: instead of comparing endpoints he builds a list of the entire range of numbers just to check membership in that range. He builds these over and over again in a loop within a loop. I see the point here. I was trying to avoid a long if-statement. Wasn't a good idea.
4. Speaking of "loop within a loop", this is an O(N-squared) algorithm when it could have been O(N) after the sort. I guess I overlooked this, I see 0(n^2) now. How can I avoid this?
5. The routine has two different non-exceptional return points; the one within the loop is unnecessary (the code works as well with it commented out).

PROBLEM Given a collection of zip code ranges (each range includes both their upper and lower bounds), provide an algorithm that produces the minimum number of ranges required to represent the same coverage as the input.

Input: [[14,17], [4,7], [2,5], [10,12] , [15,16], [4,9], [11,13]]
Output: [[2,17]]


# Implementation
def zip_range_reducer(zip_range_list):

    if not zip_range_list:
        raise Exception("Empty list of ranges provided!")

    reduced_zip_ranges = []

    zip_range_list.sort()

    while (zip_range_list):
        no_overlap_ranges = []
        reduced_zip_ranges.append(zip_range_list[0])
        if len(zip_range_list) == 1:
            return reduced_zip_ranges
        zip_range_list.pop(0)
        for zip_range in zip_range_list:
            low, high = reduced_zip_ranges[-1][0], reduced_zip_ranges[-1][1]
            range_check = range(low-1, high+2)
            if zip_range[0] in range_check or zip_range[1] in range_check:
                reduced_zip_ranges[-1][0] = min(reduced_zip_ranges[-1][0], zip_range[0])
                reduced_zip_ranges[-1][1] = max(reduced_zip_ranges[-1][1], zip_range[1])
            else:
                no_overlap_ranges.append(zip_range)
        zip_range_list = no_overlap_ranges

    return reduced_zip_ranges

Answer 1

I’ll try to go over your five points. Keep in mind that I’m not your interviewer and my interpretation might not be what they really meant.

1. While loops are not bad per se, but they are not the preferred way to iterate over a datastructure. I started solving the exercise also using a while loop to reduce a partially reduced list until reaching a fixed point. But I realized that, once the original list is sorted, you only need a single pass (more on that later). This is why solving this problem with a while loop is a weird thing to do.

2. Compare these toy examples:

   counts = []
   running_total = 0
   for amount, should_separate in some_input:
       running_total += amount
       if should_separate:
           counts.append(running_total)
           count = 0
   

   and

   counts = [0]
   for amount, should_separate in some_input:
       counts[-1] = counts[-1] + amount
       if should_separate:
           counts.append(0)
   

   even though the second one is shorter, the core of the computation (counts[-1] = counts[-1] + amount) loose its readability due to the indexing. Plus, using one less variable, you lose the opportunity to document the code using an expressive name.

3. I’m assuming Python 2 here, as in Python 3 range produces a range object, pretty much the same as xrange in Python 2. So yes, use xrange instead, you’ll save both on memory and time as checking if an element is in a list is \$\mathcal{O}(n)\$. But for such simple checks where you already have the bounds up-front, you can use the shorthand comparisons: if low - 1 <= value <= high + 1:. Especially given the fact that:
4. Once the list is sorted, only two consecutive ranges can be part of the same "mega"range. If they are not, then you know your output contains another "mega"range that starts at this moment because no other element will start before this new range. This also simplifies the check for range inclusion as you only need to check for the lower bound of the current element to be in the current range; and since items are sorted, you know that that lower bound won't be lower than the lower bound of the current range either.
5. The ….pop(0) will make the for loop a no-op when initial length is 1, so the loop will stop itself on the next iteration, so the len(…) == 1 check is really redundant with the rest of your code. Drop code that serve no purpose as it is error-prone.

Others remarks I can make:

1. Why generate an exception on empty input? Simply return an empty list as output: no range in, no range out, I don't see any problem. You won't even enter the while so return an empty list anyway, again, this code is somewhat redundant with the rest.
2. Why modify the original list by .sort()ing in place? Since you return a different result, you should not modify the input.

---

Proposed improvements:

def zip_range_reducer(ranges):
    if not ranges:
        return []

    ranges = sorted(ranges)
    reduced = []

    lowest, highest = ranges[0]
    for low, high in ranges:
        # Since we sorted ranges, we know of overlapping
        # ranges by this only check.
        if low <= highest + 1:
            lowest = min(lowest, low)
            highest = max(highest, high)
        else:
            reduced.append([lowest, highest])
            lowest = low
            highest = high
    reduced.append([lowest, highest])

    return reduced

Another interesting way to put this code and remove the boilerplate (empty check, first item extraction) is to use an helper generator function that will trigger interesting behaviours of how iteration works in Python:

def zip_range_reducer(ranges):
    ranges = iter(sorted(ranges))
    return list(_zip_range_helper(ranges))


def _zip_range_helper(sorted_ranges_iterator):
    lowest, highest = next(sorted_ranges_iterator)

    for low, high in sorted_ranges_iterator:
        # Since we have sorted ranges, we know
        # of overlaping ranges by this only check.
        if low <= highest + 1:
            lowest = min(lowest, low)
            highest = max(highest, high)
        else:
            yield [lowest, highest]
            lowest = low
            highest = high

    yield [lowest, highest]

Here the empty check is implicit by the fact that next will raise StopIteration when ranges is empty. But this StopIteration will be interpreted by list() as "there is no more elements to put in here" and an empty list will be returned. Otherwise the first element will be consumed to populate lowest and highest; and each element of the resulting list will be yielded one by one.

Answer 2

As I completely misunderstood the question before, here is my second try.

from operator import itemgetter
from itertools import groupby

def r_reduce(r):   
    # Building set items in the range
    range_set = set()
    for sublist in r:
        range_set = range_set | set(range(sublist[0], sublist[1]+1))

    # ! When using the example input !
    # At this stage sets is {2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17}

    # And you can clearly see this is a full range
    # Now we can chop the set up in smaller sub_ranges

    # Making ranges of the set
    reduced = []    
    for key, group in groupby(enumerate(sets), lambda i: i[0] - i[1]):        
        r = list(map(itemgetter(1), group))
        reduced.append([r[0], r[-1]])
    return reduced

---

When you are overcomplicating stuff things get progressively more difficult and prone to bugs. Shorter most of the time really is better.

Now let's break down your code and review:

1. while loops per se are not a bad idea, it is just using a while loop for this example is overcomplicating stuff. That makes it a bad idea.
2. reduced_zip_ranges[-1] is awkward because you keep appending that item to the list and refering last element, you could also have stored the range as a variable and keep overwritting it.