quzal

Google Online Coding Challenge Question 2 – Google Sydney

Google Online Challenge ID : 580708883661

Test Date : 17 – 18 April 2020

Question 2

Solution

C++

#include <iostream> 
using namespace std; 
  
// A Binary Tree Node 
struct Node 
{ 
    struct Node *left, *right; 
    int key; 
}; 
  
// function to create a new tree Node 
Node* newNode(int key) 
{ 
    Node *temp = new Node; 
    temp->key = key; 
    temp->left = temp->right = NULL; 
    return temp; 
} 
// Finding  lowest common ancestor of n1 and n2
Node* LCA(Node * root, int n1,int n2) 
{ 
   
    if (root == NULL) 
       return root; 
    if (root->key == n1 || root->key == n2) 
       return root; 
  
    Node* left = LCA(root->left, n1, n2); 
    Node* right = LCA(root->right, n1, n2); 
  
    if (left != NULL && right != NULL) 
         return root; 
    if (left != NULL) 
        return LCA(root->left, n1, n2); 
  
    return LCA(root->right, n1, n2); 
} 
  
// Returns level of key k if it is present in 
// tree, otherwise returns -1 
int findLevel(Node *root, int k, int level) 
{ 
    if(root == NULL) return -1; 
    if(root->key == k) return level; 
  
    int left = findLevel(root->left, k, level+1); 
    if (left == -1) 
       return findLevel(root->right, k, level+1); 
    return left; 
} 
  
int findDistance(Node* root, int a, int b) 
{ 

    Node* lca = LCA(root, a , b); 
  
    int d1 = findLevel(lca, a, 0); 
    int d2 = findLevel(lca, b, 0); 
  
    return d1 + d2; 
} 


// Function to find gcd of two numbers
int GCD(int n1,int n2){
    while(n1 != n2)
    {
        if(n1 > n2)
            n1 -= n2;
        else
            n2 -= n1;
    }
    return n1;
}

int main() 
{ 
 
    
    // creating binary tree
    Node * root = newNode(2); 
    root->left = newNode(12); 
    root->right = newNode(24); 
    root->left->left = newNode(11); 
    root->left->right = newNode(-1); 
    root->right->left = newNode(14); 
    root->right->right = newNode(21); 
  
    if(GCD(12,24)>GCD(14,21)){
        int diff=GCD(12,24)-GCD(14,21);
        cout<<diff;
    }else if (GCD(14,21)>GCD(12,24)){
        int diff = GCD(14,21)-GCD(12,24);
        cout<<diff;
    }

    return 0; 
} 

Make this code Generic and Get 5 XRP in your wallet

Leave a Reply

Your email address will not be published. Required fields are marked *.

*
*
You may use these <abbr title="HyperText Markup Language">HTML</abbr> tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>