Moksh_grover's blog

By Moksh_grover, history, 5 weeks ago, In English

Problem Statement

Given three strings p, q, r. Count the possible number of ways to create string r using string p and string q such that,the order of the selected characters in all the strings is preserved and atleast one characters from both the string is selected.

Constraint

  • Strings will have max length 100
  • They will consist of lowercase english alphabets.
  • Return the answer modulo 10^9+7

Sample Test Case

  • p :"ab"
  • q :"ba"
  • r :"aba"

Output : 2

Explanation

Two ways to form aba :
1. from p 'a' ,from q 'ba'
2. from p 'ab' ,from q 'a'

This problem was asked in recent coding rounds .Can somebody help me with the solution?

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
5 weeks ago, # |
Rev. 7   Vote: I like it -11 Vote: I do not like it

I think this should work.

mod = 10**9 + 7
p, q, r = input().strip().split()
cache = {}
# i tracks the current position in string p
# j tracks the current position in string q
# r tracks the current position in string r
def dp(i, j, k, pickedP, pickedQ):
    if k == len(r):
        # Atleast 1 character from each string constraint.
        if pickedP and pickedQ:
            return 1
        return 0
    if (i, j, k, pickedP, pickedQ) in cache:
        return cache[(i, j, k, pickedP, pickedQ)]
    res = 0
    if i < len(p):
        if p[i] == r[k]:
            res += dp(i + 1, j, k + 1, True, pickedQ)
        else:
            res += dp(i + 1, j, k, pickedP, pickedQ)
    if j < len(q):
        if q[j] == r[k]:
            res += dp(i, j + 1, k + 1, pickedP, True)
        else:
            res += dp(i, j + 1, k, pickedP, pickedQ)
    res %= mod
    cache[(i, j, k, pickedP, pickedQ)] = res
    return res

print(dp(0, 0, 0, False, False))
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

an approach similar to the classic 'Interleaving Strings' problem should work

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

why so many uber question ? Have they started to gain new markets by the way following all the Uber interview questions made one thing clear to me.i would n't be able to qualify it .

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    These questions are from the on-campus uber paper. They're selecting freshers.

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I haven't tested it yet, but this will do. This solution is in O(n^4). You can modify it a bit using 2d fenwick tree or other data structures to make the solution runs in O(n^3 log^2(n)).

Spoiler
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it