Number of Ways to Build Sturdy Brick Wall

Number of Ways to Build Sturdy Brick Wall

What is this problem about?

The Number of Ways to Build Sturdy Brick Wall problem asks you to count ways to tile a wall of width width and height height using bricks of varying lengths (always fitting within width). Adjacent rows cannot have any shared seam positions (except at the ends). This coding problem uses bitmask DP over valid row patterns.

Why is this asked in interviews?

Microstrategy and Google ask this because it requires precomputing all valid single-row layouts (as bitmasks of seam positions), then counting arrangements of height rows where no two consecutive rows share a seam bit. The array, bitmask, bit manipulation, and dynamic programming interview pattern is comprehensively tested.

Algorithmic pattern used

Bitmask DP with compatible row precomputation. Generate all valid row patterns (bitmasks of seam positions) by recursively placing bricks. Build a compatibility matrix: two row patterns are compatible if (pattern1 & pattern2) == 0 (no shared seams). dp[i][p] = ways to have the first i rows with the i-th row being pattern p. Transition: sum over compatible patterns.

Example explanation

width=4, height=2. Bricks=[1,2]. Valid rows: [4-brick], [2+2], [1+3?], [2+1+1], [1+1+2], [1+1+1+1]. Represent seams as bitmasks (excluding ends). Compatible pairs: no shared seam bit. Count all compatible pairs of rows for height=2.

Common mistakes candidates make

• Including the wall endpoints as seam positions (seams are interior only).
• Incorrect compatibility check (should be (a & b) == 0, not XOR).
• Generating invalid row patterns (sum of brick lengths must equal width exactly).
• O(n²) compatibility check without precomputation.

Interview preparation tip

Tiling DP with bitmask representation is a powerful technique for grid problems where rows interact via shared boundaries. The key steps: (1) generate all valid row bitmasks, (2) precompute compatible pairs, (3) apply DP. Step 2 can be optimized by precomputing compatibility lists. Practice brick wall tiling and similar tiling problems where each row's pattern must be compatible with adjacent rows.