Google Interview Question
Data EngineersCountry: United States
# n: number of columns to complete
# bo: boolean, whether the bottom square at the current col is open
# to: boolean, whether the top square at the current col is open
# memo: cached results
def rec(n, bo, to,memo)
# return the cached result if we have one
if memo.include?([n,bo,to])
return memo[[n,bo,to]]
end
r = if bo && to # if both squares are open
rec(n-1, true, true,memo) + # use a vertical piece
rec(n-2, true, true,memo) + # use two horizontal pieces
rec(n-1, false, true,memo) + # use an L piece, leaving top open
rec(n-1, true, false,memo) # use an L piece, leaving bottom open
elsif bo # if only the bottom is open
rec(n-1, false, true,memo) + # use a horizontal piece, leave the top open
rec(n-2, true, true,memo) # use an L shape to cover the bottom hole
else # if only the top is open
rec(n-1, true, false,memo) + # use a horizontal piece, leave the bottom open
rec(n-2, true, true,memo) # use an L shape to cover the top hole
end
memo[[n,bo,to]] = r
r
end
def solution(n)
memo = {
[1, true, true] => 1,
[1, false, true] => 0,
[1, true, false] => 0,
[2, true, true] => 2,
[2, true, false] => 1,
[2, false, true] => 1}
rec(n, true, true, memo)
end
- Anonymous January 24, 2018