Hi,
The following question was asked to me in the google phone screening round that took place during first week of July.

Problem Statement:
Find the number of possible different combinations to fill a 4 x N area (4 units height and N units width, N ≥ 1) with tiles of dimention 4 x 1 (4 units height and 1 unit width).

For example:
if N = 5, answer is 3

Possible combinations for N = 5:

1:

  | | | | |
  | | | | |
  | | | | |
  | | | | |

2:

  _ _ _ _ |
  _ _ _ _ |
  _ _ _ _ |
  _ _ _ _ |

3:

  | _ _ _ _
  | _ _ _ _
  | _ _ _ _
  | _ _ _ _

How I approached the optimized solution:
Brute Force -> Dynamic Programming -> Further O(1) space optimization

Clarifying questions I asked:

• Can I place the tiles in horizontally and vertical both ways? -> Yes
  in the above example, a 4 x 1 tile is can be placed in two ways, vertical and horizontal, as:

horizontal:
_ _ _ _

vertical:
|
|
|
|

Similar problems I could find:

1. https://leetcode.com/problems/domino-and-tromino-tiling/

Thanks