Uber | OA Coding Questions and Solutions | Set - 24 | 2022

Question

For proper oa or interview experiences list of all top tech companies visit :

https://oa.desiqna.in

https://interview.desiqna.in

 

 

Answer 1

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 at least one character from both the strings (p and q) is selected.

Note


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


Two ways to form aba


from p, a, from q, ba
from p, ab, from q, a
[execution time limit] 1 seconds (cpp)


[input] string p


[input] string q


[input] string r


[output] integer


[C++] Syntax Tips


// Prints help message to the console
// Returns a string
string helloWorld(string name) {
cout << "This prints to the console when you Run Tests" << endl;
return "Hello, " + name;
}

Answer 2

Solutions / Not tested as I haven't given the test but mostly will work given the constraints and details in the post .

Standard dynamic programming problem.
Use memorisation technique.
States

 

1. (i, j, k, haveChosenP, haveChosenQ) => (current index of p [INT], current index of q[INT], current index of r, [bool], bool])

 

Transitions

 

1. Move k and i by 1 always in each iteration of recursion if and only if either p[i] == r[k] and i < p.length()and make haveChosenP = true
   or
2. Move k and j by 1 always in each iteration of recursion if and only if q[j] == r[k] and j < q.length() make haveChosenQ = true
3. Skip current character in p (increment i by 1)
4. Skip current character in q (increment j. by 1)

 

Base case

 

1. if we reach end of r we return 1 only when both haveChosenP and haveChosenQ are true else return 0.
2. If we reach a condition when k is not at end of r and p and q ended return 0.

 

And update memo values accordingly.
Time and Space O(n^3) n = max length of p, q, r

Answer 3

Similar to merging 2 arrays, run 3 pointers in a,b and c.
Use HashMap to store intermediate results

 

int getCount(String a, String b, String c) {
  return merge(a.toCharArray(), 0, b.toCharArray(), 0, c.toCharArray(), 0, new HashMap<>());
}

int merge(char[] a, int i, char[] b, int j, char c[], int k, Map<String, Integer> map) {
        if (k >= c.length) return 1;
        if (i >= a.length && j >= b.length)
            return 0;
            
        String key = i + "," + j + "," + k;
        if (map.containsKey(key)) {
            return map.get(key);
        }
        
        int count = 0;
        // Matches with character in a
        if (i<a.length && a[i] == c[k])
            count += merge(a, i+1, b, j, c, k+1, map);
        // Matches with character in b    
        if (j<b.length && b[j] == c[k])
            count += merge(a, i, b, j+1, c, k+1, map);
        // Matches with neither a or b    
        count += merge(a,i+1,b,j+1,c,k, map);
        map.put(key, count);
        return count;
    }