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:
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?
- Adding a range to
reduced_zip_rangesbefore 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?
- 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.
- 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?
- 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) 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], reduced_zip_ranges[-1] range_check = range(low-1, high+2) if zip_range in range_check or zip_range in range_check: reduced_zip_ranges[-1] = min(reduced_zip_ranges[-1], zip_range) reduced_zip_ranges[-1] = max(reduced_zip_ranges[-1], zip_range) else: no_overlap_ranges.append(zip_range) zip_range_list = no_overlap_ranges return reduced_zip_ranges