Uber Interview QuestionSoftware Developers
- 1of 1 vote
Each test file starts with an integer ‘t’ - the number of testcases.
In each of the next ‘t’ lines, you are given a string of ‘n’ characters [ either ‘(‘ or ’)’ or ‘*’ ].
Your task is to find the number of distinct balanced parentheses expressions you can make by replacing the ‘*’ with either ‘(‘ or ‘)’ or removing the ‘*’
Note : You have to replace each ‘*’ with one of ‘(‘ or ‘)’ or remove it. If removed, assume the string has reduced by 1 character.
Duplicate strings are not allowed. The final expressions to be counted have to be distinct
As the answer may be large, please output it modulo 1000000007 (10^9+7)
Output one integer per line corresponding to each testcase.
1 <= t <= 20
1 <= n <= 100
0 <= Number of ‘*’ in the input string <= min(n,10)
The five possible valid solutions are for the first input are :
The nine possible valid solutions are for the second input are :
Interview Type: Written Test