Skip to content

Instantly share code, notes, and snippets.

@ubermajestix
Last active December 27, 2015 02:39
Show Gist options
  • Save ubermajestix/7253875 to your computer and use it in GitHub Desktop.
Save ubermajestix/7253875 to your computer and use it in GitHub Desktop.
Twitter Interview Question

This code visualizes the solution to this Twitter interview question.

My first solution only looked at immediate neighbors to figure out if you're in a trough that will collection water. The clever part is considering all values to the left and right of you, not immediate neighbors. My naive solution to [5,1,5] was pretty close, but as I expanded to more complex problems, considering your neighbors wasn't enough and my solution began to bloat. Looking at this answer gave me the insight to strip down my solution.

Once I had it solved I went back and built the simple solution display.

To run the tests simply run $> ruby -Itest rain_test.rb

# encoding: utf-8
class Rain
attr_reader :land, :volume
def initialize(land)
@land = land
@volume = 0
end
# from where you are you want to know if you're in a trough
# Moving left find the largest value, moving right find the largest value
# take the lesser of the two and subtract from yourself.
def calculate_volume
land.each_with_index{|h, index|
left = land[0..index].max
right = land[index..-1].max
if h < left && h < right
@volume += [left,right].min - h
end
}
return @volume
end
def print_solution
puts "\nBoard for #{land.inspect}"
max = land.max
max.times do |n|
n = max - n
l = []
land.each_with_index do |h, index|
left = land[0..index].max
right = land[index..-1].max
if h < left && h < right
if n <= [left,right].min && n > h
l << "•"
else
l << "|" if n <= h
l << " " if h < n
end
else
l << "|" if n <= h
l << " " if h < n
end
end
puts l.join
end
puts "_" * land.length
puts "Volume: #{calculate_volume}"
end
end
require 'minitest/autorun'
require_relative 'rain'
describe Rain do
specs = {
[1,2,3,4,5,4,5,3] => 1,
[2,1,2,3,4,2] => 1,
[5,1,5] => 4,
[2,7,2,1,7,4] => 11,
[2,8,2,1,7,4] => 11,
[2,7,2,-1,4,9] => 5+8+3,
[5,1,0,1] => 1,
[2,5,1,2,3,4,7,7,6,3,5] => 12
}
specs.each do |array, expected|
it "should provide #{expected} for #{array}" do
rain = Rain.new(array)
rain.print_solution
assert_equal expected, rain.volume, "Failed for #{array.inspect}"
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment