/* 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; | |
} | |
} |
This comment has been minimized.
This comment has been minimized.
sathya-me
commented
Oct 30, 2013
will this work for the following case [2,7,2,7,4,7,1,7,3,7] |
This comment has been minimized.
This comment has been minimized.
joist
commented
Oct 30, 2013
@sathya-me : It does handle it properly. The left and the right pointers rise to 7 and then fill in all the gaps until they meet. I tried my own hand at this problem and came up with a slightly more naive (but clearer) solution : https://gist.github.com/Joist/7229807 edit: I put my own attempt at the single pass method in my code with comments to make it a bit clearer. |
This comment has been minimized.
This comment has been minimized.
msimpson
commented
Oct 30, 2013
I wrote up a solution using JS, here: https://gist.github.com/msimpson/eb0189dd687d696ab70a Mine is based on the point-inside-polygon methodology. It is more complex than what is above, and generates a maximum height at the start. However, it would continue to work with only slight modification on a two, or possibly three, dimensional matrix -- even with gaps inside columns that create enclosed areas. |
This comment has been minimized.
This comment has been minimized.
orukusaki
commented
Oct 30, 2013
Quick PHP version: https://gist.github.com/orukusaki/bb189d9f69ad09e2cd5a |
This comment has been minimized.
This comment has been minimized.
dmitry
commented
Oct 30, 2013
Looked for the solutions and rewritten them to the ruby: https://gist.github.com/dmitry/287bd6cad9abc70436f4 |
This comment has been minimized.
This comment has been minimized.
shaobohou
commented
Oct 30, 2013
Another single pass solution, https://gist.github.com/shaobohou/7231961 |
This comment has been minimized.
This comment has been minimized.
Shruubi
commented
Oct 30, 2013
Did up a small Python solution passing both test cases: https://gist.github.com/Shruubi/7232152 |
This comment has been minimized.
This comment has been minimized.
Zibx
commented
Oct 30, 2013
JS implementation. 2n complexity https://gist.github.com/Zibx/7235776 |
This comment has been minimized.
This comment has been minimized.
thisvar
commented
Oct 30, 2013
Java, n complexity, single straight pass from left to right : https://gist.github.com/anonymous/7236132 |
This comment has been minimized.
This comment has been minimized.
twuttke
commented
Oct 30, 2013
Slightly simpler, slightly faster, and handles negative heights: http://jsbin.com/iquQOSo/1/edit function maxWater(heights) {
var left = 0,
right = heights.length - 1,
leftMax = heights[left],
rightMax = heights[right],
volume = 0;
while (left < right) {
if (leftMax < rightMax) {
var height = heights[++left];
leftMax = Math.max(leftMax, height);
volume += leftMax - height;
} else {
var height = heights[--right];
rightMax = Math.max(rightMax, height);
volume += rightMax - height;
}
}
return volume;
} |
This comment has been minimized.
This comment has been minimized.
olajep
commented
Oct 30, 2013
Did a quick Haskell solution: https://gist.github.com/olajep/7236551
|
This comment has been minimized.
This comment has been minimized.
Zibx
commented
Oct 30, 2013
JS one cycle implementation. https://gist.github.com/Zibx/7235776/726b210cf6b6c646a925c911bb00a5ab68200810 |
This comment has been minimized.
This comment has been minimized.
AndroidHumanoid
commented
Oct 30, 2013
Short Java public static int mycalculateVolume(int[] land) {
|
This comment has been minimized.
This comment has been minimized.
hwmrocker
commented
Oct 30, 2013
me too, i used just one iteration https://gist.github.com/hwmrocker/7241002 |
This comment has been minimized.
This comment has been minimized.
pavelfatin
commented
Oct 30, 2013
O(n) recursive one-liners (Haskell, Clojure, Scala) |
This comment has been minimized.
This comment has been minimized.
domluna
commented
Oct 31, 2013
Solution in julia, just did a simple linear walkthrough https://gist.github.com/Niessy/7243069 |
This comment has been minimized.
This comment has been minimized.
amuraco
commented
Oct 31, 2013
Single Iteration Streaming Java solution. Not that memory friendly though. |
This comment has been minimized.
This comment has been minimized.
jdanielmyers
commented
Oct 31, 2013
pretty simple single pass python solution: https://gist.github.com/jdanielmyers/7245316 |
This comment has been minimized.
This comment has been minimized.
leikind
commented
Oct 31, 2013
My take: https://gist.github.com/leikind/7247086 Maybe not the most efficient, but it's only 10 lines of code of functional style Ruby |
This comment has been minimized.
This comment has been minimized.
abo-abo
commented
Oct 31, 2013
My take in Clojure: https://gist.github.com/abo-abo/7247459 . |
This comment has been minimized.
This comment has been minimized.
flowolf
commented
Oct 31, 2013
here is my Python solution: |
This comment has been minimized.
This comment has been minimized.
KvanTTT
commented
Oct 31, 2013
There is my awful but satisfactory solution with all answers generation for predifined count of walls and max wall height (in my case 8 * 8): https://github.com/KvanTTT/Twitter-Puddles-Counter But it's not ideal. Number of answers can be reduced to 4 times due to symmetry along x and y axis. I mean |
This comment has been minimized.
This comment has been minimized.
Areks
commented
Oct 31, 2013
Hello guys, let me show my decision )) |
This comment has been minimized.
This comment has been minimized.
ghost
commented
Oct 31, 2013
PHP solution: public function findVolume($arr) {
} |
This comment has been minimized.
This comment has been minimized.
fergara
commented
Oct 31, 2013
The Groovy version: https://gist.github.com/fergara/7250590#file-calculaterainvolume-groovy |
This comment has been minimized.
This comment has been minimized.
ghost
commented
Oct 31, 2013
@AndroidHumanoid |
This comment has been minimized.
This comment has been minimized.
oralokan
commented
Oct 31, 2013
I did a python implementation based on a simple observation. For a square to be filled with water, it has to fulfill these two conditions:
|
This comment has been minimized.
This comment has been minimized.
ubermajestix
commented
Oct 31, 2013
Here's my solution in ruby that prints the board: https://gist.github.com/ubermajestix/7253875 |
This comment has been minimized.
This comment has been minimized.
DrewFitz
commented
Oct 31, 2013
Here's mine which solves it in one pass. https://gist.github.com/DrewFitz/7254644 It moves through the array keeping a list of unresolved "left walls" and resolves the guaranteed water blocks when hitting a right wall. Each time it resolves, it only adds the new blocks gained by "raising" the puddle's water level. |
This comment has been minimized.
This comment has been minimized.
Ruszrok
commented
Oct 31, 2013
I have solution - https://gist.github.com/Ruszrok/3adc23baa83b97de7145 |
This comment has been minimized.
This comment has been minimized.
HollyGurza
commented
Nov 1, 2013
my Python solution - https://gist.github.com/HollyGurza/7261085 please test this |
This comment has been minimized.
This comment has been minimized.
benjaminliu
commented
Nov 1, 2013
Here is a test case, please try it and here is my solution, double loop, much slower |
This comment has been minimized.
This comment has been minimized.
jianchenglee
commented
Nov 1, 2013
my lua solution: https://gist.github.com/jianchenglee/7262518 |
This comment has been minimized.
This comment has been minimized.
bxt
commented
Nov 1, 2013
I have created a python solution that makes random landscapes like this one:
|
This comment has been minimized.
This comment has been minimized.
AndroidHumanoid
commented
Nov 1, 2013
Decker108 "I like your solution, but unfortunately it doesn't work for [2, 5, 1, 2, 3, 4, 7, 5, 6] which should give 11." Yeees, what about that (it seems work, but how): https://gist.github.com/AndroidHumanoid/7241202
|
This comment has been minimized.
This comment has been minimized.
BorzdeG
commented
Nov 2, 2013
my version of the solution with 22 test models: https://github.com/BorzdeG/info.alenkov.demo.puddle_rain |
This comment has been minimized.
This comment has been minimized.
philipnilsson
commented
Nov 5, 2013
Probably the most elegant solution to this problem is using scanl/r and zipWith. Corresponds very closely to the mathematical breakdown of this problem. Here's a solution in Haskell. water hs
= sum $ zipWith (flip (-)) hs
$ zipWith min (scanl1 max hs) (scanr1 max hs) |
This comment has been minimized.
This comment has been minimized.
skariel
commented
Nov 6, 2013
Mot solutions are actually wrong... |
This comment has been minimized.
This comment has been minimized.
yannick1974
commented
Nov 6, 2013
Hi all, Another solution in Python using numpy (and matplotlib): https://gist.github.com/yannick1974/7334581 Yannick |
This comment has been minimized.
This comment has been minimized.
celwell
commented
Nov 7, 2013
So does this work for: 4,0,0,4,0,4,0,0,4,2 ? |
This comment has been minimized.
This comment has been minimized.
syfou
commented
Nov 8, 2013
Yet another solution: https://gist.github.com/syfou/7364514 It uses recursion: I tried to go for a readable and a painless, quickly implemented solution rather than something more clever. |
This comment has been minimized.
This comment has been minimized.
est
commented
Nov 11, 2013
my dumb but working version
|
This comment has been minimized.
This comment has been minimized.
thulka
commented
Nov 12, 2013
mkozakov's solution is quite perfect, no allocations, no stack uage. single pass, recursive in python: https://gist.github.com/thulka/7429806 btw, est, your solution wrong: [7,0,5,0,7,0] should be 16, yours returns 14. also you might have hidden loops in the list selectors, so not perfectly single pass. finally, it was about an elegant solution, not just a dumb working one. a simple working one, non single pass would be: for each bin the water = min(leftmax, rightmax) - current height |
This comment has been minimized.
This comment has been minimized.
chrisdone
commented
Nov 12, 2013
My first thought was to use a spreadsheet. Here's that in Haskell:
It makes a vector where the value of each cell is calculated based on the two neighboring cells. Except edges, who only have one neighbor. It's a direct way of writing how I thought of the problem statement:
Done. Oh, the
|
This comment has been minimized.
This comment has been minimized.
neuronsguy
commented
Nov 12, 2013
Short, single-pass python solution q = [2,5,1,3,1,2,1,7,7,6]
def solve(heights):
water = [0]*len(heights)
total = 0
runoff = 0
for i,height in enumerate(heights):
if i == 0:
continue
above = max(height, heights[i-1] + water[i-1]) - height
water[i] = above
if water[i] == 0:
runoff = 0
else:
runoff += water[i]
return sum(water)-runoff
print q, solve(q)
|
This comment has been minimized.
This comment has been minimized.
chrisdone
commented
Nov 13, 2013
@neuronsguy That's an incomplete solution, it only works in one direction. E.g. |
This comment has been minimized.
This comment has been minimized.
chrisdone
commented
Nov 13, 2013
@DrewFitz Only works properly in one direction.
|
This comment has been minimized.
This comment has been minimized.
chrisdone
commented
Nov 13, 2013
@HollyGurza Only works properly in one direction. You guys really need to think about the problem in both directions. |
This comment has been minimized.
This comment has been minimized.
chrisdone
commented
Nov 13, 2013
@igor47 Only works in one direction. |
This comment has been minimized.
This comment has been minimized.
tmoertel
commented
Nov 14, 2013
Thanks for the fun problem :-) I ended up solving it recursively, working from the base cases up to a general solution, and then I converted the recursive algorithm into the following Python function taking a height array A. For a problem of size len(A) = N, the function requires O(N) time and O(1) space. For a full derivation of the algorithm, starting from first principles, see the (extensive) discussion in the source code: https://github.com/tmoertel/practice/blob/master/water-holding-capacity/water_holding_capacity.py def water_holding_capacity_iterative(A):
(i, j) = (0, len(A) - 1)
lm = rm = vol = 0
# while segments remain, consume left- or right-end segment
while i <= j:
if lm < rm:
vol += max(0, lm - A[i])
lm = max(lm, A[i])
i += 1
else:
vol += max(0, rm - A[j])
rm = max(rm, A[j])
j -= 1
return vol |
This comment has been minimized.
This comment has been minimized.
emakarov
commented
Nov 16, 2013
python:
|
This comment has been minimized.
This comment has been minimized.
emakarov
commented
Nov 16, 2013
or one-way loop in python
|
This comment has been minimized.
This comment has been minimized.
divipp
commented
Nov 20, 2013
Another Haskell solution, O(1) space when switched to foldl' and strict tuples:
|
This comment has been minimized.
This comment has been minimized.
andrewnguyen42
commented
Dec 2, 2013
Elegant one liners are cool! Sadly mine is not one of those. I start by calculating what the maximum amount of water that could be held is. Then, I go level by level and remove blocks that would have fallen off. Think of it as if you dipped a lego structure into a bathtub and pulled it out: every hole is filled at first, but as you pull it out of the water, each level loses some water. |
This comment has been minimized.
This comment has been minimized.
vvsh
commented
Dec 5, 2013
rightMax should be equals land.length - 1 |
This comment has been minimized.
This comment has been minimized.
allumbra
commented
Dec 19, 2013
Short JS solution: |
This comment has been minimized.
This comment has been minimized.
joneschris
commented
Dec 20, 2013
Another Python solution - https://gist.github.com/joneschris/8049901 |
This comment has been minimized.
This comment has been minimized.
markcrandall
commented
Dec 20, 2013
Here is a solution using C# and one lambda using System;
using System.Linq;
namespace TwitterInterviewAnswer
{
class Program
{
static void Main(string[] args)
{
//the data
int[] wallHeights = {2, 5, 1, 2, 3, 4, 7, 7, 6};
//the lambda expression
Func<int[], int> volume = walls => walls.Skip(1).Take(walls.Count() - 2)
.Select((s, i) => new {s, i})
.Select(v => new[]
{
walls.Take(v.i + 1)
.Max(),
walls
.Skip(v.i + 2)
.Max()
}
.Min() - v.s)
.Where(w => w > 0)
.Sum();
//the output
Console.WriteLine("The volume is: {0}", volume.Invoke(wallHeights));
Console.ReadKey();
}
}
} |
This comment has been minimized.
This comment has been minimized.
@jbojcic your code won't work for something like [7,3,2,4]. |
This comment has been minimized.
This comment has been minimized.
jbojcic
commented
Jan 19, 2014
@mkozakov it won't fill up water that should spill out but it will spill out everything, which is also wrong |
This comment has been minimized.
This comment has been minimized.
sumerc
commented
Feb 18, 2014
# Actually the original implementation is as following which is done in n-pass:
def water_vol_orig(a):
lv = rv = -1
result = lmax = rmax = l = 0
r = len(a)-1 # no pass on array
while (l < r):
lv = a[l]
if lv > lmax:
lmax = lv
rv = a[r]
if rv > rmax:
rmax = rv
if lmax >= rmax:
result += rmax - rv
r -= 1
else:
result += lmax - lv
l += 1
return result
# This implementation avoids the lookup for the max item in the array to finish in n-pass.
# However, it is doing 3 comparisons inside the inner loop and in dynamic languages like Python/Java
# indexed access to an array is expensive, using enumerators is far more effective.
# So more efficient way of doing this in Python may be:
#1) find the max item
#2) approach to max item from left and right.
def water_vol_fast(a):
def _imax(x): # find max in single pass, faster than max(..,itemgetter(..))
max_idx = max_val = 0
for i, v in enumerate(a):
if v > max_val:
max_val = v
max_idx = i
return max_idx
def _volp(x):
max = result = 0
for e in x:
if e > max:
max = e
else:
result += max - e
return result
imax = _imax(a) # n-pass
return _volp(a[:imax]) + _volp(reversed(a[imax:])) # n pass
# This version will have 2N comparisons(1N for finding max and 1N for calculating the volume) and no index
# based access to any array.
# If these are profiled, one can see the difference:
# water_vol_orig takes 0.405603 CPU Secs, and water_vol will take 0.265202 which is nearly %80 faster.
# You can test above by:
# for test:
import random
a = [int(1000*random.random()) for i in range(10000)]
assert water_vol_orig(a) == water_vol_fast(a) |
This comment has been minimized.
This comment has been minimized.
Mak-Sym
commented
Feb 23, 2014
Hm... tried to run original solution against the data with 3 maximums and it didn't work...
|
This comment has been minimized.
This comment has been minimized.
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. |
This comment has been minimized.
This comment has been minimized.
Mak-Sym
commented
Feb 25, 2014
Thanks! There is typo in my post - sorry about that
|
This comment has been minimized.
This comment has been minimized.
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 :) ) |
This comment has been minimized.
This comment has been minimized.
Pranz
commented
May 8, 2014
unspoiled solution; I think mine works the same way as yours. |
This comment has been minimized.
This comment has been minimized.
bourneagain
commented
Sep 10, 2014
This seems to work ... |
This comment has been minimized.
This comment has been minimized.
isaiah-perumalla
commented
Aug 13, 2015
here is an alternate but simple nlog(n) solution |
This comment has been minimized.
This comment has been minimized.
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 |
This comment has been minimized.
igor47 commentedOct 30, 2013
fun problem! i took a stab at it also: https://gist.github.com/igor47/7228586