Google Coding Interview Questions

In this article, we will be discussing Google Coding Interview Questions with their solutions.

ARRAYS

Sum of Two Values

Problem Statement: You are given an array of integers and a value, the task is to determine if there exist any two integers in the array whose sum is equal to the given value.

Solution:

bool find_sum_of_two(vector<int>& A, int val) {   unordered_set<int> found_values;   for (int& a : A) {     if (found_values.find(val - a) != found_values.end()) {       return true;     }     found_values.insert(a);   }   return false; } int main() {   vector<int> v = {5, 7, 1, 2, 8, 4, 3};   vector<int> test = {3, 20, 1, 2, 7};   for(int i=0; i<test.size(); i++){     bool output = find_sum_of_two(v, test[i]);     cout << "find_sum_of_two(v, " << test[i] << ") = " << (output ? "true" : "false") << endl;   }   return 0; }

Move Zeros to the Left

Problem Statement: The task is to move all zeros to the left of an array and hence, maintaining its order.

Solution:

void move_zeros_to_left(int A[], int n) {       if (n < 1) return;      int write_index = n - 1;   int read_index = n - 1;   while(read_index >= 0) {     if(A[read_index] != 0) {       A[write_index] = A[read_index];       write_index--;     }     read_index--;   }   while(write_index >= 0) {     A[write_index] = 0;     write_index--;   } } int main() {   int v[] = {1, 10, 20, 0, 59, 63, 0, 88, 0};   int n = sizeof(v) / sizeof(v[0]);   cout << "Original Array" <<endl;      for(int x=0 ; x<n; x++) {     cout << v[x];     cout << ", ";   }        move_zeros_to_left(v, n);      cout << endl<< "After Moving Zeroes to Left"<< endl;   for(int i=0 ; i<n; i++) {     cout << v[i];     cout << ", ";   }   }

​STRINGS

String Segmentation

Problem Statement:You are given a dictionary of words alongwith an input string. The task is to tell whether the input string can be completely segmented into dictionary words.

Solution:

bool can_segment_string(string s, unordered_set <string> & dictonary) {   for (int i = 1; i <= s.length(); ++i) {     string first = s.substr(0, i);     if (dictonary.find(first) != dictonary.end()) {       string second = s.substr(i);       if (second.empty() || dictonary.find(second) != dictonary.end() || can_segment_string(second, dictonary)) {         return true;       }     }   }   return false; } int main() {   string s = "hellonow";   unordered_set <string> dictonary = { "hello", "hell", "on", "now" };   if (can_segment_string(s, dictonary))     cout << "String Can be Segmented" << endl;   else     cout << endl << "String Can NOT be Segmented" << endl;   return 0; }

Longest Repeating Subsequence

For this problem, you can navigate through the link given below providing you all with the problem statement alongwith its solution.

Longest Repeating Subsequence Problem

TREES

Mirror Binary Trees

Problem Statement: You are given the root node of a binary tree, the task is to swap the 'left' and 'right' children for each node.

Solution:

void mirror_tree(BinaryTreeNode* root) {   if (root == nullptr) {     return;   }   // We will do a post-order traversal of the binary tree.   if (root->left != nullptr) {     mirror_tree(root->left);   }   if (root->right != nullptr) {     mirror_tree(root->right);   }   // Let's swap the left and right nodes at current level.   BinaryTreeNode* temp = root->left;   root->left = root->right;   root->right = temp; } int main(int argc, char* argv[]) {   BinaryTreeNode* root = create_random_BST(15);   display_level_order(root);   mirror_tree(root);   cout << endl << "Mirrored tree = " << endl;   display_level_order(root); }

 

To check whether two Binary Trees are identical or not

Problem Statement: You are given the roots of two binary trees, the task is to determine if these given trees are identical or not.

Solution: 

bool are_identical(   BinaryTreeNode* root1,   BinaryTreeNode* root2) {   if (root1 == nullptr && root2 == nullptr) {     return true;   }      if (root1 != nullptr && root2 != nullptr) {     return ((root1->data == root2->data) &&             are_identical(root1->left, root2->left) &&             are_identical(root1->right, root2->right));   }   return false; } int main() {   BinaryTreeNode *root1 = new BinaryTreeNode(100);   insert_bst(root1, 50);   insert_bst(root1, 200);   insert_bst(root1, 25);   insert_bst(root1, 125);   insert_bst(root1, 350);   display_level_order(root1);      BinaryTreeNode *root2 = create_random_BST(15);   display_level_order(root2);      // Try changing the roots being passed   if(are_identical(root1, root2)) {     cout<< " the trees are identical" << endl;   } else {     cout<< "the trees are not identical" << endl;   } }

​

The various other problem asked in Google Interview are discussed below under the following links for better understanding.

Check for Duplicate SubTree

Connect Nodes at Same Level

Convert Binary Tree to Mirror Tree

Linked Lists

Delete Node with Given Key

Problem Statement: You are given the head of a linked list and a key. The task is to you have to delete the node that contains this given key.

Solution:

LinkedListNode* delete_node(     LinkedListNode* head,     int key) {   LinkedListNode* prev = nullptr;   LinkedListNode* current = head;   while (current != nullptr) {     if (current->data == key) {       if(current == head){           head = head->next;           delete current;           current = head;         }       else{         prev->next = current->next;         delete current;         current = prev->next;       }     }    else{        prev = current;       current = current->next;      }   }   // key not found in list   if (current == nullptr) {     return head;   }      return head; } int main(int argc, char* argv[]) {   LinkedListNode* list_head = nullptr;   list_head = LinkedList::create_random_list(10);   printf("Original: ");   LinkedList::display(list_head);      vector<int> lst = LinkedList::to_list(list_head);   printf("\nDeleting %d",lst.at(5));   list_head = delete_node(list_head, lst.at(5));   printf("\nAfter Delete Node:");   LinkedList::display(list_head);   printf("\nDeleting (Non-Existing) %d", 101);   list_head = delete_node(list_head, 101);   printf("\nAfter Delete Node:");   LinkedList::display(list_head);   printf("\nDeleting 1st node:%d", lst.at(0));   list_head = delete_node(list_head, lst.at(0));   printf("\nAfter Delete 1st Node:");   LinkedList::display(list_head);   lst = LinkedList::to_list(list_head);   printf("\nDeleting last node: %d" , lst.at(lst.size() - 1));   list_head = delete_node(list_head, lst.at(lst.size() - 1));   printf("\nAfter Delete last Node:");   LinkedList::display(list_head); }

Graphs

Minimum Spanning Tree

Problem Statement: The task is to find the minimum spanning tree of a connected, undirected graph given with weighted edges.

Solution: 

#include <iostream> #include <vector> using namespace std; class vertex { private:   int id;   bool visited; public:   vertex(int id, bool visited) {     this->id = id;     this->visited = visited;   }   int getId() {     return id;   }   void setId(int id) {     this->id = id;   }   bool isVisited() {     return visited;   }   void setVisited(bool visited) {     this->visited = visited;   } }; class edge { private:   int weight;   bool visited;   vertex* src;   vertex* dest; public:   edge(int weight, bool visited, vertex* src, vertex* dest){     this->weight = weight;     this->visited = visited;     this->src = src;     this->dest = dest;   }   int getWeight() const {     return weight;   }   void setWeight(int weight) {     this->weight = weight;   }      bool isVisited() const {     return visited;   }   void setVisited(bool visited) {     this->visited = visited;   }   vertex* getSrc() const {     return src;   }   void setSrc(vertex* src) {     this->src = src;   }   vertex* getDest() const {     return dest;   }   void setDest(vertex* dest) {     this->dest = dest;   } }; class graph { private:   vector<vertex*> g;    //vertices   vector<edge*> e;      //edges public:   int find_min_spanning_tree(){          //TODO: Write - Your - Code   }      const vector<vertex*>& getG() const {     return g;   }   void setG(const vector<vertex*>& g) {     this->g = g;   }   const vector<edge*>& getE() const {     return e;   }   void setE(const vector<edge*>& e) {     this->e = e;   }   // This method returns the vertex with a given id if it   // already exists in the graph, returns NULL otherwise   vertex* vertex_exists(int id) {     for (int i = 0; i < this->g.size(); i++) {       if (g[i]->getId() == id) {         return g[i];       }     }     return nullptr;   }   string print_graph() {     string result = "";     for (int i = 0; i < g.size(); i++) {       cout<<g[i]->getId()<< ' ' <<g[i]->isVisited()<< endl;     }     cout << endl;     for (int i = 0; i < e.size(); i++) {       result += "[" + std::to_string(e[i]->getSrc()->getId()) + "->" + std::to_string(e[i]->getDest()->getId()) + "],";       cout << e[i]->getSrc()->getId() << "->"           << e[i]->getDest()->getId() << "["           << e[i]->getWeight() << ", "           << e[i]->isVisited() << "]  ";     }     cout << endl << endl;     return result;   }      // This method generates the graph with v vertices   // and e edges   void generate_graph(int vertices,       vector< vector<int> > edges) {     // create vertices     for (int i = 0; i < vertices; i++) {       vertex* v = new vertex(i + 1, false);       this->g.push_back(v);     }     // create edges     for (int i = 0; i < edges.size(); i++) {       vertex* src = vertex_exists(edges[i][1]);       vertex* dest = vertex_exists(edges[i][2]);       edge* e = new edge(edges[i][0], false, src, dest);       this->e.push_back(e);     }   } };

Happy Learning!!