Java Collection Framework (java.util.* package) is a unified architecture for representing and manipulating collections. This post is a quick note of my knowledge about Java Collection Framework that covers frequently used java data structure to store a group of elements and/or key-value pairs. In the java.util framework, there are two major camps - Collections & Map.

To illustrate, I use solid lines to denote 'extends', and dash lines to denote 'implements'. The way to use my note is to first go to the diagram looking for the specific class or interface, then read the brief blurb that'll remind you what the class or interface is about for the right data structure.

There is a wall of size 4xN. You have infinite supply of bricks of size 4x1 and 1x4 in the house. How many ways are there to fill out a wall of size 4xN?

This can be addressed by dynamic programming. The characteristics of optimal substructure, recursive nature, and bottom-up approach were mentioned in this post. 

Let's say, number of ways to fill out a wall of size 4xN with infinite supply of 4x1 and 1x4 bricks is said to be f(N). Per common sense, we know:

f(1) = 1
f(2) = 1
f(3) = 1
f(4) = 2

Also, when you think about it when filling out 4xN with f(N) ways of doing it, you can break f(N), when N >= 4, down to 2 substructures as below. Given the fact that one 4x1 can goes either horizontally or vertically. When it goes horizontally, there's only one way as shown in f(N-1). But when it goes vertically, all other 3 bricks may need to go vertically as well as seen in f(N-4) below.