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;
	}
}

fun problem! i took a stab at it also: https://gist.github.com/igor47/7228586

will this work for the following case [2,7,2,7,4,7,1,7,3,7]

@sathya-me : It does handle it properly. The left and the right pointers rise to 7 and then fill in all the gaps until they meet.

I tried my own hand at this problem and came up with a slightly more naive (but clearer) solution : https://gist.github.com/Joist/7229807

edit: I put my own attempt at the single pass method in my code with comments to make it a bit clearer.

I wrote up a solution using JS, here: https://gist.github.com/msimpson/eb0189dd687d696ab70a

Mine is based on the point-inside-polygon methodology. It is more complex than what is above, and generates a maximum height at the start. However, it would continue to work with only slight modification on a two, or possibly three, dimensional matrix -- even with gaps inside columns that create enclosed areas.

Quick PHP version: https://gist.github.com/orukusaki/bb189d9f69ad09e2cd5a

Looked for the solutions and rewritten them to the ruby: https://gist.github.com/dmitry/287bd6cad9abc70436f4

Another single pass solution, https://gist.github.com/shaobohou/7231961

Did up a small Python solution passing both test cases: https://gist.github.com/Shruubi/7232152

JS implementation. 2n complexity https://gist.github.com/Zibx/7235776

Java, n complexity, single straight pass from left to right : https://gist.github.com/anonymous/7236132

Slightly simpler, slightly faster, and handles negative heights: http://jsbin.com/iquQOSo/1/edit

function maxWater(heights) {
  var left = 0,
      right = heights.length - 1,
      leftMax = heights[left],
      rightMax = heights[right],
      volume = 0;

  while (left < right) {
    if (leftMax < rightMax) {
      var height = heights[++left];
      leftMax = Math.max(leftMax, height);
      volume += leftMax - height;
    } else {
      var height = heights[--right];
      rightMax = Math.max(rightMax, height);
      volume += rightMax - height;
    }  
  }
  return volume;
}

Did a quick Haskell solution: https://gist.github.com/olajep/7236551

rainSolver = solve 0

solve acc [] = acc
solve acc (x:xs)
  | xs' == [] = solve acc xs -- no right border -> this x cannot be left border
  | otherwise = solve (acc+area) xs'
  where
    height      = minimum [x, maximum xs]
    (elems,xs') = span (<height) xs
    area        = (length elems * height) - (sum elems)

JS one cycle implementation. https://gist.github.com/Zibx/7235776/726b210cf6b6c646a925c911bb00a5ab68200810

Short Java
http://it.laplit.com/index.php/humanoid-blog/128-article-7
https://gist.github.com/AndroidHumanoid/7241202

public static int mycalculateVolume(int[] land) {
int leftMax = 0;
int subvolume = 0;
int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + subvolume;
            subvolume = 0;
        }
        else {
            subvolume = subvolume + leftMax - land[index];
        }
    }
    return volume;
}

me too, i used just one iteration https://gist.github.com/hwmrocker/7241002

O(n) recursive one-liners (Haskell, Clojure, Scala)

Solution in julia, just did a simple linear walkthrough https://gist.github.com/Niessy/7243069

Single Iteration Streaming Java solution. Not that memory friendly though.
https://gist.github.com/amuraco/7244151

pretty simple single pass python solution: https://gist.github.com/jdanielmyers/7245316

My take: https://gist.github.com/leikind/7247086

Maybe not the most efficient, but it's only 10 lines of code of functional style Ruby

My take in Clojure: https://gist.github.com/abo-abo/7247459 .
Not the best efficiency, but very straightforward.

here is my Python solution:
https://gist.github.com/flowolf/7247585

There is my awful but satisfactory solution with all answers generation for predifined count of walls and max wall height (in my case 8 * 8): https://github.com/KvanTTT/Twitter-Puddles-Counter

But it's not ideal. Number of answers can be reduced to 4 times due to symmetry along x and y axis. I mean
V(x_1, x_2, ..., x_n) = V(x_n, x_n-1, ..., x_1) and V(x_1, x_2, ..., x_n) = n*h - V(h - x_1, h - x_2, ..., h - x_n). Possible there are another dependencies from input heights which are not so clear.

Hello guys, let me show my decision ))
function calc(input){
if (input.length < 3) return 0;
var v = 0,
sort = input.slice(0).sort(function(x,y){return y-x}),
a = input.indexOf(sort[0]),
b = input.indexOf(sort[1], (sort[0]==sort[1]) ? a+1 : 0),
last, first = ( a > b ) ? (last=a,b) : (last=b,a);
for (var j = first+1; j < last; j++ ) v+=sort[1]-input[j];
return v + calc(input.filter(function(z,y){return (y < first-1) || (y >= last) }))
}

PHP solution:

public function findVolume($arr) {
$v = 0;
$l = 0;
$r = count($arr) - 1;

while ($l < count($arr) && $arr[$l + 1] >= $arr[$l]) {
    $l++;
}

while ($r > 0 && $arr[$r - 1] >= $arr[$r]) {
    $r--;
}

$pointer = $l;

while (++$pointer < $r) {
    $v += $arr[$l] - $arr[$pointer];
} 

$return $v;

}

The Groovy version:

https://gist.github.com/fergara/7250590#file-calculaterainvolume-groovy

@AndroidHumanoid
I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11.

I did a python implementation based on a simple observation. For a square to be filled with water, it has to fulfill these two conditions:

1. It has to be a free-space square (as opposed to a solid block) to begin with.
2. There has to be a solid block at the same height on either side of it (not necessarily adjacently)

https://gist.github.com/oralokan/107958531b3e33062bc5

Here's my solution in ruby that prints the board: https://gist.github.com/ubermajestix/7253875

Here's mine which solves it in one pass. https://gist.github.com/DrewFitz/7254644

It moves through the array keeping a list of unresolved "left walls" and resolves the guaranteed water blocks when hitting a right wall. Each time it resolves, it only adds the new blocks gained by "raising" the puddle's water level.

I have solution - https://gist.github.com/Ruszrok/3adc23baa83b97de7145
It works in many cases. Can break it anyone?

my Python solution - https://gist.github.com/HollyGurza/7261085 please test this

Here is a test case, please try it
6, 1, 4, 6, 7, 5, 1, 6, 4

and here is my solution, double loop, much slower
https://gist.github.com/benjaminliu/7261468

my lua solution: https://gist.github.com/jianchenglee/7262518

I have created a python solution that makes random landscapes like this one:

                           #                                                    
                          ###                                                   
               #~~~~~~~~######~~~~~~~#                                          
   #~~~~~~~~~~~###~~~~~~#######~~~~~##~#~~~~~~~##~~~~~~~~~~~~~~~~~~#            
   #~~~~~~~~~~####~~~~##########~~~~#####~~##~~##~~~~~~~~~~#~~~~~~##            
#~###~~~~~~~#######~~~##########~~~###############~~~~~~~~~#~~~~#####~#~##      
#~###~~~############~#############~###############~~~~~~~~####~~###########     
######~#############~##############################~#~#~~~#################     
######~#################################################~###################    
########################################################~###################~~##

Decker108 "I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11."

Yeees, what about that (it seems work, but how):

https://gist.github.com/AndroidHumanoid/7241202
http://it.laplit.com/index.php/ct-menu-item-8/128-article-7

public static int mycalculateVolume(int[] land) {
    int leftMax = 0;
    int rightMax = 0;
    int volumeLeft = 0;
    int volumeRight = 0;

    int volume = 0;

    for (int index = 0; index < land.length; index++) {
        if (land[index] >= leftMax){
            leftMax = land[index];  
            volume = volume + volumeLeft;
            volumeLeft = 0;
        } 
        else {
            volumeLeft = volumeLeft + leftMax - land[index];
        }
        if (land[land.length - 1 - index] >= rightMax){
            rightMax = land[land.length - 1 - index];  
            volume = volume + volumeRight;
            volumeRight = 0;
        }
        else {
            volumeRight = volumeRight + rightMax - land[land.length - 1 - index]; 
        }
    }
    return volume;
}

my version of the solution with 22 test models: https://github.com/BorzdeG/info.alenkov.demo.puddle_rain

Probably the most elegant solution to this problem is using scanl/r and zipWith. Corresponds very closely to the mathematical breakdown of this problem. Here's a solution in Haskell.

water hs
  = sum $ zipWith (flip (-)) hs 
        $ zipWith min (scanl1 max hs) (scanr1 max hs)

Mot solutions are actually wrong...

Hi all,

Another solution in Python using numpy (and matplotlib):

https://gist.github.com/yannick1974/7334581

Yannick

So does this work for:

4,0,0,4,0,4,0,0,4,2

?

Yet another solution: https://gist.github.com/syfou/7364514

It uses recursion: I tried to go for a readable and a painless, quickly implemented solution rather than something more clever.

my dumb but working version

def get_volumn(seq):
    total = 0
    for level in xrange(max(seq)-1, 0, -1):
        row = [ 1 if row-level > 0 else 0 for row in seq]
        first = row.index(1)
        last = len(row) - row[::-1].index(1) - 1
        if last - first > 0:
            total += row[first:last].count(0)
    return total

if '__main__' == __name__:
    s1 =  [2,5,1,2,3,4,7,7,6]
    print get_volumn(s1)
    s2 = [ 2, 5, 1, 3, 1, 2, 1, 7, 7, 6]
    print get_volumn(s2)

mkozakov's solution is quite perfect, no allocations, no stack uage.

single pass, recursive in python: https://gist.github.com/thulka/7429806

btw, est, your solution wrong: [7,0,5,0,7,0] should be 16, yours returns 14. also you might have hidden loops in the list selectors, so not perfectly single pass. finally, it was about an elegant solution, not just a dumb working one. a simple working one, non single pass would be:

for each bin the water = min(leftmax, rightmax) - current height

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