2

I've discovered my biggest issue with practicing interview questions and writing software more generally is keeping track of indices in python, maybe partly because my first two languages were the 1-indexed Fortran and R. When I'm iterating through an array, especially with more complicated nested for loops, I very frequently get out of range errors. Is it better practice then to try to avoid to manually updating pointers? Here's is some sample code of mine where I am trying to build all subsets of a list nums.

def oob(index, arr_len):
    return index == arr_len 

nums = [1,2,3]
arr_len = len(nums)

# iterate through len of subsets
for sub_len in range(arr_len):
    sub_len += 1 

    #create list of pointers, iteratively increasing the last one
    pointers = list(range(sub_len))

    for point in range(len(pointers)):
        curr = len(pointers) - 1 - point

        #make sure not out of bounds, add solution, update curr pointer and OOB
        while not oob(pointers[curr], arr_len):
            ans.add(tuple((nums[elem] for elem in pointers)))
            pointers[curr] += 1 

            arr_len = pointers[curr]

PS, I know there's probably a cleaner solution out there for this problem, but I wanted to showcase some general code I write to help demonstrate where my shortcomings my be.

PSS: note this "solution" isn't even valid for the task at hand, it only works for a 3-array. I only figured that out after asking the question, but the answers were really good anyways

2
  • 1
    I know you do not ask for this, nevertheless the structure for i in range(len(arr)): is not pythonic. Python has some nice built-in features to avoid that structure e.g. the enumerate(): realpython.com/python-enumerate This talk by Raymond Hettinger is quite nice in showing a pythonic way as alternative to idioms in other languages: youtube.com/watch?v=OSGv2VnC0go
    – gillesB
    Feb 24 at 8:03
  • 1
    You're totally right about not using range(len(arr)), this is mostly a bad habit, but I also sometimes feels it's a little excessive to write i , _ in enumerate(arr). I should totally check out that video though, thanks! Feb 25 at 19:25

3 Answers 3

9

The answer is simple in theory: avoid to write such convoluted code.

(But of course, how to do this may take a while to learn).

When I'm iterating through an array, especially with more complicated nested for loops,

Here is your problem, and the obvious solution is: don't write complicated nested "for" loops. You can accomplish this, for example, by refactoring inner loops into functions on their own. Though your code will de facto still execute two nested loops, this often helps because

  • it introduces a clearer boundary between the scopes of the two loops
  • it forces you to make the input and output of the inner loop more explicit
  • it allows to reason about the outer and inner loop on its own
  • it allows to give the "inner" task a name of its own, making the intention clearer

Moreover, in the code above, I spotted a very risky construct which frequently leads to errors: messing around with loop index variables inside the loop. For example

for sub_len in range(arr_len):
    sub_len += 1 

Don't do this. Never!

In this example, using pointers = list(range(sub_len + 1)) at the line below instead would be sufficient. In case if you really need sub_len + 1 inside the loop body more than once, introduce a new variable for holding the value, don't try to save a few stack bytes by "reusing" the loop variable. Same holds for variables describing the loop iteration range, like that arr_len = pointers[curr] in the innermost loop, which can affect the outermost loop.

Another thing which might help to keep things under control is clear and concise naming.

PS, I know there's probably a cleaner solution out there for this problem, but I wanted to showcase some general code I write to help demonstrate where my shortcomings my be.

There is always a cleaner solution, not just in the contrived example of this question. You may have to invest some time into brainwork to find it, but this is balanced by saving a lot of debugging time.

1
  • interestingly I went back to the drawing board and solved this with a recursion. Although recursion is another beast in terms of its complexity (well in this case my non-recursive solution wasn't correct), I think you have a really good point about defining more functions. I think that's another Achilles heal of my coding. Appreciate the answer a lot! Feb 25 at 19:29
1

First, your while loop is effectively an if statement, since after arr_len = pointers[curr], pointers[curr] == arr_len will be true. It also doesn't prevent duplicate elements, which is a problem for calculating the powerset.

To look at a more Pythonic implementation, I would suggest looking to the standard library, specifically the itertools recipes. It shows the following implementation:

from itertools import combinations, chain

def powerset(iterable):
    "powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s) + 1))

This function converts its argument to a list, so you can pass any iterable to it.

It then generates, for all r where 0 <= r < len(s) + 1 all the subsequences of s with length r, and then chains them all together.

It returns an iterator, which you can convert into a list by passing it to list. The advantage of this is that if you only need a small number of all the subsets of a long list, you don't need to keep a list of length 2 ** len(s) in memory!

This approach, where you use the standard library as a collection of building blocks to build your code from, means that your code will be shorter, simpler, and less prone to bugs like the two I identified or the one Doc Brown identified.

1
  • I appreciate the solution, although maybe I should have been a bit more clear, I would usually use a library for this kind of thing, but I'm practicing for SWE interviews so I wouldn't have access to that kind of thing. Interesting point about the while loop. I think generally I'm abusing the control structure and there are better things for my purpose out there. Feb 25 at 19:33
1

There are cases where manipulating indices directly is useful for performance reasons, but this is more relevant when writing lower level code, like c# or c++. For example when doing image processing.

If this is the case, a good recommendation is to be meticulous when writing unit tests. Indexing errors might still be likely to occur, but the unit tests should catch these early and let you fix issues before the code is used anywhere. If you write such code often you will likely learn effective strategies for managing indices.

For less performance sensitive code I would refer to the other answers.

2
  • I think some of my writing is leftovers from being taught algorithms in C++ (although these days I can't code in that language). What kind of unit tests do you mean? I'm more familiar with the econometrics meaning of the phrase. Feb 25 at 19:35
  • @JoeTheShmoe unit tests are automated tests designed to test a small section of code. I.e. You would give your algorithm some sets of data and check that the result matches your expecations. Keep these tests around in case you need to do any modifications.
    – JonasH
    Feb 28 at 7:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.