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

You and your best friend leave messages for one another in your favorite places around town. But you don't want any strangers to read them, so you hide them within strings. To decode a message in a string you need to find a string subsequence of length 5 which is a palindrome - this subsequence is the code itself.

Given a string message, return the number of such subsequences within it.


Example


For message = "abcdba", the output should be
solution(message) = 2.
You can obtain such palindromes: "abcba" and "abdba".
For message = "aabccba", the output should be
solution(message) = 4.
You can obtain "abcba" 4 times with different a and c from the given string.
Input/Output


[execution time limit] 0.5 seconds (cpp)


[input] string message


The encrypted message.


Guaranteed constraints:
1 ≤ message.length ≤ 700.


[output] integer


The number of subsequence palindromes with exactly 5 letters in the given string. It's guaranteed that for the given test cases the answer always fits signed 32-bit integer type.


[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

Since length < 700

 

Choose all pairs of indices i, j such that s[i] == s[j]. and j > i + 1 in the string s.
At indexes i and j find out count of all the characters (26 alphabets ) prior to i and after j.

 

To count occurrences of all chars prior to index i use standard prefix sums.
To count occurrences of all chars post index j use standard suffix sums and precompute these 2 values.

 

The number of palindromes such that the first and fourth index of that 5 length palindrome in string s are i and j respectively will be
summation of following expression over all 26 chars.

 

int ans = 0;
for(int ch= 0; ch< 26; ch ++) {
    ans += prefix[i - 1][ch] * suffix[j +1][ch] * ( j - i - 1)
}

 

At the end answer will be summation of all the answers in the code snippet above.
Time Complexity O(N^2) space O(N) where N = length of string
Space Complexity O(N)