-
-
Save mkozakov/59af0fd5bddbed1a0399 to your computer and use it in GitHub Desktop.
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; | |
} | |
} |
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
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Thanks!
There is typo in my post - sorry about that
I meant this one: