-
-
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; | |
} | |
} |
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
This seems to work ...
https://gist.github.com/bourneagain/0cb90851106756746933