Skip to content

Instantly share code, notes, and snippets.

# mkozakov/gist:59af0fd5bddbed1a0399 Secret

Created October 29, 2013 06:48
Star You must be signed in to star a gist
Twitter Interview Solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 /* 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 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 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 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 commented May 8, 2014

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

### isaiah-perumalla commented Aug 13, 2015

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

### harrytallbelt commented May 18, 2016 • edited

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

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