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

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))