SDE - 1

Given two sorted arrays 'a' and 'b' of size 'n' and 'm' respectively.

Find the median of the two sorted arrays.

Median is defined as the middle value of a sorted list of numbers. In case the length of list is even, median is the average of the two middle elements.

The expected time complexity is O(min(logn, logm)), where 'n' and 'm' are the sizes of arrays 'a' and 'b', respectively, and the expected space complexity is O(1).

Example:

Input: 'a' = [2, 4, 6] and 'b' = [1, 3, 5]

Output: 3.5

Explanation: The array after merging 'a' and 'b' will be { 1, 2, 3, 4, 5, 6 }. Here two medians are 3 and 4. So the median will be the average of 3 and 4, which is 3.5.

You are given the first term (A), the common ratio (R) and an integer N. Your task is to find the Nth term of the GP series.

The general form of a GP(Geometric Progression) series is A, A(R), A(R^2), A*(R^3) and so on where A is the first term of GP series

Note :

As the answer can be large enough, return the answer modulo 10^9 + 7.

You are given two binary trees with 'n' and 'm' nodes respectively.

You need to return true if the two trees are identical. Otherwise, return false.

Example:

For the trees given below:- 

The given trees are identical as:-
1. The number of nodes in both trees is the same. 
2. The number of edges in both trees is the same. 
3. The data for root for both the trees is the same i.e 5. 
4. The data of root -> left (root’s left child) for both the trees is the same i.e 2.
5. The data of root -> right (root’s right child) for both the trees is the same i.e 3.
6. The data of root -> right -> left ( left child of root’s right child) for both the trees is the same i.e 6.
7. Nodes with data 2 and 6 are the leaf nodes for both the binary trees. 

You have been given string 'S' of length 'N' that may contain duplicate alphabets. Your task is to return the count of distinct subsequences of it.

For example:

For the given string “deed” :
The possible subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“d”}, {“dd”}, {“ed”}, {“ded”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}.

As, {“d”}, {“e”}, {“de”}, {“ed”} and {“ded”} are repeated. 

The distinct subsequences are {“”}, {“d”}, {“e”}, {“de”}, {“ee”}, {“dee”}, {“dd”}, {“ed”}, {“ded”}, {“eed”} and {“deed”}

Thus, the output will be 11. 

Note:

As the answer can be large, return your answer modulo 10^9  + 7.  

What do you expect from this opportunity?

What are your future plans?

What are your weaknesses?

What do you know about the work culture here?