Technically a Software Developer - Part 2

I’m on vacation this week in the beautiful Finger Lakes in New York (walked Watkins Glen today!) so I’ve been taking a small break from building and deploying websites. I’m starting a big project next week so the break won’t last long. In the meantime, I’ve been practicing algorithms at Codility in preparation of a technical assessment. It’s with the same company I interviewed with in the past, which made me realize I never finished discussing one of the problems from a couple months ago. I eventually came up with a simple solution, let me

Just a little refresher, the problem consisted of finding the least amount of steps it would take to a given parameter, N, starting from one by either doubling the number or adding one to it. The sample test case gave the parameter of 18, which should result in 6 steps.

[1] - 1
[2] - 2
[3] - 4
[4] - 8
[5] - 9
[6] - 18

Originally, I approached the problem as it was necessary to begin with 1 and work our way up to N, adding it to a hash. Basically I would double the number unless it was greater than N, then go back a step and add 1, looping this process until it equaled N, and finally returning the length of the hash

function Solution(n) {
    let ladder = {}
    ladder[0] = 1
    let x = 1
    while(!Object.values(ladder).includes(n)) {
        if (ladder[x-1]*2 > n) {
            ladder[x-1] = ladder[x-2] + 1
            ladder[x] = ladder[x-1]*2
        } else {
            ladder[x] = ladder[x-1]*2
        }
        x++
    }
    return Object.keys(ladder).length
}

The biggest issue with this solution was it would exceed the time limit when dealing with different edge cases including the maximum number N could be. Having to repeatedly reverse the accumulator was definitely not optimal, which was accomplished with too many if statements. What I’ve eventually learned is that using conditional statements increases time as well, so regardless if the solution produces the correct result, it would still fail the complexity part.

After banging my head against my desk for a while and scribbling on some scrap paper, I eventually had a eureka moment. The biggest realization, it was unnecessary to begin with 1 and slowly work our way up to N. Why not begin with N and work our way down to 1? This change in perspective also made me realize that I could also reverse my solution. Instead of doubling my accumulator, I could divide N if it was divisible by 2, or subtract 1 if not. Also, it was completely unnecessary to store the sequence in a hash just to return the length of the hash, as I only needed to keep a counter going after each step was made.

function Solution(n) {
    let x = 1
    while(n>1) {
        if (n%2===0) {
            n%2
        } else {
            n-=
        }
        x++
    }
    return x
}

As you could see, this cut my solution by more than half, and would reduce the space and time needed for large parameters. All in all it wasn't a very hard problem, especially evident with this solution. I've used this problem as a major learning moment, to look at things from a different perspective, to step back and approach the problem from a different angle.

While I continue to practice for future assessments, my favorite part is trying to make the solutions even smaller. Ternary operator has become my go to conditional statement. Finally, my final solution.

function Solution(n) {
    let x = 1
    while(n>1) {
        n = (n%2===0) ? n%2 : n-1
        x++
    }
    return x
}