CareerCup

consider moving 1 in different position. When we put 1 at position 2, 3, ... n-1, it has no contribution to both view. When it is put at position 1, it add 1 to the left view and when it is put at n, it adds 1 to right view. Hence We have
F(n, L, R) = (n - 2)*F(n-1, L, R) + F(n-1, L-1, R) + F(n-1, L, R - 1)

#include<stdio.h>

int fun(int n,int L,int R)
{

if ( n <= 0 )
{
return 0;
}
else if( L > n or R > n)
{
return 0;
}
else if ( n == 1 && R == 1 && L == 1)
{
return 1;
}
else
{
return ((n-2)*fun(n-1,L,R) + fun(n-1,L-1,R) + fun(n-1,L,R-1));
}
}

int main()
{
int n = 3;
int L = 2;
int R = 2;
int ret;
ret = fun(n,L,R);
printf("\n %d \n",ret);

return 0;
}

If my solution is right then we can optimized it using dynamic programming

consider the place where you will put the block with height 1. Therefore,

F(N, L, R) = F(N-1, L-1, R) + F(N-1, L, R-1) + (N-2) F(N-1, L, R)

As this block has no contribution to L and R unless it is placed at left
most or right most.

The question just asks the number of ways that this can be arranged in not a program.

If seeing from the left causes only L blocks to be seen, the Lth block has to be the tallest block seen. So the Lth block is already chosen. Similarly from the right if only R blocks are to be chosen, the Rth block is the tallest block that can be seen. So from either end the last block seen is the tallest block(Nth block). So the number of ways this can be arranged is

(N-1) C (L-1) * (N-L) C (R-1) + (N-1) C (R-1) * (N-R) C (L-1)

int permutation(int n, int k)
{
int u = 1;
for(int i=0; i<k; i++)
{
u *= n-i;
}
return u;
}

int combination(int n, int k)
{
return permutation(n, k)/permutation(k,k);
}

int seeWaysOfTopKFromOneSide(int n, int k)
{
if (n == k)
return 1;
if (n < k)
{
return 0;
}

if (k == 1)
return 1;

int c = 0;
for(int m=0; m<n; m++)
{
c+= combination(n-1, m) * seeWaysOfTopKFromOneSide(m, k-1) * permutation(n-m, n-m);
}
return c;
}

int seeWaysOfTopKFromBothSides(int n, int l, int r)
{
int c = 0;
for(int m=0; m<n; m++)
{
c+= combination(n-1, m) * seeWaysOfTopKFromOneSide(m, l-1) * seeWaysOfTopKFromOneSide(n-m-1, r-1);
}
return c;
}

hey game did u attend any google interview?where?which pos?

have a look at technical-interview. com for more questions from google

technical-interview.com

java program for F(n, r) = n! /r! (n-r)!???????