Twitter Puddle
November 15, 2013
We have today an interview question from Twitter:
Consider the following picture:
In this picture we have walls of different heights. This picture is represented by an array of integers, where the value at each index is the height of the wall. The picture above is represented with an array as [2,5,1,2,3,4,7,7,6].
Now imagine it rains. How much water is going to be accumulated in puddles between walls?
We count volume in square blocks of 1X1. So in the picture above, everything to the left of index 1 spills out. Water to the right of index 7 also spills out. We are left with a puddle between 1 and 6 and the volume is 10.
Your task is to write a program to compute the volume of water in the puddle; you should strive for an algorithm that completes the task in a single pass. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
In Python. I understood “single pass” as a single scan trough the data from left to right. Then some more bookkeeping is needed, as it is not known until the last moment what the highest wall on the right will be. So, volume is calculated with the height of the wall on the left. If higher wall on the right appears, it is simple and the volume calculated so far can be added to the total volume. If never a higher wall appears, volumes have to be corrected for the lower right wall and all volume at the right of the right wall has to be subtracted again.
def twitter_puddle(seq): """scan seq from left to right there can be more that one puddle """ left = right = 0 number_in_puddle = 0 # number of contributionsin puddle number_at_top = 0 # number of contributions @ last high on the right puddle = 0 # volume in current puddle volume = 0 # volume after last high on the right xvolume = 0 # volume after last high on the right - splills off for last puddle for s in seq: if s >= right: right = s number_at_top = number_in_puddle xvolume = 0 if left > right: number_in_puddle += 1 puddle += (left - s) xvolume += (left - s) else: # puddle if full - right >= left -> next puddle volume += puddle xvolume = 0 left = right right = 0 puddle = number_in_puddle = n_at_top = 0 else: # last puddle - extra volume has to be subtracted # right is lower than left, so puddle volume has to be corrected assert left > right puddle -= number_at_top * (left - right) volume += puddle - xvolume return volume assert twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6]) == 10 assert twitter_puddle([2, 5, 1, 3, 1, 2, 1, 7, 7, 6]) == 17 assert twitter_puddle([2, 7, 2, 7, 4, 7, 1, 7, 3, 7]) == 18 assert twitter_puddle([6, 7, 7, 4, 3, 2, 1, 5, 2]) == 10 assert twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4]) == 26A C++11 version of the answer described on his blog (not feeling too
creative today myself):
#include <algorithm> #include <iostream> #include <vector> template <typename UInt> auto calculate_volume(const std::vector<UInt>& heights) -> UInt { auto lmax = UInt{0}, rmax = UInt{0}, volume = UInt{0}; auto left = size_t{0}, right = heights.size() - 1; while (left < right) { lmax = std::max(lmax, heights[left]); rmax = std::max(rmax, heights[right]); if (lmax >= rmax) { volume += rmax - heights[right]; --right; } else { volume += lmax - heights[left]; ++left; } } return volume; } auto main() -> int { auto puddles = std::vector<std::vector<uintmax_t>> {{2, 5, 1, 2, 3, 4, 7, 7, 6}, {2, 5, 1, 3, 1, 2, 1, 7, 7, 6}, {2, 7, 2, 7, 4, 7, 1, 7, 3, 7}, {6, 7, 7, 4, 3, 2, 1, 5, 2}, {2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4}}; for (auto p: puddles) { std::cout << calculate_volume(p) << std::endl; } return EXIT_SUCCESS; }Well, this python program doesn’t even pass its own tests!
Here is a Common Lisp solution that passes its own tests, and those of the python program:
;; -*- mode:lisp; coding:utf-8 -*- ;; 1| ;; 2| ___ ;; 3| |7 7|_ ;; 4| _ | 6| ;; 5| |5| _| | ;; 6| | | _|4 | ;; 7| _| | _|3 | ;; 8| |2 |_|2 | ;; 9|_|____1____________|___ ;; 10| 0 1 2 3 4 5 6 7 8 9 ;; ;; The vector of altitudes is extended with 0's to the infinites. (defun make-dvector (length &key (initial-element 0)) (cons (make-array length :adjustable t :initial-element initial-element) initial-element)) (defun (setf dref) (new-value dvector i &key (initial-element 0)) (unless (< i (length (car dvector))) (setf (car dvector) (adjust-array (car dvector) (1+ i) :initial-element initial-element))) (setf (aref (car dvector) i) new-value)) (defun dref (dvector i &key initial-element) (declare (ignore initial-element)) (if (< i (length (car dvector))) (aref (car dvector) i) (cdr dvector))) (defun dref-vector (dvector) (car dvector)) (defstruct state (altitude 0) (safe 0) (lefts (make-dvector 8 :initial-element -1))) ;; _h ;; ______| --> move left wall x,h ;; ;; _ ;; | _h ;; |____| --> XXXX are safe, move left wall x,h ;; ;; _h ;; _ | ;; ___| |____| --> XXXX are safe, move left wall x,h ;; ;; | ;; | _h ;; | _ | j ;; |___| |____| --> XXXX and XXXXXXXXXX are safe, move left wall x,j and x,h ;; _ ;; | ;; ... |_h --> current altitude := h (defun accumulate-left (state position height) (with-accessors ((altitude state-altitude) (safe state-safe) (lefts state-lefts)) state (loop :for a :from altitude :below height :do (unless (minusp (dref lefts a)) (incf safe (- position (dref lefts a))) (setf (dref lefts a) -1))) (setf altitude height))) (defun move-left (state position height) (with-accessors ((altitude state-altitude) (lefts state-lefts)) state (loop :for a :from height :below altitude :do (setf (dref lefts a) position)) (setf altitude height))) (defun process-step (state position height) (if (< (state-altitude state) height) (accumulate-left state position height) (move-left state position height))) (defun compute-retained-water (relief) (let ((state (make-state))) (loop :for position :from 0 :below (length relief) :do (process-step state position (aref relief position)) :finally (process-step state (length relief) 0)) (state-safe state))) (assert (= 10 (compute-retained-water #(2 5 1 2 3 4 7 7 6)))) (assert (= 17 (compute-retained-water #(2 5 1 3 1 2 1 7 7 6)))) (assert (= 18 (compute-retained-water #(2 7 2 7 4 7 1 7 3 7)))) (assert (= 10 (compute-retained-water #(6 7 7 4 3 2 1 5 2)))) (assert (= 26 (compute-retained-water #(2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4)))) (defparameter *little* #(2 5 1 2 3 4 7 7 6)) (defparameter *2little* #(2 2 5 5 1 1 2 2 3 3 4 4 7 7 7 7 6 6)) (defparameter *91719* #(9 1 7 1 9)) (defparameter *91717* #(9 1 7 1 7)) (defparameter *91715* #(9 1 7 1 5)) (defparameter *1917191* #(1 9 1 7 1 9 1)) (defparameter *1917171* #(1 9 1 7 1 7 1)) (defparameter *1917151* #(1 9 1 7 1 5 1)) (defparameter *71917* #(7 1 9 1 7)) (defparameter *719aba917* #(7 1 9 10 11 10 9 1 7)) (defparameter *12345654321* #(1 2 3 4 5 6 5 4 3 2 1)) (defparameter *9* #(9)) (defun twice (x) (+ x x)) (assert (= 10 (compute-retained-water *little*))) (assert (= 20 (compute-retained-water *2little*))) (assert (= 10 (compute-retained-water (reverse *little*)))) (assert (= 20 (compute-retained-water (reverse *2little*)))) (assert (= 20 (compute-retained-water (map 'vector (function twice) *little*)))) (assert (= 40 (compute-retained-water (map 'vector (function twice) *2little*)))) (assert (= 18 (compute-retained-water *91719*))) (assert (= 12 (compute-retained-water *91717*))) (assert (= 12 (compute-retained-water (reverse *91717*)))) (assert (= 10 (compute-retained-water *91715*))) (assert (= 10 (compute-retained-water (reverse *91715*)))) (assert (= 18 (compute-retained-water *1917191*))) (assert (= 12 (compute-retained-water *1917171*))) (assert (= 12 (compute-retained-water (reverse *1917171*)))) (assert (= 10 (compute-retained-water *1917151*))) (assert (= 10 (compute-retained-water (reverse *1917151*)))) (assert (= 12 (compute-retained-water *71917*))) (assert (= 12 (compute-retained-water *719aba917*))) (assert (= 0 (compute-retained-water *12345654321*))) (assert (= 0 (compute-retained-water *9*))) (let ((d (make-dvector 4 :initial-element -1))) (loop :for i :below 10 :do (assert (= -1 (dref d i)))) (loop :for i :below 7 :do (setf (dref d i) i) (assert (= i (dref d i)))) (loop :for i :from 7 :below 20 :do (assert (= -1 (dref d i)))) d)# a is a list, e.g. [2,5,1,2,3,4,7,7,6]
def f(a):
water = 0
i = 0
while i a[i+1]:
x = 0
j = 0
while j < a[i]:
x += 1
j = a[i+x]
dwater = (x-1)*a[i]
for k in range(i+1,i+x):
dwater -= a[k]
water += dwater
i += (x-1)
except:
life = 42
i += 1
return water
sorry for that formatting. how do I make it like the codes above?
In C#:
/// <summary> /// Gets the puddle volume. /// </summary> /// <param name="wall">The given wall.</param> /// <returns>The volume of the puddles formed on the wall.</returns> private static int GetPuddleVolume(int[] wall) { int volume = 0; int currentWaterLevel = 0; // Run through the wall. for (int i = 1; i < (wall.Length - 1); i++) { // Checks if the current block of the wall is smaller than the next, meaning the puddle will potentially start. if (wall[i] < wall[i - 1]) { // Gets the point where the puddle should end. int j = i; while ((j < wall.Length) && (wall[j] < wall[i - 1])) { j++; } // Set the water level to the height of the point where the puddle should end if that's the lower point, or to the point where it started if not. if ((wall.Length == j) || (wall[j] < wall[i - 1])) { currentWaterLevel = (wall.Length == j) ? wall[j - 1] : wall[j]; } else { currentWaterLevel = wall[i - 1]; } } // Adds to the volume if current wall is lower than the current water level. if ((currentWaterLevel - wall[i]) > 0) { volume += (currentWaterLevel - wall[i]); } } return volume; }I’ve also created a little routine that displays the wall in a console screen:
/// <summary> /// Displays the wall. /// </summary> /// <param name="wall">The wall.</param> private static void DisplayWall(int[] wall) { Console.Clear(); for (int i = 0; i < wall.Length; i++) { for (int currentTop = 0; currentTop < (wall[i] * 2); currentTop++) { Console.SetCursorPosition(i * 4, Console.WindowHeight - currentTop); Console.Write("|"); } for (int currentTop = 0; currentTop < (wall[i] * 2); currentTop++) { Console.SetCursorPosition(i * 4 + 4, Console.WindowHeight - currentTop); Console.Write("|"); } Console.SetCursorPosition(i * 4 + 1, Console.WindowHeight - (wall[i] * 2)); Console.Write("___"); } }Ugh, sorry, my first post was incorrect, I missed one little extra thing in the first if:
/// <summary> /// Gets the puddle volume. /// </summary> /// <param name="wall">The given wall.</param> /// <returns>The volume of the puddles formed on the wall.</returns> private static int GetPuddleVolume(int[] wall, out IList<Point> puddle) { int volume = 0; int currentWaterLevel = 0; puddle = new List<Point>(); // Run through the wall. for (int i = 1; i < (wall.Length - 1); i++) { // Checks if the current block of the wall is smaller than the next, meaning the puddle will potentially start. if ((wall[i] > currentWaterLevel) && (wall[i] < wall[i - 1])) { // Gets the point where the puddle should end. int j = i; while ((j < wall.Length) && (wall[j] < wall[i - 1])) { j++; } // Set the water level to the height of the point where the puddle should end if that's the lower point, or to the point where it started if not. if ((wall.Length == j) || (wall[j] < wall[i - 1])) { currentWaterLevel = (wall.Length == j) ? wall[j - 1] : wall[j]; } else { currentWaterLevel = wall[i - 1]; } } // Adds to the volume if current wall is lower than the current water level. if ((currentWaterLevel - wall[i]) > 0) { for (int puddleFiller = wall[i] + 1; puddleFiller <= currentWaterLevel; puddleFiller++) { puddle.Add(new Point { X = i, Y = puddleFiller }); } volume += (currentWaterLevel - wall[i]); } } return volume; }http://codepad.org/FkazvRJz
Oops. In my post above I was caught by a late edit. I forgot to rename thevariable n_at_top on line 25 into number_at_top. After changing this it works again (at least for the test cases).
A bunch of ‘correct’ solutions here, so I went the other way and made it pretty. :) Basically, I made a falling sand style particle simulation that drops water until all of the puddles are full then counts it up. Pretty far from efficient, but it looks nice.
Linky: jverkamp.com: Twitter puddle
I was trying out “pencilcode.net” (i.e. logo in the age of javascript), and wrote an animated version based on message-passing concurrency.
http://coldtortuga.pencilcode.net/home/twitterpuddle
Here’s my recursive solution in Common Lisp, which easily be TCO’d away:
(defun walk-heights (area maybe-area heights current lmax)
(cond
((>= current (length heights))
area)
((> lmax (aref heights current))
(walk-heights area (+ maybe-area (- lmax (aref heights current)))
heights (1+ current) lmax))
(t
(walk-heights maybe-area maybe-area heights (1+ current) (aref heights current)))))
(defun twitter-puddle (heights)
(walk-heights 0 0 heights 0 0))
;;; repl
CL-USER> (time (twitter-puddle #(2 5 1 2 3 4 7 7 6)))
Evaluation took:
0.000 seconds of real time
0.000004 seconds of total run time (0.000003 user, 0.000001 system)
100.00% CPU
4,376 processor cycles
0 bytes consed
10
hmm, that wasn’t formatted like I thought, how does one post code-blocks with the line numbers and everything?
and it’s not right anyway. argh sorry for the noise
I don’t know if you’re watching this, Paul, but I don’t think your solution works. The problem (I believe) will show up if the terrain looks something like 7,6,5,4,3,2,x. Your code appears to traverse the sequence strictly from left to right, holding an almost-finite amount of state. But the value of x determines how much spills in a way that depends on just how the terrain descends. This won’t work. The “official” solution gets around this by working from both ends, so it only inspects each value once but it does so out of order.
Addendum: the best way I can see to do it if you have to traverse the sequence from left to right is by using a stack to keep track of the “open” puddles. The stack will grow each time the terrain descends and shrink every time it ascends far enough to close a puddle.
Here’s a simple solution. I found that if the right most position holds the highest value on the list (highest wall), then the algorithm is really simple.
So then what I do is to divide the original list into two lists that meet the above condition and do the simple algorithm on each and add the results.
How to create the two lists?
Find the max value on the entire list, then
part1 = [ 0 .. max_value ]
part2 = reverse [ max_value .. length – 1 ]
Counting water on those two lists is equivalent to counting water in the original input list.
Here’s the code: http://pastebin.com/Fb0ZvYBK
I tested it with the following scenarios:
2 5 1 2 3 4 7 7 6 => 10
2 2 5 1 3 1 2 1 7 7 6 => 17
2 7 2 7 4 7 1 7 3 7 => 18
4 6 7 7 4 3 2 1 5 2 => 10
5 2 5 1 2 3 4 7 7 6 2 7 1 2 3 4 5 5 4 => 26
This solution (slightly) violates the rule of looping through the input list only once, but it is O(n) anyway.
Cheers!
Juan Ignacio
An additional comment just for the followup option that I forgot to check :P.
/*
There are 2 sollutions :
1. When moving from left to right, use a temp variable to store the volume accumulated in a column.
Since there is a potential overflow problem u might have to back track/store the previous values.
Back tracking would result in slightly more than one pass and storing would be complex.
Hence process the list from both the ends. Keep track of the last height point.
when both pointers meet, calculate the overflow voulme, and subract it.
2. arguably a single pass. Code is not efficent but it is much more simple.
cosider the walls to be in a x-y grid.
run a nested loop. inner loop would move from left to right ie in x-direction. outer loop would be for the next level ie y-direction.
when an empty cell is encountered after a wall, start adding to temp. if a wall is encountered , add temp to total volume.
The doubleLoop function prints out the sollution this way.
*/
package problems;
public class TwitterPuddle {
private static Integer[] input = new Integer[] {0,1,2,3,2,1,0,1,2,3,2,1,0};
//{0,1,2,3,2,1,0,1,2,3,2,1,0}
//{2, 5, 1, 2, 3, 4, 7, 7, 6, 2, 7, 1, 2, 3, 4, 5, 5, 4};
//{0,1,0,1,0,3,2,1,0,1,1,0,2,0,5,0,2,3}
public static void run() {
Integer totalVoulume = 0;
boolean leftFound = false, rightFound =false, done = false;
int tempVolumeL = 0,tempVolumeR=0, leftHeight=0, rightHeight=0, leftIndex =0, rightIndex = 0;
if ( input[0] > 0 ) {
leftFound = true;
leftHeight= input[0];
leftIndex = 0;
}
if ( input[input.length-1] >0) {
rightFound = true;
rightHeight = input[input.length-1];
rightIndex = input.length-1;
}
for ( int j=0,k= input.length -1; j rightHeight ) {
totalVoulume = totalVoulume + tempVolumeR + tempVolumeL –
( (leftHeight-rightHeight) * (j- leftIndex) );
}
else if ( leftHeight < rightHeight ) {
totalVoulume = totalVoulume + tempVolumeL + tempVolumeR –
( (rightHeight – leftHeight) * (rightIndex-k) );
}
else {
totalVoulume = totalVoulume + tempVolumeR + tempVolumeL;
}
break;
}
if ( j<k)
{
j++;
if( leftFound == true && input[j] =leftHeight) {
totalVoulume = totalVoulume + tempVolumeL;
leftHeight = input[j];
tempVolumeL = 0;
leftIndex = j;
}
else if ( leftFound == false && input[j] > 0 ) {
leftFound = true;
leftHeight= input[j];
leftIndex = j;
}
if ( k-j == 1) { done = true; continue;}
}
{
k–;
if( rightFound == true && input[k] =rightHeight) {
totalVoulume = totalVoulume + tempVolumeR;
rightHeight = input[k];
tempVolumeR = 0;
rightIndex = k;
}
else if ( rightFound == false && input[k] > 0 ) {
rightFound = true;
rightHeight= input[k];
rightIndex = k;
}
if ( k-j == 1) done = true;
}
}
System.out.println(” total volume=”+ totalVoulume);
doubleLoop();
}
private static void doubleLoop() {
Integer totalVoulume = 0;
for ( int i = 1;; i++){
boolean leftFound = false, rightFound= false; int tempVolume = 0;
if ( input[0] >= i ) {
leftFound = true;
}
for ( int j=1 ; j< input.length; j++) {
if( leftFound == true && input[j] =i) {
totalVoulume = totalVoulume + tempVolume;
rightFound = true;
tempVolume = 0;
}
else if ( leftFound == false && input[j] >=i) {
leftFound = true;
}
}
if ( leftFound == false || rightFound == false)
break;
}
System.out.println(” double loop –total volume=”+ totalVoulume);
}
}
Ruby version I bashed out the day after getting this question, unfortunately I’m a sysadmin really so I floundered around a bit in the interview. No promise that this is right, it spits out an array of the depths so some for the volume…
#!/usr/bin/ruby
print “Enter terrain heights (space separated): ”
terrain = gets.chomp.split(” “).map { |s| s.to_i }
rainDepth = Array.new(terrain.length)
lInd=0
lMaxInd=0
rInd=terrain.length-1
rMaxInd=terrain.length-1
i=0
while i < terrain.length do
if terrain[lInd] terrain[lMaxInd] then lMaxInd = lInd end
rainDepth[lInd] = terrain[lMaxInd] – terrain[lInd]
lInd+=1
else
if terrain[rInd] > terrain[rMaxInd] then rMaxInd = rInd end
rainDepth[rInd] = terrain[rMaxInd] – terrain[rInd]
rInd-=1
end
i+=1
end
puts “#{rainDepth}”
This works and is short?
“`
def twitter_puddle(wall):
height = max(wall)
total = 0
for x in range(1, len(wall)-2):
lowest_wall = min(max(wall[:x]), max(wall[x+1:]))
if lowest_wall > wall[x]:
total += lowest_wall – wall[x]
return total
assert(twitter_puddle([2, 5, 1, 2, 3, 4, 7, 7, 6]) == 10)
“`
Here is Python code that completes the task in a single pass. I consider calling max() an additional pass of the list. https://wiki.python.org/moin/TimeComplexity
def twitter_puddle(t): state = {} volume = 0 left_bank = last = t[0] for cur in t[1:]: if cur > last: # height went up if cur > left_bank: # height of current left bank went up left_bank = cur # save any amount now trapped # only need to save/reset between last and cur (not 0 and cur) -- reduces dictionary size for x in range(last,cur): # use .get for default of 0 if entry does not exist volume += state.get(x, 0) state[x] = 0 if cur < left_bank: # increment area held by left bank but not saved for x in range(cur,left_bank): state[x] = state.get(x, 0) + 1 last = cur return volumeJS version to handle arbitrarily large streams (would need to change volume data type at some point, and the walls in the accumulator could get large for a long sequence of descending steps).
function processWall(value, accumulator) {
var volume = accumulator.volume,
walls = [],
wallIndex = 0,
wall, lastWall;
while(wallIndex value) {
walls.push([wall[0], wall[1]+1]);
} else if(wall[0] < value && lastWall) {
volume += lastWall[1] * (Math.min(value, lastWall[0]) - wall[0]);
}
lastWall = wall;
++wallIndex;
}
walls.push([value, 0]);
return {volume: volume, walls: walls}
}
function calculateVolume(puddle) {
var accumulator = { volume: 0, walls: [] };
for(var i = 0; i < puddle.length; ++i) {
accumulator = processWall(puddle[i], accumulator);
}
return accumulator.volume;
}
My solution goes from right to left and always assumes that there’s a big maximum and many local maximums, until there’s a new big maximum.
Let’s say the big maximum is 7, then we create 2 new arrays. One to keep track of how many steps were taken being less than 7,6,5,4,3,2,1. Another array keeps track of the volume less than 7, 6,5,4,3,2,1. If there’s a new local maximum, say 5. We calculate the volume as steps[5]*newmax – accumvol[5]. If there’s a new maximum, say 10. We ignore the local sums, and take the volume between big maxs (between 7 and 10).
Code in java, working and with some tests:
http://pastebin.com/5EF06zGc
i have a solution made with netbeans and javafx you can watch the demo on youtube :
http://speedysoft.blogspot.com/2015/06/puddles-with-javafx-programmingpraxis.html
in golang:
package main
import “fmt”
func calc(values []int) int {
var (
left = 0
right = len(values) – 1
lmax = values[0]
rmax = values[right]
volume = 0
)
for right > left {
if lmax = lmax {
lmax = values[left]
} else {
volume += lmax – values[left]
}
} else {
right–
if values[right] >= rmax {
rmax = values[right]
} else {
volume += rmax – values[right]
}
}
}
return volume
}
func main() {
testcase1 := []int{2, 5, 1, 2, 3, 4, 7, 7, 6}
testcase2 := []int{2, 5, 1, 3, 1, 2, 1, 7, 7, 6}
testcase3 := []int{6, 1, 4, 6, 7, 5, 1, 6, 4}
fmt.Printf(“%v %v\n”, testcase1, calc(testcase1))
fmt.Printf(“%v %v\n”, testcase2, calc(testcase2))
fmt.Printf(“%v %v\n”, testcase3, calc(testcase3))
}