We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Interview Preparation Kits
  3. Lego Blocks
  4. Discussions

Lego Blocks

Sort by

recency

|

81 Discussions

|

  • dusankil
     + 0 comments

    Main points to take care about are: 1) calculate total number of combination per row using dynamic programming 2) inclusion/exclusion concept by splitting the wall on 2 parts - use dynamic programming for better performance 3) Fast/binary exponentiation by squaring the base and halving the exponent

    Java code

    public static long[] combinations;
    public static long modulo = 1000000007;
    private static long [] totals;
    private static long [] goods;
    private static long [] bads;
    public static int legoBlocks(int n, int m) {
        totals = new long[m+1];
        goods = new long[m+1];
        bads = new long[m+1];
        totals[0] = totals[1] = goods[0] = goods[1] = 1L;
        combinations = new long[m+1];
        combinations[0]=1L;
        long good = calculateGood(n,m);
        return (int) (good%modulo);
    }
    
    public static Long calculateGood(int n, int m) {
        if(goods[m]!=0) {
            return goods[m];
        }
        Long total = calculateTotal(n,m);
        Long bad = calculateBad(n,m);
        Long good = (total - bad)%modulo;
        if(good<0){
            good+=modulo;
        }
        goods[m] = good;
        return goods[m];
    }
    
    private static Long calculateBad(int n, int m) {
        if(bads[m]!=0){
            return bads[m];
        }
        Long totalBad = 0L;
        for(int i =1; i< m;i++) {            
            Long currentBad = (calculateGood(n, i)*calculateTotal(n, m-i))%modulo;
            totalBad=(totalBad+currentBad)%modulo;
        }
        bads[m]=totalBad%modulo;
        return totalBad;
    }
    
    private static Long calculateTotal(int n, int m){
        if(totals[m]!=0){
            return totals[m];
        }
        Long perRow = calculateCombinationsPerRow(m);
        
        long total = modPow(perRow, n);
        totals[m] = total%modulo;
        return totals[m];
    }
    
    private static long modPow(long base, int exponent) {
        long result = 1L;
        base = base % modulo;
        while (exponent > 0) {
            if (exponent%2 == 1) {
                result = (result * base) % modulo;
            }
            base = (base * base) % modulo;
            exponent /=2;
        }
    
        return result;
    }
    
    private static Long calculateCombinationsPerRow(int width){
        
        if(combinations[width]!=0){
            return combinations[width];
        }
        long total = 0L;
        if(width-4>=0){
            total += calculateCombinationsPerRow(width-4);
        }
        if(width-3>=0){
            total += calculateCombinationsPerRow(width -3);
        }
        if(width-2>=0){
            total += calculateCombinationsPerRow(width -2);
        }
        if(width-1>=0){
            total += calculateCombinationsPerRow(width -1);
        }
        combinations[width] = total%modulo;
        return combinations[width];
    }

  • LJM720
     + 0 comments

    Anyone know how I can improve my score (83.33) to 100.00. I've done all the optimisations I could think of..

    class Result {

    /*
 * Complete the 'legoBlocks' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER n (width)
 *  2. INTEGER m (height)
 */

// Cache previous C(n,m) calculations - All Combinations to build a wall with Brick sizes [1,4]
// Cache previous N(n,m) calculations - All Combinations to build a legitimate wall with no breaks

public static Map<String, BigInteger> C_n_m = new HashMap<>();
public static Map<String, BigInteger> N_n_m = new HashMap<>();
public static BigInteger modulo = BigInteger.valueOf(1_000_000_007);

public static BigInteger noBreakWalls(int n, int m) {
    String key = n + "," + m;
    if (N_n_m.containsKey(key)) return N_n_m.get(key);
    BigInteger sum = buildAnyWall(n, m);
    for (int i=1; i < n ; i++) {
        sum = sum.subtract(buildAnyWall(n-i, m).multiply(noBreakWalls(i, m))); 
    }
    sum = sum.mod(modulo);
    N_n_m.put(key, sum);
    return sum;
}

public static BigInteger buildAnyWall(int n, int m) {
    String key = n + "," + m;
    if (C_n_m.containsKey(key)) return C_n_m.get(key);
    if (n < 5) {
        BigInteger basecase = BigInteger.valueOf(2).modPow(BigInteger.valueOf(m*(n-1)), modulo);
        C_n_m.put(key, basecase);
        return basecase;
    } else {
        BigInteger row = buildAnyWall(n-1, 1)
                            .add(buildAnyWall(n-2, 1))
                                .add(buildAnyWall(n-3, 1))
                                    .add(buildAnyWall(n-4, 1))
                                        .modPow(BigInteger.valueOf(m), modulo);
        C_n_m.put(key, row);
        return row;
    }
}

public static int legoBlocks(int n, int m) {
    return noBreakWalls(n, m).intValue();
}

    }

  • knee982
     + 0 comments

    this question would be Hard Level in Leetcode

  • enadream
     + 1 comment

    One of the dumbest question I have ever seen. This is mathematical problem not algorithm or data structure.

  • joseespejo
     + 1 comment

    ┌──┬─┐
    ┼──┼─┼
    ┼──┴─┼
    └────┘

    Is this a valid wall? There are 2 rows with the same breaks but the total break doesnt reach the full height.