shantgk
BAN USER
Comments (3)
Reputation 15
Page:
1
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
1
of 3 vote
This problem can be efficiently solved using the modified dynamic algorithm for finding longest common sub-sequence.
The algorithm should be modified as follows:
Assume S1 is the the top row and S2 is the first column.
Then, the algorithm is allowed to move without penalty:
- diagonally if both are letters
- vertically (downwards) if '*' or '?'
- horizontally: only one step if '?' and many steps if '*'
For any other mismatch, penalize with infinity.
The strings match if there is a solution with cost less than infinity.
The cost of the algorithm is O(mn), m, n being the lenghts of S1 and S2.
The recursive algorithm mentioned here could have exponential time complexity.
Page:
1
CareerCup is the world's biggest and best source for software engineering interview preparation. See all our resources.
I think the approach is correct! Each number 1 to 7 will have probability of 3/25. 4/25 probability of having the repeat when result is outside the range!
- shantgk January 14, 2013