Last active
December 27, 2015 00:09
-
-
Save Zibx/7235776 to your computer and use it in GitHub Desktop.
Quest from twitter interview
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
var calculate = function( arr ){ // one cycle solution | |
var minMax, | |
sum = 0, | |
fullSum = 0, | |
el, | |
maxMax, | |
i, _i = arr.length - 1; | |
minMax = arr[0]; // first item is the current left max | |
maxMax = arr[_i]; // last item is the current right max | |
for( i = 0; i <= _i; i++ ){ | |
el = arr[ i ]; | |
if( minMax < el ){ // if the wall is getting higher | |
sum += ( el - minMax ) * i; //add rectangular currentHeight-lastHeight x distanceFromStart | |
fullSum += ( el - minMax ) * i; //add such rectangular to the whole avaliable free space | |
minMax = el; | |
}else{ // if we are getting down | |
fullSum += minMax - el; // add down delta to the whole avaliable free space sum | |
} | |
el = arr[ _i - i ]; | |
if( maxMax < el ){ // same from the right side | |
sum += ( el - maxMax ) * i; | |
maxMax = el; | |
} | |
} | |
return fullSum - sum; // here we get whole avaliable space and reversed space that would be filled with water | |
}; | |
// testing | |
[ | |
[[0,0,0,10,0,0,0,0,0],0], | |
[[0,1,0,10,0,0,0,0,0],1], | |
[[1,0,1], 1], | |
[[5,0,5], 5], | |
[[0,1,0,1,0], 1], | |
[[1,0,1,0,1,0,1,0], 3], | |
[[1,0,1,0], 1], | |
[[1,0,1,2,0,2], 3], | |
[[2,5,1,2,3,4,7,7,6], 10], | |
[[5,1,0,1],1], //# thanks https://news.ycombinator.com/item?id=6640085 | |
[[2,5,1,2,3,4,7,7,6,3,5], 12] //# thanks https://news.ycombinator.com/item?id=6640105 | |
].forEach(function( el ){ | |
if( calculate( el[0] ) !== el[1] ) throw( el ); | |
}); |
Not sure if I understand you. You can't replace sum += to sum -= cause you don't know sum at the very begining, so you need to pass all elements at least once to calculate it (and find out minMax value). Please check my fork. I'm not very experienced with JS, but hope solution is clear.
I really liked your idea to calculate 'air' rectangles. In my tests it showed better speed (~10-20%) then solution in original habrahabr topic, especially with big arrays.
As for GIF - have you checked the following link?
http://stackoverflow.com/questions/10486084/generate-animated-gif-with-html5-canvas
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
You are quite right, also I can stop calculating it and just change sum += to sum -= and replace fullSum += to sum -=. But I like this solution geometrically, I draw it first on paper and it looks logical and cool, I want to make a gif with an animation of process, but for me it's easier to make it on canvas, but I haven't got skill to convert it to gif :(