Skip to content

Instantly share code, notes, and snippets.

@binarybana

binarybana/interview.jl

Created January 13, 2015 21:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save binarybana/027c49dc286e6a8abcfe to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save binarybana/027c49dc286e6a8abcfe to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. binarybana created this gist Jan 13, 2015.
    100 changes: 100 additions & 0 deletions interview.jl
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,100 @@
    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)