Count number of ways to construct binary search tree with n elements
The number of trees can be expressed in the closed form \$\frac{\binom{2n}{n}}{n+1}\$, and due to \$\binom{2n}{n} = \frac{4n - 6}{n} \binom{2(n-1)}{n-1}\$ the result is computed in linear time.

I would not ask such question in face-to-face interview (unless the position requires in-depth knowledge of combinatoric and graph theory).