Google Interview: Arrangement of Blocks

Question

You are given N blocks of height 1…N. In how many ways can you arrange these blocks in a row such that when viewed from left you see only L blocks (rest are hidden by taller blocks) and when seen from right you see only R blocks? Example given N=3, L=2, R=1 there is only one arrangement {2, 1, 3} while for N=3, L=2, R=2 there are two ways {1, 3, 2} and {2, 3, 1}.

How should we solve this problem by programming? Any efficient ways?

Answer 1

This is a counting problem, not a construction problem, so we can approach it using recursion. Since the problem has two natural parts, looking from the left and looking from the right, break it up and solve for just one part first.

Let b(N, L, R) be the number of solutions, and let f(N, L) be the number of arrangements of N blocks so that L are visible from the left. First think about f because it's easier.

APPROACH 1

Let's get the initial conditions and then go for recursion. If all are to be visible, then they must be ordered increasingly, so

f(N, N) = 1 

If there are suppose to be more visible blocks than available blocks, then nothing we can do, so

f(N, M) = 0 if N < M 

If only one block should be visible, then put the largest first and then the others can follow in any order, so

f(N,1) = (N-1)! 

Finally, for the recursion, think about the position of the tallest block, say N is in the kth spot from the left. Then choose the blocks to come before it in (N-1 choose k-1) ways, arrange those blocks so that exactly L-1 are visible from the left, and order the N-k blocks behind N it in any you like, giving:

f(N, L) = sum_{1<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)!  

In fact, since f(x-1,L-1) = 0 for x<L, we may as well start k at L instead of 1:

f(N, L) = sum_{L<=k<=N} (N-1 choose k-1) * f(k-1, L-1) * (N-k)!  

Right, so now that the easier bit is understood, let's use f to solve for the harder bit b. Again, use recursion based on the position of the tallest block, again say N is in position k from the left. As before, choose the blocks before it in N-1 choose k-1 ways, but now think about each side of that block separately. For the k-1 blocks left of N, make sure that exactly L-1 of them are visible. For the N-k blocks right of N, make sure that R-1 are visible and then reverse the order you would get from f. Therefore the answer is:

b(N,L,R) = sum_{1<=k<=N}  (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1) 

where f is completely worked out above. Again, many terms will be zero, so we only want to take k such that k-1 >= L-1 and N-k >= R-1 to get

b(N,L,R) = sum_{L <= k <= N-R+1}  (N-1 choose k-1) * f(k-1, L-1) * f(N-k, R-1) 

---

APPROACH 2

I thought about this problem again and found a somewhat nicer approach that avoids the summation.

If you work the problem the opposite way, that is think of adding the smallest block instead of the largest block, then the recurrence for f becomes much simpler. In this case, with the same initial conditions, the recurrence is

f(N,L) = f(N-1,L-1) + (N-1) * f(N-1,L) 

where the first term, f(N-1,L-1), comes from placing the smallest block in the leftmost position, thereby adding one more visible block (hence L decreases to L-1), and the second term, (N-1) * f(N-1,L), accounts for putting the smallest block in any of the N-1 non-front positions, in which case it is not visible (hence L stays fixed).

This recursion has the advantage of always decreasing N, though it makes it more difficult to see some formulas, for example f(N,N-1) = (N choose 2). This formula is fairly easy to show from the previous formula, though I'm not certain how to derive it nicely from this simpler recurrence.

Now, to get back to the original problem and solve for b, we can also take a different approach. Instead of the summation before, think of the visible blocks as coming in packets, so that if a block is visible from the left, then its packet consists of all blocks right of it and in front of the next block visible from the left, and similarly if a block is visible from the right then its packet contains all blocks left of it until the next block visible from the right. Do this for all but the tallest block. This makes for L+R packets. Given the packets, you can move one from the left side to the right side simply by reversing the order of the blocks. Therefore the general case b(N,L,R) actually reduces to solving the case b(N,L,1) = f(N,L) and then choosing which of the packets to put on the left and which on the right. Therefore we have

b(N,L,R) = (L+R choose L) * f(N,L+R) 

Again, this reformulation has some advantages over the previous version. Putting these latter two formulas together, it's much easier to see the complexity of the overall problem. However, I still prefer the first approach for constructing solutions, though perhaps others will disagree. All in all it just goes to show there's more than one good way to approach the problem.

---

What's with the Stirling numbers?

As Jason points out, the f(N,L) numbers are precisely the (unsigned) Stirling numbers of the first kind. One can see this immediately from the recursive formulas for each. However, it's always nice to be able to see it directly, so here goes.

The (unsigned) Stirling numbers of the First Kind, denoted S(N,L) count the number of permutations of N into L cycles. Given a permutation written in cycle notation, we write the permutation in canonical form by beginning the cycle with the largest number in that cycle and then ordering the cycles increasingly by the first number of the cycle. For example, the permutation

(2 6) (5 1 4) (3 7) 

would be written in canonical form as

(5 1 4) (6 2) (7 3) 

Now drop the parentheses and notice that if these are the heights of the blocks, then the number of visible blocks from the left is exactly the number of cycles! This is because the first number of each cycle blocks all other numbers in the cycle, and the first number of each successive cycle is visible behind the previous cycle. Hence this problem is really just a sneaky way to ask you to find a formula for Stirling numbers.

Answer 2

well, just as an empirical solution for small N:

blocks.py:

import itertools from collections import defaultdict  def countPermutation(p):     n = 0     max = 0     for block in p:         if block > max:             n += 1             max = block     return n  def countBlocks(n):     count = defaultdict(int)     for p in itertools.permutations(range(1,n+1)):         fwd = countPermutation(p)         rev = countPermutation(reversed(p))         count[(fwd,rev)] += 1     return count  def printCount(count, n, places):     for i in range(1,n+1):         for j in range(1,n+1):             c = count[(i,j)]             if c > 0:                 print "%*d" % (places, count[(i,j)]),             else:                 print " " * places ,         print  def countAndPrint(nmax, places):     for n in range(1,nmax+1):         printCount(countBlocks(n), n, places)         print 

and sample output:

blocks.countAndPrint(10)      1              1      1              1      1      1      2      1              2      3      1      2      6      3      3      3      1              6     11      6      1      6     22     18      4     11     18      6      6      4      1             24     50     35     10      1     24    100    105     40      5     50    105     60     10     35     40     10     10      5      1            120    274    225     85     15      1    120    548    675    340     75      6    274    675    510    150     15    225    340    150     20     85     75     15     15      6      1            720   1764   1624    735    175     21      1    720   3528   4872   2940    875    126      7   1764   4872   4410   1750    315     21   1624   2940   1750    420     35    735    875    315     35    175    126     21     21      7      1           5040  13068  13132   6769   1960    322     28      1   5040  26136  39396  27076   9800   1932    196      8  13068  39396  40614  19600   4830    588     28  13132  27076  19600   6440    980     56   6769   9800   4830    980     70   1960   1932    588     56    322    196     28     28      8      1          40320 109584 118124  67284  22449   4536    546     36      1  40320 219168 354372 269136 112245  27216   3822    288      9 109584 354372 403704 224490  68040  11466   1008     36 118124 269136 224490  90720  19110   2016     84  67284 112245  68040  19110   2520    126  22449  27216  11466   2016    126   4536   3822   1008     84    546    288     36     36      9      1 

You'll note a few obvious (well, mostly obvious) things from the problem statement:

• the total # of permutations is always N!
• with the exception of N=1, there is no solution for L,R = (1,1): if a count in one direction is 1, then it implies the tallest block is on that end of the stack, so the count in the other direction has to be >= 2
• the situation is symmetric (reverse each permutation and you reverse the L,R count)
• if p is a permutation of N-1 blocks and has count (Lp,Rp), then the N permutations of block N inserted in each possible spot can have a count ranging from L = 1 to Lp+1, and R = 1 to Rp + 1.

From the empirical output:

• the leftmost column or topmost row (where L = 1 or R = 1) with N blocks is the sum of the rows/columns with N-1 blocks: i.e. in @PengOne's notation,

  b(N,1,R) = sum(b(N-1,k,R-1) for k = 1 to N-R+1

• Each diagonal is a row of Pascal's triangle, times a constant factor K for that diagonal -- I can't prove this, but I'm sure someone can -- i.e.:

  b(N,L,R) = K * (L+R-2 choose L-1) where K = b(N,1,L+R-1)

So the computational complexity of computing b(N,L,R) is the same as the computational complexity of computing b(N,1,L+R-1) which is the first column (or row) in each triangle.

This observation is probably 95% of the way towards an explicit solution (the other 5% I'm sure involves standard combinatoric identities, I'm not too familiar with those).

---

A quick check with the Online Encyclopedia of Integer Sequences shows that b(N,1,R) appears to be OEIS sequence A094638:

A094638 Triangle read by rows: T(n,k) =|s(n,n+1-k)|, where s(n,k) are the signed Stirling numbers of the first kind (1<=k<=n; in other words, the unsigned Stirling numbers of the first kind in reverse order). 1, 1, 1, 1, 3, 2, 1, 6, 11, 6, 1, 10, 35, 50, 24, 1, 15, 85, 225, 274, 120, 1, 21, 175, 735, 1624, 1764, 720, 1, 28, 322, 1960, 6769, 13132, 13068, 5040, 1, 36, 546, 4536, 22449, 67284, 118124, 109584, 40320, 1, 45, 870, 9450, 63273, 269325, 723680, 1172700

As far as how to efficiently compute the Stirling numbers of the first kind, I'm not sure; Wikipedia gives an explicit formula but it looks like a nasty sum. This question (computing Stirling #s of the first kind) shows up on MathOverflow and it looks like O(n^2), as PengOne hypothesizes.