Twitter Interview Solution

gistfile1.java

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		int[] myIntArray = {2, 5, 1, 2, 3, 4, 7, 7, 6}; 
		System.out.println(calculateVolume(myIntArray));
	}
	
	public static int calculateVolume(int[] land) {
		
		int leftMax = 0;
		int rightMax = 0;
		int left = 0;
		int right = land.length - 1;
		int volume = 0;
		
		while(left < right) {
			if(land[left] > leftMax) {
				leftMax = land[left];
			}
			if(land[right] > rightMax) {
				rightMax = land[right];
			}
			if(leftMax >= rightMax) {
				volume += rightMax - land[right];
				right--;
			} else {
				volume += leftMax - land[left];
				left++;
			}
		}
		return volume;
	}
}

My first thought was to use a spreadsheet. Here's that in Haskell:

import Control.Lens
import qualified Data.Vector as V
import Data.Vector ((!),Vector)

-- | Calculate the water volume.
water :: Vector Int -> Int
water = V.sum . V.map (view _3) . loeb . V.imap cell where
  cell i x xs
    | i == 0               = edge _1
    | i == V.length xs - 1 = edge _2
    | otherwise            = col i x xs
    where edge ln = set l (view l (col i x xs)) (x,x,0)
            where l = cloneLens ln
  col i x xs = (l,r,min l r - x)
    where l = neighbor _1 (+)
          r = neighbor _2 (-)
          neighbor l o = max x (view l (xs ! (i `o` 1)))

It makes a vector where the value of each cell is calculated based on the two neighboring cells. Except edges, who only have one neighbor. It's a direct way of writing how I thought of the problem statement:

• I'm a cell. My puddle's extent is determined by finding the largest cell to the left of me, and the largest to the right of me.
• My potential volume is calculated by taking the minimum height of said two cells.
• My actual volume is calculated by subtracting from that my height.
• If I'm on the edge (either side), then my height on one side is restricted to me, and my volume is zero.

Done.

Oh, the loeb function is from here:

-- | Map over a structure, passing in itself.
loeb :: Functor f => f (f b -> b) -> f b
loeb x = fmap (\f -> f (loeb x)) x

Short, single-pass python solution

q = [2,5,1,3,1,2,1,7,7,6]
def solve(heights):
    water = [0]*len(heights)
    total = 0
    runoff = 0
    for i,height in enumerate(heights):
        if i == 0:
            continue
        above = max(height, heights[i-1] + water[i-1]) - height 
        water[i] = above
        if water[i] == 0:
            runoff = 0
        else:
            runoff += water[i]
    return sum(water)-runoff
print q, solve(q)

@neuronsguy That's an incomplete solution, it only works in one direction. E.g. solve([6,7,7,4,3,2,1,5,2]) → 0

@DrewFitz Only works properly in one direction.

print puddle([2,5,1,2,3,4,7,7,6]) → 10
print puddle([6,7,7,4,3,2,1,5,2]) → 11

@HollyGurza Only works properly in one direction.

You guys really need to think about the problem in both directions.

@igor47 Only works in one direction.

Thanks for the fun problem :-)

I ended up solving it recursively, working from the base cases up to a general solution, and then I converted the recursive algorithm into the following Python function taking a height array A. For a problem of size len(A) = N, the function requires O(N) time and O(1) space. For a full derivation of the algorithm, starting from first principles, see the (extensive) discussion in the source code:

https://github.com/tmoertel/practice/blob/master/water-holding-capacity/water_holding_capacity.py

def water_holding_capacity_iterative(A):
    (i, j) = (0, len(A) - 1)
    lm = rm = vol = 0
    # while segments remain, consume left- or right-end segment
    while i <= j:
        if lm < rm:
            vol += max(0, lm - A[i])
            lm = max(lm, A[i])
            i += 1
        else:
            vol += max(0, rm - A[j])
            rm = max(rm, A[j])
            j -= 1
    return vol

python:

numbers = [6,7,7,4,3,2,1,5,2]
def vol(numbers):
  prev_max = 0
  total = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total_1 = total
  total = 0
  numbers = numbers[::-1]
  prev_max = 0
  for n in numbers[0:-1]:
    if n > prev_max:
      prev_max = n
    else:
      total = total + (prev_max-n)
  total = min(total_1,total)
  return total

or one-way loop in python

def vol2(numbers):
  prev_max_left = 0
  prev_max_right = 0
  total_left = 0
  total_right = 0
  for n in xrange(0,len(numbers)-1):
    if numbers[n] > prev_max_left:
      prev_max_left = numbers[n]
    elif numbers[n] < prev_max_left:
      total_left = total_left + (prev_max_left - numbers[n])
    if numbers[-1-n] > prev_max_right:
      prev_max_right = numbers[-1-n]
    elif numbers[-1-n] < prev_max_right:
      total_right = total_right + (prev_max_right - numbers[-1-n])
  return min(total_left,total_right)

Another Haskell solution, O(1) space when switched to foldl' and strict tuples:

water is = w1 + w2 + t1 - length is * m1 where
   (t1,m1,w1) = foldl f (0,0,0) is
   (t2,m2,w2) = foldl f (0,0,0) $ reverse is
   f (t,m,w) i = (t+i, max m i, w + max 0 (m-i))

Elegant one liners are cool! Sadly mine is not one of those.

I start by calculating what the maximum amount of water that could be held is. Then, I go level by level and remove blocks that would have fallen off. Think of it as if you dipped a lego structure into a bathtub and pulled it out: every hole is filled at first, but as you pull it out of the water, each level loses some water.

https://gist.github.com/andrewnguyen42/7745194

rightMax should be equals land.length - 1

Short JS solution:
https://gist.github.com/allumbra/8035125
1 pass. Keeps track of last time wall height was seen.

Another Python solution - https://gist.github.com/joneschris/8049901

Here is a solution using C# and one lambda

using System;
using System.Linq;

namespace TwitterInterviewAnswer
{
    class Program
    {
        static void Main(string[] args)
        {
            //the data
            int[] wallHeights = {2, 5, 1, 2, 3, 4, 7, 7, 6};

            //the lambda expression
            Func<int[], int> volume = walls => walls.Skip(1).Take(walls.Count() - 2)
                .Select((s, i) => new {s, i})
                .Select(v => new[] 
                 {
                     walls.Take(v.i + 1)
                        .Max(), 
                     walls
                        .Skip(v.i + 2)
                        .Max()
                  }
                 .Min() - v.s)
                 .Where(w => w > 0)
                 .Sum();

            //the output
            Console.WriteLine("The volume is: {0}", volume.Invoke(wallHeights));
            Console.ReadKey();
        }
    }
}

@jbojcic your code won't work for something like [7,3,2,4].
You will fill in water that should spill out

@mkozakov it won't fill up water that should spill out but it will spill out everything, which is also wrong

# Actually the original implementation is as following which is done in n-pass:

def water_vol_orig(a):    
    lv = rv = -1
    result = lmax = rmax = l = 0
    r = len(a)-1 # no pass on array    
    while (l < r):
        lv = a[l]
        if lv > lmax:
            lmax = lv

        rv = a[r]
        if rv > rmax:
            rmax = rv

        if lmax >= rmax:
            result += rmax - rv
            r -= 1
        else:
            result += lmax - lv
            l += 1
    return result

# This implementation avoids the lookup for the max item in the array to finish in n-pass. 
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java 
# indexed access to an array is expensive, using enumerators is far more effective. 

# So more efficient way of doing this in Python may be:
#1) find the max item
#2) approach to max item from left and right.

def water_vol_fast(a):

    def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
        max_idx = max_val = 0
        for i, v in enumerate(a):
            if v > max_val:
                max_val = v
                max_idx = i
        return max_idx

    def _volp(x): 
        max = result = 0        
        for e in x:
            if e > max:
                max = e
            else:
                result += max - e
        return result

    imax = _imax(a) # n-pass
    return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass

# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index 
# based access to any array.

# If these are profiled, one can see the difference:

# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.

# You can test above by:

# for test:
import random 
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a)

Hm... tried to run original solution against the data with 3 maximums and it didn't work...

public class TestTest {
    public static void main (String[] args) throws java.lang.Exception
    {
        int[] testData1 = {1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult1 = 17;
        int[] testData2 = {4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult2 = 40;
        int[] testData3 = {1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult3 = 40;
        int[] testData4 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0};
        int expectedResult4 = 41;
        int[] testData5 = {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};
        int expectedResult5 = 61;

        test(expectedResult1, testData1);
        test(expectedResult2, testData2);
        test(expectedResult3, testData3);
        test(expectedResult4, testData4);
        test(expectedResult5, testData5);   //[ERROR] Test failure! Expected: 61 but was: 62

    }

    public static void test(int expected, int[] array){
        int result = calculateVolume(array);
        if(result != expected) {
            System.out.println("[ERROR] Test failure! Expected: " + expected + " but was: " + result);
        } else {
            System.out.println("[INFO] Test successful!");
        }
    }

    public static int calculateVolume(int[] land) {

        int leftMax = 0;
        int rightMax = 0;
        int left = 0;
        int right = land.length - 1;
        int volume = 0;

        while(left < right) {
            if(land[left] > leftMax) {
                leftMax = land[left];
            }
            if(land[right] > rightMax) {
                rightMax = land[right];
            }
            if(leftMax >= rightMax) {
                volume += rightMax - land[right];
                right--;
            } else {
                volume += leftMax - land[left];
                left++;
            }
        }
        return volume;
    }
}

@Mak-Sym Original implementation returns 51 and your expectation should not be 61. 51 is the correct volume for input set: {2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3}.

Please do not forget the fact that water will spill from left/right if there is no surrounding block.

Thanks!

There is typo in my post - sorry about that
I meant this one:

int[] testData5 = {2, 1, 3, 5, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3};  //should be 61, but was 62

Whoops - found bug in my calculations - it should be 62 (not sure how I missed this during numerous manual verifications and my v1 impl :) )

unspoiled solution; I think mine works the same way as yours.
https://gist.github.com/Pranz/45eff77d201ef1e2dc61

This seems to work ...
https://gist.github.com/bourneagain/0cb90851106756746933

here is an alternate but simple nlog(n) solution
https://gist.github.com/isaiah-perumalla/105b72e6b99f69b599ec

just an F# solution for aestetic pleasure

let oneWayCapacity a =
    let mutable max = 0
    a |> List.map (fun e -> if e > max then max <- e; 0 else max - e)

let totalCapacity a =
    let aL = a |> oneWayCapacity
    let aR = a |> List.rev |> oneWayCapacity |> List.rev
    List.map2 min aL aR |> List.sum


let test a =
    a |> totalCapacity |>
    printfn "totalCapacity %A = %i" a

let () = 
    [1; 2; 1; 3; 5; 3; 1; 2; 4; 1] |> test
    [2; 5; 10; 7; 3; 8; 5; 2] |> test
    [2; 5; 1; 2; 3; 4; 7; 7; 6] |> test

https://gist.github.com/harry-tallbelt/cc236e710c9edf858853c118bc38c9ad

one-pass solution in js

const assert = require('assert')

// original walls, expect 17
const walls1 = [  2, 5, 1, 3, 1, 2, 1, 7, 7, 6 ]

// case when some water spills over the right edge, expect 12
const walls2 = [  2, 5, 1, 3, 1, 2, 1, 4, 4, 3 ]

// should be 51
const walls3 = [ 2, 1, 3, 4, 1, 2, 1, 3, 2, 1, 0, 2, 4, 3, 1, 5, 3, 1, 4, 1, 2, 1, 0, 5, 2, 1, 3 ]

function volume(walls) {

	let level = 0
	let acc = 0
	let result = 0
	let prev = 0
	let level_pos = -1

	for(let i = 0; i < walls.length; i++) { 
		if ( walls[i] >= level ) {
			//  new high-water level mark, flush accumulated volume into final result
			level = walls[i]
			level_pos = i
			result = result + acc
			acc = 0
		}

		if ( walls[i] < level ) {
                         // water accumulation
			let delta = level - walls[i]
			acc = acc + delta		

			if ( walls[i] > prev ) {
			      // this a local extremum
                              let above = (level - walls[i]) * (i - level_pos)
			      let pond = acc - above
			      result = result + pond
			      acc = above
                                // get water pond by local extremum and add to final result, 
                                // accumulated volume is now the water above the extremum
			}
		}

		prev = walls[i]
	}

	return result	
}


assert(volume(walls1), 17)
console.log(volume(walls1))

assert(volume(walls2), 12)
console.log(volume(walls2))

assert(volume(walls3), 51)
console.log(volume(walls3))