## Google Interview Question for Software Engineer / Developers

• 3

Country: Israel
Interview Type: In-Person

Comment hidden because of low score. Click to expand.
11
of 13 vote

At first it seems like a dynamic programming type of problem but looking more closely it reduces to the simple problem of finding the nth Fibonacci number. Denote by f(n) the number of possibilities to tile a 2xn board.

Consider tiling a 2xn board for some n>2. Let us sort all the possibilities according to the last 2 columns. There are f(n-1) possibilities where the last column includes a single tile and there are f(n-2) possibilities where the last 2 columns include 2 horizontally placed tiles. This covers all possibilities and hence: f(n) = f(n-1) + f(n-2) which is exactly the nth Fibonacci number.

The common iterative O(n) solution for finding the nth Fibonacci number is as follows:

``````public static long tilings(int n){
if (n<=0){return 0;}
if (n==1){return 1;}
long prev = 1;
long cur = 2;
for (int i=3;i<=n;i++){
cur += prev;
prev = cur - prev;
}

return cur;
}``````

A more efficient solution (O(logn) can be achieved by using the matrix representation for finding the nth Fibonacci number:

``````private boolean isLegal2By2Matrix(long[][] m){
if ((m==null) || (m.length!=2)){return false;}
for (int i=0;i<m.length;i++){
if ((m[i]==null) || (m[i].length!=2)){return false;}
}

return true;
}

private long[][] mul(long[][] m1, long[][] m2){
if ((!isLegal2By2Matrix(m1)) || (!isLegal2By2Matrix(m2))){return null;}

long[][] res = new long;

for (int i=0;i<res.length;i++){
for (int j=0;j<res[i].length;j++){
res[i][j] = (m1[i]*m2[j]) + (m1[i]*m2[j]);
}
}

return res;
}

private long[][] nthPower(long[][] m, int n){
if ((n<1) || (!isLegal2By2Matrix(m))){return null;}
if (n==1){return m;}
long[][] pM = nthPower(m,(n/2));
long[][] res = mul(pM,pM);

return (n%2==0) ? res : mul(res,m);
}

public long tilings2(int n){
if (n<=0){return 0;}
if (n<=2){return n;}

long[][] m = {{1,1},{1,0}};
long[][] fm = nthPower(m,n-2);

return (fm*2) + fm;
}``````

Comment hidden because of low score. Click to expand.
0

I consider f(0) as 0 (the 0 Fibonacci number is 0 instead of 1)

Comment hidden because of low score. Click to expand.
1
of 1 vote

How about the case where the last two columns consists of two vertically placed tiles? I think your formula should be:

f(n) = 2*f(n - 1) + f(n - 2)

with f(0) = 0 and f(1) = 1

So you were right the first time. This is indeed a DP problem.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Forgive me. The case with f(n - 1) and the single vertical tile already takes care of this. False alarm.

Nice solution! :)

Comment hidden because of low score. Click to expand.
1
of 1 vote

Please clear my doubt. Are all arrangements unique? What I mean it consider a 2x3 board, there can be 2 unique ways of arranging 2x1 tiles. However, you can also do another ways if you consider all arrangements unique.

_____
| |___|
I_ |___| is same as

_____
|___| |
|___| _|

Comment hidden because of low score. Click to expand.
-1
of 1 vote

As per question, the target board is 2*n, why are you making it complicated by considering m*n?

Comment hidden because of low score. Click to expand.
0
of 0 vote

I din't understand why f(3) is not 24: here are all the possibilities:

If I'm right the formula to f(n) is f(n)=n*2*f(n-1), or I'm missing something?

``````|a|b|c| |a|c|b| |b|a|c| |b|c|a| |c|b|a| |c|a|b|
|a|b|c| |a|c|b| |b|a|c| |b|c|a| |c|b|a| |c|a|b|

|a|a|c| |b|b|c| |a|a|b| |c|c|b| |c|c|a| |b|b|a|
|b|b|c| |a|a|c| |c|c|b| |a|a|b| |b|b|a| |c|c|a|

|c|a|a| |c|b|b| |b|a|a| |b|c|c| |a|c|c| |a|b|b|
|c|b|b| |c|a|a| |b|c|c| |b|a|a| |a|b|b| |a|c|c|``````

Comment hidden because of low score. Click to expand.
0

Your first line is 6 times the same solution.
Your two last lines are also only one solution.

Comment hidden because of low score. Click to expand.
0
of 0 vote

I think the solution would be
F(n) = int(n/2) * (n+1)

Every 2x2 block on the board will result in 2 ways.. and in 'n' is odd, we need to place one more block which has n + 1 options.

Can anyone please tell me if this doesn't work in any case?

Thank you.

Comment hidden because of low score. Click to expand.
0
of 0 vote

f(1) = 1 + (1-1)+ (1-1) = 1
f(2) = 2 + (2-1)+ (2-1) = 4

Comment hidden because of low score. Click to expand.
0
of 0 vote

It's a combination problem

for i from 0 to [n/2]
sum = 0
sum = sum + Combination (pick n-2*i elements from n-i elements)

Comment hidden because of low score. Click to expand.
0
of 0 vote

In a board of 2 x N (2 rows and N cols) tiles, N - 2 x 1 tiles can be placed.
Therefore each of N tiles has an option of being placed Horizontal(0) or Vertical(1): Orientation and a choice of position.
The solution is split into solving Orientation for each tile and then its positions.

Deciding Orientation:
Choose 0 or 1 for each tiles, therefore pow(2,N) possibilities. For ex: 100 - place first tile vertical and next two tiles horizontal

But there are two restrictions to this approach
Restriction:1) There cannot be odd number of Horizontal tiles as it creates a horizontal space that can be filled only by another horizontal tile.(applicable for a board of 2 rows and N cols - for N x 2 board vice versa with Vertical applies)
So choose 0 or 1 for each tile from 1 to n-1.There are pow(2,n-1) possibilities and decide the orientation for the last tile based on the number of horizontal tiles.
If there are odd number of horizontal tiles upto n-1, then the choice for last tile is horizontal. If even number of horizontal tiles found upto n-1 then choice for the last is vertical. As there is only one orientation for the last tile, the total number of choices till now is pow(2,n-1)
Restriction:2) there should be two consecutive Horizontal tiles so that they can placed one below the other. Choice of 010 is physically invalid in the board as the arrangement will become either 001 or 100. In other words horizontal should be followed by horizontal. So from the pow(2,n-1) possibilities, some of the possibilites should be reduced

Summing up above two, there should be even number of tiles and horizontal tiles should be paired next to each other (that is 00 in choice)

For ex:
possibilities of placeing 3 - 2x 1 tiles in a 2 x 3 board
001
010 - invalid (when placed in the board will become 100 or 001)
011 - invalid (odd number of horizontal)
100
101 - invalid (odd number of horizontal)
110 - invalid (odd number of horizontal)
111
only 3 possiblities out of pow(2,3-1) = 4 possibilities (or out of 8 possibilties for 3 tiles as shown above)

Position:
for example if we choose the arrangement 100, three tiles A,B,C can be arranged 3! ways
Similarly for 001 and 111.

So there are 3 * 3! = 18 possible arrangements in the board.

Comment hidden because of low score. Click to expand.
0
of 0 vote

This is more like a math problem, you can come up with a closed math formula. As explained above, it's like getting # of possible pattern of V(vertical) and H(horizontal) letters where #V + (2*#H) = N. So it will be Sigma(i=0,2,..,N) (((N-i)/2) + i))! / (i! ((n-i)/2)!) when N is even, or Signa(i=1,3,..,N) (same) when odd.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.