Technical Interview

Tips, questions, answers and puzzles at
www.technical-interview.com

Sunday, February 28, 2010

Arangement of blocks

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}.

2 comments:

  1. There is a recurrent solution for this one.
    Let's say that F(N, L, R) is the number of arrangements which fit the stated condition.
    F(1, 1, 1) = 1 (obviously)
    F(N, L, R) = (F(N-1, L, R) * (N-2) iff L+R-1 < N) + (F(N-1, L-1, R) iff L > 1) + (F(N-1, L, R-1) iff R > 1);

    ReplyDelete
  2. @anonymous:
    functionality is not properly defined... stopping conditions of function F(_,_,_) is not comprehensive . Just saying F(1,1,1)= 1 doesn't suffice.

    ReplyDelete