Water accumulated between towers

Question

I came across this interview question to find water accumulated between towers:

You are given an input array whose each element represents the height of the tower. The width of every tower is 1. You pour water from the top. How much water is collected between the towers?

Any suggestions?

def test(x):
    if len(x) <= 2 or x == sorted(x) or x == sorted(x, reverse=True):
        return 0

    area = 0
    count = 1
    max_height = x[0]

    while count < len(x) - 1:
        if x[count] < max_height and x[count:] != sorted(x[count:], reverse=True):
            temp_count = 0
            new_count = count
            temp_height = 0
            height = max_height
            while count < len(x):
                if x[count] >= height or count == len(x) - 1:
                    temp_count = count
                    temp_height = x[count]
                    height = min(max_height, temp_height)
                    break
                count += 1
            while new_count < temp_count:
                area += height - x[new_count]
                new_count += 1
        else:
            max_height = x[count]
            count += 1

    return area

try:
    a = [1,2,3,4,5]
    print a, test(a)

    b = [5,4,3,9,1]
    print b, test(b)

    c = [3,2,1,1,1,2,3]
    print c, test(c)

    e = [1,2,0,2,1]
    print e, test(e)

    f = [1, 4, 2, 5, 1, 2, 3]
    print f, test(f)

    g = [3, 2, 1, 1, 1, 2, 3]
    print g, test(g)

    a1 = [1001,1000,1002]
    print a1, test(a1)
except Exception as e:
    print e

Answer 1

Three quick comments:

• There’s no documentation anywhere in your code. Ideally there should be a docstring, and some comments explaining why the code is behaving in a particular way. I wasn’t able to work out your approach to the problem because there are no comments, and I didn’t want to sit down and reverse engineer it.

  Note that variable names are also a form of documentation, and some of yours could be better – x is a poor name, and so is count. What’s it counting?

• Your tests aren’t very useful, because I have to work out if they're correct by hand. If I start editing the code, and I introduce a bug, there’s a possibility I won’t notice the test changes. Your tests should warn me if there’s been a regression, not simply print out some results. The most basic form of this is something like.

  assert test(a) == 0
  assert test(b) == 3
  assert test(c) == 8
  

  Now I can read your tests and find out what the results should be, and I can be warned if I introduce a bug.

  The better way to do tests is with the unittest module. If you haven’t used that before, I recommend Ned Batchelder’s talk Getting started with testing, which is a good introduction to Python testing in general.

• I don’t know why you have the try…except block. You should really only use try…except if you expect an exception to be raised, so that you can wrap it accordingly. Unexpected exceptions tell you something about your program – there’s a problem – and you shouldn’t be ignoring that information.

  And you should try to avoid broad except: statements. Better to catch only the specific exceptions you think might be raised (in this case, there aren’t any), and let anything else bubble to the top.