Return to Question

added 9 characters in body; edited tags

Source Link

edited Sep 8, 2017 at 5:39

2.7k
10
22

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 becuasebecause it didntdidn'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 Feedbackfeedback I recievedreceived:

The while (zip_range_list): linewhile (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_rangesreduced_zip_ranges before it's reduced, and then continually referring to the element you just added as reduced_zip_ranges[-1]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)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).

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 becuase it didnt 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 recieved:

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?
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?
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).

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:

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?
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?
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).

Source Link

asked Sep 8, 2017 at 5:29

Andrew Parmar

Return a minimum number of ranges from a collection of ranges

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 becuase it didnt 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 recieved:

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?
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?
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[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

python algorithm