quzal

Google Online Coding Challenge Question 1 – Google Sydney

Google Online Challenge ID : 580708883661

Test Date : 17 – 18 April 2020

Important reminders before you start the challenge:
— You will have 45 minutes total to complete two coding questions. The challenge will be automatically submitted at the mark of 45 minutes
— Ensure you have a reliable internet connection. We recommend using one of the latest versions of Google Chrome or Firefox for a browser
— Please attempt only on one browser. Once you launch the challenge page, please do not refresh the page or close the window

For the Coding Challenge:
— Currently the tool only supports the following languages: C, C++, C#, Python and Java. We do not offer other languages such as Javascript, Ruby, Perl, Go, etc
— We are only able to offer the following versions: C 99, C++ 11, Python 3.5, Java 9, C# 6
— You can copy-paste on the same editor window (for Mac users, please use  Ctrl+C / Ctrl+V) but not allowed to copy-paste from outside the editor
— Please select the coding language you are most comfortable in, if you change the language in between the code will have to be reworked
— We highly recommend that you do not use an AZERTY keyboard as there are some character restrictions. If you are using a ‘Swiss Macbook” and “German standard”, please use ALT+8 and ALT+9 to enter “{“ and “}” respectively
— Pre-installed plugins should be disabled from the web browsers before the start of the language as this may interfere with editor functioning smoothly
— If your system shuts down abruptly, don’t panic. Your results will still be recorded
— If you run out of time, don’t worry your progress so far will be auto saved and submitted

Question 1

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; 
} 
  

int main() 
{ 
    int k=3;
    int count =0; // count of pair of leaf nodes where distance leaf nodes is less than or equal to k
    
    // creating binary tree
    Node * root = newNode(2); 
    root->left = newNode(3); 
    root->right = newNode(5); 
    root->left->left = newNode(4); 
    root->left->right = newNode(6); 
    root->right->left = newNode(1); 
    root->right->right = newNode(7); 
  
    // finding Distance between leaf nodes
    if(findDistance(root, 4, 6)<=k){
        count++;
    }

    if(findDistance(root, 4, 1)<=k){
        count++;
    }

    if(findDistance(root, 4, 7)<=k){
        count++;
    }

    if(findDistance(root, 6, 1)<=k){
        count++;
    }

    if(findDistance(root, 6, 7)<=k){
        count++;
    }

    if(findDistance(root, 1, 7)<=k){
        count++;
    }
    cout<<count;
    return 0; 
} 

Make this code Generic and Get 5 XRP in your wallet

2 thoughts on “Google Online Coding Challenge Question 1 – Google Sydney

  • Muntu
    April 21, 2020 at 4:13 pm

    Good one

    • admin
      April 28, 2020 at 12:38 pm

      Thanks Muntu

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>