Skip to content

Instantly share code, notes, and snippets.

@mkozakov
Created October 29, 2013 06:48
  • Star 95 You must be signed in to star a gist
  • Fork 15 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save mkozakov/59af0fd5bddbed1a0399 to your computer and use it in GitHub Desktop.
Twitter Interview Solution
/* 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;
}
}
@sumerc
Copy link

sumerc commented Feb 24, 2014

@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.

@Mak-Sym
Copy link

Mak-Sym commented Feb 25, 2014

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

@Mak-Sym
Copy link

Mak-Sym commented Feb 25, 2014

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

@Pranz
Copy link

Pranz commented May 8, 2014

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

@bourneagain
Copy link

@isaiah-perumalla
Copy link

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

@harrytallbelt
Copy link

harrytallbelt commented May 18, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment