Count Number of Ways to Place Houses

Count Number of Ways to Place Houses

What is this problem about?

There is a street with $n$ plots on each side (total $2n$ plots). You want to place houses such that no two houses are adjacent on the same side of the street. Houses on opposite sides of the street do not affect each other. You need to return the total number of ways to place the houses modulo $10^9 + 7$.

Why is this asked in interviews?

This problem, frequently asked by Microsoft and Amazon, tests your ability to decouple independent events and recognize standard sequences. Since the two sides of the street are independent, the total ways is simply (ways_for_one_side) * (ways_for_one_side). The problem then reduces to finding the number of ways to pick non-adjacent items from a line, which is a classic DP task.

Algorithmic pattern used

This uses Dynamic Programming, specifically the Fibonacci sequence logic.

1. Let dp[i] be the number of ways to place houses in i plots.
2. For the $i$-th plot, you have two choices:
   • Don't place a house: Then you have dp[i-1] ways.
   • Place a house: Then you couldn't have placed a house at i-1, so you have dp[i-2] ways.
3. dp[i] = dp[i-1] + dp[i-2].
4. This is the Fibonacci sequence where dp[1]=2 (empty, H) and dp[2]=3 (empty, H-, -H).

Example explanation

Let $n = 2$.

• One side of the street:
  • Plot 1, Plot 2: (Empty, Empty), (House, Empty), (Empty, House).
  • Total = 3 ways.
• Since there are two sides:
  • Total ways = $3 imes 3 = 9$. Result: 9.

Common mistakes candidates make

One frequent mistake is trying to solve both sides of the street simultaneously in one DP state, which makes the logic much more complicated. Another is missing the fact that the answer should be squared. Some candidates also forget to handle the modulo operation after the multiplication step.

Interview preparation tip

Always check if a problem can be broken down into independent sub-problems. If two parts of a system don't interact (like the two sides of the street), calculate the result for one part and use the multiplication principle of combinatorics.