Number of Ways to Build House of Cards

Number of Ways to Build House of Cards

What is this problem about?

The Number of Ways to Build House of Cards problem asks you to count distinct structures you can build with n playing cards arranged as a house of cards. Each horizontal level uses some cards as triangles (each triangle uses 3 cards: 2 leaning and 1 horizontal) and 2 cards between each adjacent pair of triangles. This coding problem derives a recurrence based on how many rows of triangles fit on each level.

Why is this asked in interviews?

Airbnb asks this to test the ability to derive DP recurrences from physical constraints. The key insight: a level with k triangles uses 2k cards (leaning) + (k-1) flat cards = 3k-1 cards. Enumerate k from 1 upward and recurse on remaining cards. The math and dynamic programming interview pattern is demonstrated.

Algorithmic pattern used

Memoized recursion. dp(n) = ways to build houses of cards using exactly n cards. For each possible bottom row with k triangles (using 3k-1 cards), if n >= 3k-1 and n-(3k-1) allows valid construction above, add dp(n - (3k-1)). Base cases: dp(0)=1 (empty valid structure), dp(1)=dp(2)=0 (can't make a triangle).

Example explanation

n=2: no valid structure. Answer=0. n=3: one triangle (2 cards + 1 flat, but actually 2 leaning + no flat = 3 cards for 1 triangle). Answer=1. n=14: try bottom rows of k=1 (uses 2 cards), k=2 (uses 5 cards), k=3 (uses 8 cards), k=4 (uses 11 cards). dp(14): k=1→dp(12), k=2→dp(9), k=3→dp(6), k=4→dp(3). Sum.

Common mistakes candidates make

• Off-by-one in the cards-per-row formula (verify with small examples).
• Not including the base case dp(0)=1.
• Using n cards instead of n-(3k-1) for the recursive step.
• Not memoizing (exponential recomputation without it).

Interview preparation tip

Physical/geometric DP problems require deriving the recurrence from the constraints. Always start by computing "how many cards does k rows use?" on paper. Verify with small cases (k=1: 3 cards for 1 triangle, k=2: 5 cards = 3+2 connecting, etc.). Once the formula is correct, the DP structure is straightforward. Practice similar "counting ways to tile/build a structure" problems to develop intuition for geometric recurrences.