## Amazon Interview Question

SDE1s**Country:**India

**Interview Type:**Phone Interview

My idea is to draw a diagonal and divide the polygon

```
NonIntersectingDiagonals(N, K)
{
totalSolutions=0;
if(K==1) return N*(N-3)/2;
if(N<4) return 0;
for(int i=3;i<=N-1;i++)
{
for(int j=0;j<=K;j++)
{
totalSolutions += NonIntersectingDiagonals(i,j)*NonIntersectingDiagonals(N-i+2, K-j);
}
}
return totalSolutions*N;
}
```

- SK August 24, 2014