Sort by

recency

|

86 Discussions

|

  • + 1 comment

    I was so ready to give up on this Even with @dusanki solution, I didn't understand why the maths works.

    It was only when I found on the internet an explanation with pictures that it all clicked.

    I will probably implement it now. Just for closure. But I feel like Hackerrank has stolen a part of my life 😛

    • + 0 comments

      And now I've finally implemented an accepted solution I offer a little follow up to @jltd0jsn5's hint.

      Unfortunately BigInt doesn't (by itself) save the day for Javascript developers as it's too slow.

      I say that but I see solutions below whch seem to rely on it. So feel free to ignore me it if works for you.

  • + 1 comment

    so what kind of education do you need to be able solve this? i've been in IT 18 years and i don't think i could've ever solved this without internet assistance

    • + 0 comments

      This is a pretty intense combinatorial problem. For the record just figuring out all of the ways to stack n number of 1x2 lego bricks contiguously is itself a deep theoretical math question for mathemeticians, and only has a theorem that was proven in 1988.

      Even attempting to brute force the solution is itself a challenge to write, let alone something reasonably efficient. I think if any company expected you to do this problem I would ask if any of their engineers could solve it provided you make a small tweak to the parameters.

  • + 1 comment

    I don't know who needs to hears this, but as a 8 YoE software engineer, this took me an entire weekend to solve ^^'.

    A little spoiler-free tip I wish I had:

    • you will need to use the modulo whenever you can, because the amount of combination explodes pretty quickly. modulo is distributive over +, * and - operations, aka applying it to all those operators, is equivalent to only doing it once at the end.
    • even with modulo, in Typescript/Javascript you will need to watch out for some exploding results that exceed the maximum javascript integer (2^53-1)
    • + 0 comments

      The very idea anyone would think this is a good thing to test someone on in a time limited scenario is patently absurd, how is this how hiring is done now?

  • + 0 comments

    Having some difficult with a valid JavaScript version. The values that are failing are when combinations get over MOD (10^9 +7) Has anybody got a JavaScript version working or can spot the error in this code? Thanks

    *(legoBlocks(8,10) on my code is giving 634608018.

    Hacker rank is giving 634597424*


    function legoBlocks(h, w) {
        // Write your code here
        let mod = (Math.pow(10, 9) + 7)
    
        //different combinations for a width when height is 1
        let t = [0];
        if (w >= 1) t.push(1)
        if (w >= 2) t.push(2)
        if (w >= 3) t.push(4)
        if (w >= 4) t.push(8)
        while (w >= 5 && t.length <= w){
            let start = t.length -4
            let arr = t.slice(start, t.length)
            let sum = arr.reduce((partialSum, a) => partialSum + a, 0)
            t.push(sum)
        }
    
        //different combinations for width given height h
        //e.g. total[height=2] is t^2, total[height=3] is t^3
        let total = t.slice()
        for (let outer=2; outer<=h; outer++) {
            for (let i = 0; i <= w; i++) {
                total[i] = (t[i] * total[i])
            }
        }
    
    
        let solid = []
        solid.length = w+1;
        solid.fill(0)
        solid[1] = 1
    
        //s[x] = total[x] - (SUM (where i starts at 1 and ends at x-1)  s[i] * total[w-i]))
        if (w>1){
            for (let ww=2; ww<=w; ww++){
                let unsolid_sum = 0;
                for (let i=1; i<ww; i++){
    
                    unsolid_sum += (((solid[i]) * (total[ww-i])))
                }
                solid[ww] = ((total[ww] - unsolid_sum))
            }
        }
    
    return solid[w] % mod
    

    }

  • + 0 comments

    This question wrinkled my brain until I looked at Willis42's code. Here's some extra annotation in case it helps.

    def legoBlocks(n, m): # the ways to build a line of m from 0 up to 4 using legobricks from 1-4 # this takes the prev sums and adds one more way to it each time permutations = [0, 1, 2, 4, 8] mod = 10**9+7 # just keeps our numbers from getting too large - wraps if so

    # for the rest, use dp to keep compiling the already set base cases. We dont need to add one more way here (like we did above) because we already compiled all the ways for bricks from 1-4 now if m is >=5 we just need to get the last 4 subproblems we already compiled and sum them. Remember, don't add "one more" bc we're not adding a "new way" bc we only consider lego bricks from 1-4. Permutations array already holds all the ways for 1-4, we just want to grab the already computed prev 4 ways each time. 
    
    for i in range(5, m+1): 
        permutations.append((permutations[i-1]  + permutations[i-2] + permutations[i-3] + permutations[i-4])% mod)
    
    # at this point we have all possible permutations of bricks from 1-4 up to m
    # now we need to calculate n (height) 
    # we need to loop through all our permutations for each m, and raise them to the power of n to get all possible combinations up to n for each mth row.
    
    for i in range(len(permutations)): 
        permutations[i] = (permutations[i] ** n) % mod
    
    # now we have all possible but we need to introduce our condition to reduce by "bad" walls 
    # start with setting "good" permutations as 0 and 1 ( we dont have to worry about reducing till start stacking) 
    good_permutations = [0,1]
    
    for i in range(2, m+1): # starting at 2 we are stacking rows
        current = permutations[i] # grab the current one assuming all are "good"
        for j in range(1, i): # now loop from each last known "good" section and subtract the right assuming all bad. as we move, we are only keeping known "good" sections and building on them            
            current -= (good_permutations[j] * permutations[i-j])
        good_permutations.append(current % mod)
    return good_permutations[m]