twitterinterview.py

walls = [2,3,4,0,1,3,1,5,4,3,4,0,1,2,0,1,0,2,0,4]
lmax=0;
total=0;
copen=0;
buff=0;
print "\n-----------BEGIN ALG-----------\n"
if walls[0]>walls[1]:
    lmax=walls[0];
    copen=1;
for i in range(1, len(walls)):
    if walls[i]<walls[i-1]:
        copen=1;
        buff=buff+(lmax-walls[i]);
    else:
        if walls[i]<lmax:
            buff=buff+(lmax-walls[i]);
            buff=buff-(copen*(walls[i]-walls[i-1]));
            total=total+(copen*(walls[i]-walls[i-1]));
            copen=copen+1;
        else:
            total=total+buff;
            buff=0;
            copen=1;
            lmax=walls[i];
        
    print "step "+str(i)+": total = " +str(total) + " buff = " +str(buff);
print "\nTOTAL = "+str(total);
print "\n-----------END ALG-----------\n"

Hey!

I've tested it and it's very fast!

but sometimes it miscalculates.
I tested with this array, and came to 50191 with your solution and 50242 with mine.

The benchmark between our two solutions is interesting as well. For an array with length 10000:

Mine runs 0.017299 seconds and yours 0.003123 seconds.

I also get differences for simple cases like:
[landscape] my result / yours
[5, 9, 5, 0, 5, 2, 9, 3, 6, 8, 0, 5, 7, 6, 0, 10, 8, 5, 9, 0] 66 / 65
[2, 9, 9, 5, 10, 9, 3, 1, 10, 7, 8, 9, 9, 4, 7, 10, 1, 4, 1, 9] 58 / 48
[0, 8, 6, 1, 7, 8, 2, 0, 0, 8, 5, 4, 1, 3, 0, 0, 3, 3, 3, 4] 47 / 45
[1, 1, 9, 6, 2, 7, 7, 4, 2, 6, 6, 8, 6, 4, 2, 4, 8, 4, 2, 7] 48 / 30
[10, 7, 5, 9, 10, 7, 9, 5, 2, 6, 0, 5, 0, 1, 6, 6, 2, 0, 9, 1] 77 / 40
[39, 11, 34, 8, 27, 23, 2, 31, 6, 34, 31, 16, 18, 13, 10, 26, 13, 4, 26, 38] 351 / 163

I'm not sure your algorithm is correct.

hth
Florian

walls = [2,5,1,2,3,4,7,7,6] → 10
walls = [6,7,7,4,3,2,1,5,2] → 4

Another broken algorithm that depends on order.