Uber | OA Coding Questions and Solutions | Set - 21 | 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

Q1. Given two strings s and t. Count the number of occurence of t in s as follows. Length of t is 3, increment count when t == s[i]s[i+2]s[i+4]
e.g s = aabbcc , t = abc . output = 2.
Q2. Broken keyboard on a phone. Only some keys are functional, Given list of words find which words can be typed on this phone.
Q3. Rotate matrix k times while keeping the elements on both diagonals fixed.
Q4. Given two arrays a and b and list of queries. Return the values of get query in an array.
Queries are of two types:
0. update [type, index of element in a, value]. Update the element in a by given value

 

1. get [type, sum]. Return the number of ways a[i] + b[j] == sum where 0<=i < len(a) and 0<= j < len(b)

 

e.g a = [1,2,3] , b = [4,5]
queries = [[1,6], [0, 1, 2], [1,8]]
result = [2, 2]
for query 1, 6 can come in 2 ways, 1 + 5 and 2 + 4
for query 2 -> update a[1] += 2 , so a becomes [1,4,3]
for query 3, 8 can come in 2 ways now as well. 4 + 4 and 5 + 3

 

1 <= a.length < 10^5
1 <= b.length< 10^4

Answer 2

Q1,


static int count(String a, String b)
{
int m = a.length();
int n = b.length();


// Create a table to store
// results of sub-problems
int lookup[][] = new int[m + 1][n + 1];

// If first string is empty
for (int i = 0; i <= n; ++i)
    lookup[0][i] = 0;

// If second string is empty
for (int i = 0; i <= m; ++i)
    lookup[i][0] = 1;

// Fill lookup[][] in
// bottom up manner
for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        // If last characters are
        // same, we have two options -
        // 1. consider last characters
        //    of both strings in solution
        // 2. ignore last character
        //    of first string
        if (a.charAt(i - 1) == b.charAt(j - 1))
            lookup[i][j] = lookup[i - 1][j - 1] +
                           lookup[i - 1][j];
             
        else
            // If last character are
            // different, ignore last
            // character of first string
            lookup[i][j] = lookup[i - 1][j];
    }
}

return lookup[m][n];

}

 

 

For Q4, it looks like we can keep a counter of A. And for the query, we can iterate through b to find matches in a.

 

Complexity:

 

• O(1) for update
• O(10^4) for query