## Amazon Interview Question

Software Engineer / Developers**Team:**SDE

**Country:**India

**Interview Type:**In-Person

for 2N braces, it can only be organized in two fashions:

(.....)(...) and (........)

In the first case, first ( and first ) meant to be a pair, second ( and second ) DOES NOT have to be a pair. so ()()() should be viewed as () ()()

In the second case, two ( ) is a pair, so ( ()() ) is valid, but not ()()()

In the first case, the first ')' can occur at i = 2, 4, .... 2N-2. For a fixed i, there are

f(i-2)*f(2n-i) cases

and for case two, f(2n-2) cases.

So f(n) = sum_{i=2, 4, ... 2N-2} ( f(i-2)*f(2n-i) ) + f(2n-2)

The solution provided by Hello World is most optimum one. We go on recursivelya dding left and right brackets to form valid strings.

We can add left brackets as long as we have left brackets remaining with us.

We can add right brackets as long as the number of right brackets remaining is > number of left brackets remaining.

When the number of right brackets and left brackets is exhausted, print the string

- hello world February 03, 2012