How should I practice Coloring Houses?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Snowflake online assessment problems in FastPrep.

Is Coloring Houses associated with Snowflake?

FastPrep tags this as a Snowflake coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Dynamic Programming

Coloring Houses

Learn this problem

● MediumSnowflakeINTERNOA

See Snowflake hiring insights

Problem statement

The city of Hackerland can be represented with an even number n houses arranged in a row. A painter must paint the houses using at most three colors. The following conditions must hold true:

No two adjacent houses are the same color.

The houses which are at the same distance from both ends must not be colored with the same color. For example, n=6 then houses will be [1,2,3,4,5,6], so the houses at the same distance from both the ends will be [1,6], [2,5], [3,4].

The task is to find the number of ways to paint the houses using at most three colors such that both the above conditions hold true. Since the answer can be large, report it modulo 10^9 + 7. Two ways are considered different if at least one house is colored differently.

Function

countWaysToColorHouses(n: int) → int

Complete the countWaysToColorHouses function in the editor.

countWaysToColorHouses takes in a single parameter:

int n, the number of houses

Examples

Example 1

n = 4return = 18

For n = 4, some of the possible valid arrangements are:

(color1, color2, color3, color2)

(color1, color3, color1, color3)

The number of ways to paint 4 houses using three colors is 18. Return 18 modulo (10^9 + 7) which is 18.

Example 2

n = 2return = 6

The valid arrangements for 2 houses are: (color1, color2) (color1, color3) (color2, color1) (color3, color1) (color2, color3) (color3, color2)

Example 3

n = 4return = 18

Total valid arrangements for 4 hourses are 18. Some of the valid arrangements are: {color1, color2, color1, color2} {color1, color3, color1, color3} {color2, color1, color2, color1} {color3, color1, color3, color1} {color2, color3, color2, color3} {color3, color2, color3, color2}

Constraints

1 <= n <= 100000

n is an even integer