Interview Question - Validate Page Range

Question

I applied for a job position in a software company some time ago. They emailed me the following question and asked me to solve it in one day, but I failed to do so. Today I looked back at this question (to prepare for other interviews) and managed to write a solution, though it is lengthy and not optimized. I would like to see whether there's a better solution.
_______________________________________________________________________
Here's the question:

Given the 4-line testbench as below:
isPageRange(1, '1,2,5-7,9-') # true
isPageRange(6, '1,2,5-7,9-') # true
isPageRange(12, '1,2,5-7,9-') # true
isPageRange(3, '1,2,5-7,9-') # false

Create the function isPageRange().
The first parameter is the page number.
The second parameter is a string representing a range.
The comma in the range represents 'and', the dash in the range represents 'to'.
________________________________________________________________________

Here's my solution:
https://code.sololearn.com/cA23A9a4A18a/#py

Answer 1

Firstly, I like your general approach. It's clean, and gets the job done.

Whenever you have a nested loop like on lines 27-30 of your code, it's a good idea to think about whether you can somehow eliminate one of those loops.

Let's step away from the code for a second and think instead about what our "plan" is for the code. I won't go into it here, but take a look over at this site for a really cool and useful thought-process for thinking about interview questions: https://www.fullstackacademy.com/blog/how-to-ace-a-technical-interview-reacto

What *really* are we asking to do here? We're looking to see if a page (our first argument) is either:
1) *exactly* equal to one of the single-number elements in our list, or
2) included in the range denoted by an "a-b" format.

Okay, so we have two major "ways" of finding our page. As such, it's likely we'll need two different methods for finding our page. Before we do that, however, let's take a minute and actually convert our string list of ranges to an array:

range = range.split(',')

Next, let's loop thru and look at each element. I'd actually use a for-in loop here, since it's clearer what your intentions are:

for rng in ranges:

Either way, we're gonna need some if statements here. Let's first check to see if it's *NOT* a range:

if '-' not in rng:

We can add another nested if statement to check if that single number == our page, or we can just use "and":

if '-' not in rng and int(rng) == page: return True

next, we need a nested if:

elif page>=int(rng.split('-')[0]): #if our page is >= the FIRST number in the list

Finally, let's check to see if we have a maximum for our range. If the current range string ends with '-', then we dont; if page<= our first number in the range, return true. Otherwise, split the string at '-' and take the second (1th) element. If our number is > the 0th number and < the 1th element, return True

Otherwise, return false.
Here's my edit: https://code.sololearn.com/ca251a5A16A2

Answer 2

Nice challenge!

Regarding your code:

The logic is basically straight forward, but I find it quite hard to read.

Variable names are very cryptic. A good name should represent the purpose of the variable.

It is lengthy because it does every step seperately and "by hand". For example the first two loop are for data preparation and could be done as one. If a condition is True in the third loop you could directly return True. This would make the last loop obsolete.

If you want to convert all strings to numbers (second loop) you could use map()

Here is my try:
https://code.sololearn.com/c4A4A30a17a2

Answer 3

@HealyUnit @Benjamin Jürgens
Thanks a lot for your replies! I can't believe this can be done in a single loop, and there were so much to be improved in my code. It seems that I need to train myself more in Python...

I guess I wrote the solution in a rather "C++ way", since I used C++ more in the past.

Anyway, your solutions teach me some Python features that I didn't knew (especially the "if '-' in range", didn't knew we can parse through characters in string this way). Really appreciate your help, and hope you two have a nice day.

Answer 4

You are right about your coding style, I guessed that you have a C/C++ background.

Python is much closer to spoken language than most programming languages. For many small challenges the python code is like a translation of the description, depending on the description of course.

C# goes a similar way, there it is called fluent code / fluent api. But python code is much shorter

Answer 5

@Hanz Firstly, you're very welcome!
I personally come from a heavy JavaScript background, so most of my Python code probably "smells" JavaScript-ish.

As for the "done in a single loop" idea, the reason I latched onto this has to do with a concept known as Time Complexity. Basically, time complexity talks about how much, for a given input size *n*, the amount of time it takes for a function increases. It's important to note that it's often not an exact number, but more of a "sense" of difference. For example:

#assume len(range1) == len(range2)
def nested_func(range1,range2):
for num_a in range1:
for num_b in range2:
#do something with num_a, num_b

def parallel_func(range1,range2):
for i in range (0,range1):
num_a = range1[i]
num_b = range2[i]
#do something

Which of the above functions runs "faster"? Imagine we're given two arrays of 10 elements. The first function runs 10x10 = 100 times, while the 2nd function only runs 10 times.

It's also important to note that brevity is absolutely not everything. For example, here's a rather difficult-to-read solution that, while it is surprisingly compact, doesn't really help; it's not readable, and would likely just get you frowned at:

def isPageRange(targ,ranges):
return len(list(filter(lambda r:('-' in r and targ>=int(r.split('-')[0]) and (r.endswith('-') or targ<=int(r.split('-')[1]))) or ('-' not in r and int(r)==targ), ranges.split(','))))>0

It's likely there's an even *shorter* version, but... no one is going to want to read that.