15 days ago

John 850

Hyderabad

Question 1

Find Extra Letter

Problem Statement

You are given a function: char FindExtraLetter(string A, string B, int N);

The function accepts two strings 'A' and 'B' of size 'N' and 'N' + 1 respectively, if we remove one character from 'B' then 'B' becomes the permutation of 'A'. Your task is to return that character.

Example:

Input:

A="cocubes", B="ocucybse", N = 7

Output:

y

Explanation:

If we remove character 'y' from B then B becomes "ocucbse" which is a permutation of A ("cocubes").

The custom input format of the above case:

5

cocubes

ocucybse

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N + 1')

Sample input

A = "abcdefghij", B = "jihgfedkcba", N = 10

Sample Output

k

The custom input format for the above case:

10

abcdefghij

jihgfedkcba

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N+1')

Problem Statement

You are given a function:

char findExtraLetter(string A, string B, int N);

The function accepts two strings *A' and 'B' of size 'N' and 'N'+1 respectively. If we remove one character from 'B', then '8' becomes the permutation of 'A'. Your task is to return that

character.

Example:

Input:

A- "cocubes*, B= "ocucybse", N = 7

Output:

Explanation:

If we remove character 'y' from | Y then B becomes "ocucbse" which is a permutation of A ("cocubes"),

The custom input format for the above case:

cocubes

ocucybse

(The first line represents 'N', the second line represents the string 'A' and the third line represents the string 'B' which is of size 'N+1")

Sample input

A

"abcdefghig", B - "jingfedkeba", N - 10

Sample Output

1560

k

The custom input format for the above case:

10

abodefghij

jihgfedkeba

(The first line represents 'N', the second line represents the string *A' and the third line

represents the string 'B' which is of size 'N+1')

Question 2

Leaf Nodes At Same Level

Problem Statement

A binary tree is represented by the following structure:

struct TreeNode
{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
};

Implement the following function:

int LeafNodesLevel(struct TreeNode* root);

The function accepts the root node of a binary tree 'root' as its argument. Implement the function to find the sum of leaf nodes at same level and return the product of all the sums.

Assumption:

• Level of input tree is between D and 2D

Note:

• If the input tree is NULL (None in case of Python), then return D
• If all leaf nodes are at the same level then return the sum of leaf nodes

Example:

Input:

Output:

36

Explanation:

Sum of the leaf nodes at level 3 is 3 ( 1+ 2) and sum of leaf nodes at level 2 is 12 ( 5+ 4+ 3) and the product of these sums is 36 ( 3 x 12).

The custom input format for the above case:

3

9 8 7 6 5 4 3 1 2 -1 -1 -1 -1 -1 -1

(The first line represents the height of the tree, the second line represents the level order traversal of the given tree, in second line -1 represents an empty node)

Sample Input

Sample output

16

The custom input format for the above case:

2

10 9 2 1 7 -1 -1

(The first line represents the height of the tree, the second line represents the level order traversal of the given tree, in second line -1 represents an empty node)

Instructions :

• This is a template based question, DO NOT write the "main" function.
• Your code is judged by an automated system, do not write any additional welcome/greeting messages.
• "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring.
• Additional score will be given for writing optimized code both in terms of memory and execution time.

A binary tree is represented by the following structure:
struct TreeNode
{
int data;
struct TreeNade* left;
struct TreeNode* right;
};
Implement the following function:
int LeafNodesLevel (struct TreeNode* root) ;
the of a binary tree 'root' as its argument. Implement the function to find root nade The function accepts the 80209 0 N
at same level and return the product of all the sums
Assumption:
Level of input tree is between 0 and 20
Note:
If the input tree is NULL (None of in case of Python), then return D
If all leaf nodes are at the same level then return the sum of leaf nodes
Example:
Input:
root:
Output:
36
Explanation:
Sum of leaf nodes at level 3 is 3 (1 + 2) and sum of leaf nodes at level 2 is 12 (5
+ 3) and the product of these sums is 36 (3 * 12).
The custom input format for the above case:
9 8 7 6 5 4 3 1 2 -1 -1 -1 -1 -1 -1

Sample Output
16
2
The custom input format for the above case:
10 9 2 1 7 -1 -1
(The first line represents the height of the tree, the second line represents the level order
traversal of the given tree, in second line -1 represents an empty node)
Instructions:
• This is a template based question, DO NOT write the "main" function.
• Your code is judged by an automated system, do not write any additional welcome/greeting messages.
• "Save and Test" only checks for basic test cases, more rigorous cases will be used to judge your code while scoring
•Additional score will be given for writing optimized code both in terms of memory and execution time.

4 weeks ago

Lokesh 310

Bengaluru

Question 1:

Approach:

• If String X is a permutation of String Y, then each frequency of each character in X is the same as Y .
• So find the frequency of each character in strings A and B, and check for which character they are different. Output that.

PseudoCode:

char findExtraLetter(string A, string B, int N)
{
    vector<int> A1(26, 0), B1(26, 0);
    for (int i = 0; i < N; i++)
    {
        A1[int(A[i] - 'a')]++;
        B1[int(B[i] - 'a')]++;
    }
    B1[int(B[N] - 'a')]++;
    char ans;
    for (int i = 0; i < 26; i++)
    {
        if (A1[i] != B1[i])
        {
            ans = char(int(i + 'a'));
            break;
        }
    }
    return ans;
}

19 months ago

Rajat kataria • 10

Question 2: Leaf Node at Same Level

Overview

• Given a Binary tree. Implement an function to find the sum of leaf nodes at same level and return the product of all the sums.
• 20 >= Height of Binary tree (H) >= 0

Approach

• Maintain an heightSum array ( i th value of heightSum array contains the sum of leaf nodes at level i ).
• Do a dfs on the tree with height of the node passed to the dfs function.
• check if the current node is leaf node. If Yes then add the value of that node to heightSum[height], else dfs to its child node with childHeight=height+1
• Now initialize ans variable = 1 and iterate over the heightSum array and if the i*thheight contains a leaf node ( We can check it by keeping a hasLeaf boolean array, if its true, it means their is a leaf node at ithheight) multiply that **heightSum [ i ]*** to our ans.
• return ans

• Eg: Take below tree as an example with root value 10 and leaf nodes marked in green color. [graph image][1]
• Lets start dfs from root node, We pass root node and height = 0 to dfs.
• we are now at node with value 10. Check whether its a leaf node. Its not a leaf node. Now call dfs on its left and right child with height = prev_height + 1 i.e. 0 + 1 = 1
• left child of 10 i.e. 9 . Check whether its a leaf node. Its not a leaf node. Now call dfs on its left and right child with height = prev_height+1 i.e. 1+1 = 2
• left child of 9 i.e 1. Now this is a leaf node with height 2, we mark hasLeaf [ 2 ] = true and heightSum [ 2 ] += value (here 1), and heightSum [ 2 ] = 1
• right child of 9 i.e. 7. Now this is a leaf node with height 2, we mark hasLeaf [ 2 ] = true and heightSum [ 2 ] += value (here 7) i.e. { 1 + 7 } heightSum [ 2 ] = 8.
• right child of 10 i.e. 2 . Now this is a leaf node with height 1, we mark hasLeaf [ 1 ] = true and heightSum [ 1 ] += value (here 2) i.e. { 0 + 2 } heightSum [ 1 ] = 2.
• dfs ends as no more children are left
• As we are given that the maximum height of tree can be 20. Then we iterate on height from 0 to 20. Initialize ans = 1 and whenever we find hasLeaf [ height ] = true, we multiply ans with heightSum [ height ] i.e.
• For height = 1, ans = ans x heightSum [ 1 ] => ans = ans x 2 => ans = 2
• For height = 2, ans = ans x heightSum [ 2 ] => ans = ans x 8 => ans = 16
• return ans; { ans = 16 }

Complexity

• O(N) | N is the number of nodes.

Pseudo Code

void dfs(vector<int> &heightSum,vector<int>&hasLeaf,int height,TreeNode* root){
    if(root->left == NULL && root->right == NULL){     // check whether node is a leaf node
        hasLeaf[height]=1;     // *height* has a leaf node
        heightSum[height]+=root->data;   // adding value of leaf node to this height
        return;
    }
    dfs(heightSum,vis,height+1,root->left);    // dfs on left child 
    dfs(heightSum,vis,height+1,root->right);  // dfs on right child 
}

int Solution(TreeNode* Root){
    if(Root == NULL) return 0;   // returning D=0 if tree is empty
    vector<int> heightSum(20,0);
    vector<int> hasLeaf(20,0);
    dfs(heightSum,hasLeaf,0,Root);
    long long int ans=1;
    long long int mod=1e9+7;
    for(int i=0;i<20;i++){
        if(hasLeaf[i]==1)
        ans*=heightSum[i];
        ans%=mod;
    }
    return ans;
}