Complex is Better than Complicated

January 31, 2012

Some employers I’ve dealt with recently like to give their prospective software engineers a coding test to complete prior to the in-person interview. I’m undecided as to whether this is a good way of screening potential hires, but I do like the additional time it gives to think about the problem. Unfortunately it also allows candidates to Google for their solutions instead of coming up with their own. In order to do my part to help I’ve decided to post my answers to any such tests I complete here. Maybe if I collect enough of them I’ll get the priviledge of skipping that part of the process next time around.

This first one really puzzled me for a while and made me question the basic foundations of my Python knowledge, but it turns out that the solution is quite reasonable. I was given the following piece of code, which should print out a multiplication table, and told to fix the bug that was causing it to malfunction. See if you can spot it:

table = [[0]*10]*10
for i in range(1,11):
    for j in range(1, 11):
        table[i-1][j-1] = i*j

for i in range(10):
    for j in range(10):
        print table[i][j],
    print

Now because I’m not Dutch (see import this), I was pulling my hair out for a while. I even resorted to verifying that Python was parsing the code in the way I expected. This task is made surprisingly easy by the ast module. I eventually did come to my senses though after looking a little more closely.

In Python, mutable objects like lists are never copied unless you specifically ask for copying. The first line above looks like it’s making a list of ten sublists, each containing ten zeroes. In reality though, it makes a list of ten references to the same one sublist with the ten zeroes. Note that this issue doesen’t affect the actual zero values themselves as they are immutable. To demonstrate:

>>> table[0] is table[1]
True
>>> from itertools import combinations
>>> all(r1 is r2 for (r1, r2) in combinations(table, 2))
True

So all of our rows are actually stored in the same list. Because of this, whenever we update a value in any row of our table it effectively updates all of the rows, putting that value in the same position. There is really only one row, it just happens to be accessible in ten different places. That’s why we end up with all of the rows having the values we’d expect to be in the last row.

Here’s a better way to print out the multiplication table, by simply printing the values instead of storing them and reading them back. It also uses xrange() instead of range() to save some memory and aligns all of the columns with string formatting.

for i in xrange(1, 11):
    for j in xrange(1, 11):
        print "%3d" % (i * j),
    print

Stay tuned for more coding solutions and Python trivia!