Created
January 13, 2015 21:00
-
-
Save binarybana/027c49dc286e6a8abcfe to your computer and use it in GitHub Desktop.
Interview Question
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
using PyPlot | |
using Base.Test | |
function minops{T<:Integer}(n::T) | |
queue = (T,T)[] | |
push!(queue, (n,0)) | |
visited = Set{T}() | |
pops,evals = 0,0 | |
while true | |
pops += 1 | |
val,depth = shift!(queue) | |
val in visited && continue | |
evals += 1 | |
# Subtract one | |
val-1 == 1 && return depth+1 | |
push!(queue, (val-1,depth+1)) | |
# Divide by two | |
if val%2 == 0 | |
div(val,2) == 1 && return depth+1 | |
push!(queue, (div(val,2),depth+1)) | |
end | |
# Divide by three | |
if val%3 == 0 | |
div(val,3) == 1 && return depth+1 | |
push!(queue, (div(val,3),depth+1)) | |
end | |
# Don't duplicate the above work | |
push!(visited, val) | |
end | |
end | |
function minops_rev{T<:Integer}(n::T) | |
queue = (T,T)[] | |
push!(queue, (1,0)) | |
visited = Set{T}() | |
evals = 0 | |
while true | |
val,depth = shift!(queue) | |
evals += 0 | |
val in visited && continue | |
# Add one | |
val+1 == n && return depth+1 | |
push!(queue, (val+1,depth+1)) | |
# Multiply by two | |
if val*2 <= n | |
val*2 == n && return depth+1 | |
push!(queue, (val*2,depth+1)) | |
end | |
# Divide by three | |
if val*3 <= n | |
val*3 == 1 && return depth+1 | |
push!(queue, (val*3,depth+1)) | |
end | |
# Don't duplicate the above work | |
push!(visited, val) | |
end | |
@show evals | |
end | |
function minops_dp{T<:Integer}(n::T) | |
solns = Array(T,n) | |
solns[1] = 0 | |
for i=2:n | |
solns[i] = 1 + solns[i-1] | |
i%2 == 0 && (solns[i] = min(solns[i], 1 + solns[div(i,2)])) | |
i%3 == 0 && (solns[i] = min(solns[i], 1 + solns[div(i,3)])) | |
end | |
return solns[n] | |
end | |
@test minops(5) == 3 | |
@test minops(10) == 3 | |
@test minops_rev(5) == 3 | |
@test minops_rev(10) == 3 | |
@test minops_dp(5) == 3 | |
@test minops_dp(10) == 3 | |
sizes = int(logspace(1,7,20)) | |
loglog(sizes, [@elapsed minops(x) for x in sizes], label="BFS down") | |
loglog(sizes, [@elapsed minops_rev(x) for x in sizes], label="BFS up") | |
loglog(sizes, [@elapsed minops_dp(x) for x in sizes], label="DP") | |
xlabel("Starting positive integer n") | |
ylabel("Seconds") | |
title("Time to compute minimum number of operations to unity") | |
legend(loc="best") | |
@time minops(typemax(Int)-1) | |
@time minops(BigInt(2)^100-1) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment