## scylla

BAN USER- 1of 1 vote

AnswersEach test file starts with an integer ‘t’ - the number of testcases.

- scylla in India

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.

Constraints :

1 <= t <= 20

1 <= n <= 100

0 <= Number of ‘*’ in the input string <= min(n,10)

Sample Input:

2

(*(*)*)

*(*(**)*

Sample Output

5

9

Explanation

The five possible valid solutions are for the first input are :

((()))

()(())

()()()

(())()

(())

The nine possible valid solutions are for the second input are :

(((())))

(()(()))

(()()())

(()())

((()))

()(())

()()()

()()

(())| Report Duplicate | Flag | PURGE

Uber Software Developer Algorithm - -1of 1 vote

Answershow many elements can be sorted in theta(log n) time using heap sort ?

- scylla in India| Report Duplicate | Flag | PURGE

Algorithm

suppose you are comparing the numbers in pairs so you get a max of the two for each pair proceeding like this save the max and min at every step... you will need n-1 comparisons to get the max continuing in same manner by comparing winners at each stage. Since you saved the min values in first iteration you have saved n/2 comparisons, second now the min value can be one from the numbers that were left out when we were searching for max so that counts another logn comparisons so in all you will have

n-1+n/2+logn or 3n/2+logn-1 comparisons in best case

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window

i missed the i and j condition, yes it can be solved in a single pass in O(n) starting from end and keeping track of the diff and max values...

- scylla April 09, 2013suppose the array is A = {1,3,45,6,9}

here 9>6 so initialize diff = 3 and i = 3, j = 4, max = 9 and maxID = 4

next comparing A[2] with max as it's larger update maxID = 2, max = 45

again A[1] < max and (max - A[1]) > diff so updating diff = 42 , i = 1, j =maxID

again A[0] < max and (max - A[0]) > diff so updating diff = 43, j = maxID and i = 0;

so i=0 and j=2 gives the solution in single linear scan