Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Google Interview Questions
2.1.
What is merge sort?
2.2.
How do you convert a Queue into a Stack?
2.3.
Compare lookup operation in Trie vs Hash Table?
2.4.
Explain the key differences between the B+ tree and the B tree?
2.5.
Explain LRU cache? Also, mention the data structures used in LRU cache implementation?
2.6.
Let say we have array nums of size n that contain both positive and negative integers, we have to return all the triplets [nums[i], nums[j], nums[k]], where 1<=i,j,k<=n such that i!= j, i!= k, and j!= k, and nums[i] + nums[j] + nums[k] == 0. return all the triplets [nums[i], nums[j], nums[k]].
2.6.1.
Steps of Algorithm
2.7.
C++
2.8.
Given a doubly linked list, we have reversed the given linked list.
2.9.
Java
2.10.
The problem is to find the Equilibrium Point of an array. You are given N elements in an array, and you need to find the index such that the sum of the elements towards its left is equal to the sum of the element towards its right.
2.11.
C++
2.12.
Given an unsorted array of integers, and an integer k. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to k or not”.
2.12.1.
Steps
2.13.
Java
2.13.1.
Complexity Analysis
2.14.
Given an integer matrix of size N x M, where ‘N’ is the number of rows and ‘M’ is the number of columns, You task is to rotate all matrix elements in the clockwise direction. You will get a better understanding of the problem from the following example.
2.14.1.
Implementation
2.15.
C++
2.16.
There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N- 1’ (both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party. Your task is to find out the celebrity at the party. Print the id of the celebrity. If there is no celebrity at the party, then print -1.
2.17.
C++
2.18.
In this problem, you will be given two strings. You have to find the length of the longest substring, which is common in the two given strings. 
2.19.
C++
2.20.
What is a binary search tree, and how is it implemented?
2.21.
C++
2.22.
Count the number of Longest Palindromic Substrings.Given a string s, find the length of the longest palindromic substring of the string and also see the number of palindromic substrings of that length.
2.23.
You are given a reference or a pointer to the root of a binary search tree. Our task is to find the Lowest Common Ancestor in a Binary Search Tree.
2.24.
You have been given an array/list 'ARR' consisting of 'N' integers. Your task is to find the majority element in the array. If there is no majority element present, print no majority element. 
2.24.1.
Naive Method
2.24.2.
Algorithm
2.25.
C++
2.25.1.
Complexity
2.26.
Given a 9x9 sudoku board. Determine whether the given sudoku board is valid or not. Only the filled cells need to be validated according to the following constraints:
2.27.
C++
2.27.1.
Time complexity
2.27.2.
Space Complexity
2.28.
How do you implement a breadth-first search?
2.29.
Python
2.30.
Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently. Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with a nut to see which one is bigger/smaller.
2.31.
C++
3.
Frequently Asked Questions
3.1.
How long are Google interviews?
3.2.
Does Google hire Freshers?
3.3.
Are Google Interviews hard?
4.
Conclusion
Last Updated: May 15, 2024
Hard

Google Interview Questions and Answers

Author Rinki Deka
0 upvote

Introduction

This article will discuss the most common Google interview questions and answers that will help you prepare well for your upcoming interview. 

Google Interview Questions

Google LLC, founded in 1998 by Larry Page and Sergey Brin, is an American multinational technology firm that specializes in Internet-related services and products such as cloud computing, online advertising technologies, a search engine, software, and hardware. Google, along with Amazon, Apple, Microsoft, and Facebook, is one of the Big Five corporations in the United States Information Technology industry. 

Google Interview Questions

What is merge sort?

The merge sort algorithm employs the "divide and conquer" strategy, in which we divide the problem into subproblems and solve each one individually.

These subproblems are then combined or merged to form a complete solution.

  • By dividing the list on the middle element, the list is divided into two arrays of equal length. The list is considered sorted if the number of elements in it is either 0 or 1.
  • Each sublist is sorted individually using a recursive merge sort.
  • The sorted sublists are then combined or merged to form the final sorted list.

Psudeocode-

Declare an array Arr of length N

If N=1, Arr is already sorted

If N>1,

Left = 0, right = N-1

Find middle = (left + right)/2

Call merge_sort(Arr,left,middle) =>sort first half recursively

Call merge_sort(Arr,middle+1,right) => sort second half recursively

Call merge(Arr, left, middle, right) to merge sorted arrays in above steps.

Exit

How do you convert a Queue into a Stack?

To build a stack using queues, we'll need two queues (q1 and q2), as well as the following queue actions to imitate stack operations:

For Pushing an element E:

if q1 is empty, enqueue E to q1

if q1 is not empty, enqueue all elements from q1 to q2, then enqueue E to q1, and enqueue all elements from q2 back to q1

For popping an element:

dequeue an element from q1

As we can see, q1 is the stack's main source, while q2 is merely a helper queue that we utilise to keep the stack's anticipated order.

Compare lookup operation in Trie vs Hash Table?

  • Tries allow for ordered iteration, whereas iterating over a hash table produces a pseudorandom order determined by the hash function (the order of hash collisions is also implementation specified), which is usually useless.
     
  • Tries are faster at insertion than hash tables on average because hash tables must rebuild their index as it fills up, which is a costly operation. As a result, tries have considerably better limited worst-case time costs, which is crucial for latency-sensitive algorithms.

As a result of the aforementioned, tries to facilitate longest-prefix matching, but hashing does not. Depending on the implementation, a "closest fit" search can be as quick as an exact search.

Explain the key differences between the B+ tree and the B tree?

  •  B-trees are a sort of self-balancing tree structure used to store and retrieve large quantities of data quickly.
     
  • They are frequently confused with the Binary Search Tree, which is a close relative. The Binary Search Tree is a specific form of B-tree, despite the fact that they're both m-way search trees.
     
  • Multiple key/value pairs can be found in a node of a B-tree, which is sorted ascendingly by key order. This key/value pair is referred to as a payload.
     
  • When it comes to insert, remove, and search operations, B-trees are seen to be particularly useful because they give logarithmic O(log(n)) time complexity.
     
  • In a doubly-linked list, all leaf nodes are linked together. Only the leaf nodes store satellite data. Internal nodes solely serve as routers to the correct leaf node and store keys.
     
  • Data put on the leaf node improves the search efficiency in B+trees because we can store more keys in internal nodes, requiring us to access fewer nodes.
     

Because we just need to delete data from leaf nodes, deleting data from a B+tree is easier and faster.

In fact, B+trees are used for indexing in 99 per cent of database management systems.

Explain LRU cache? Also, mention the data structures used in LRU cache implementation?

Ans : The most frequently used data is temporarily stored in cache memory on computers. Because the retrieval procedure is so quick, it's a wonderful approach to getting the most frequently utilised data.

However, because cache memory is limited, there must be a means to govern which data must be removed from the cache in order to make room for new data. This is when the LRU cache comes into play.

It's a cache replacement algorithm that clears out the data that hasn't been used in a while to make room for fresh data.

In order to achieve this, two data structures are used:

a. Queue: A doubly-linked list is used to do this. The cache size, i.e. the total number of available frames, determines the queue's maximum size. The pages that have been used the least lately will be near the front of the queue, while the pages that have been used the most recently will be near the back.

b. Hashmap: The page number is the key, and the address of the matching queue node is the value, in a hashmap.

Head over to This link to practice LRU Cache Implementation.

Let say we have array nums of size n that contain both positive and negative integers, we have to return all the triplets [nums[i], nums[j], nums[k]], where 1<=i,j,k<=n such that i!= j, i!= k, and j!= k, and nums[i] + nums[j] + nums[k] == 0. return all the triplets [nums[i], nums[j], nums[k]].

Note: solution set must not contain duplicate triplets.

The basic approach involves running three loops and checking if the total of three elements is zero or not one by one. Print elements if the sum of the three elements is 0(zero-sum); otherwise, print not found.

Optimized approach 
As an array has both -ve and +ve numbers, firstly we sort the array. Sorted array would have -ve numbers together and +ve numbers together in increasing order. This will make it easy to search the required numbers to make a 0 sum.

Base cases after sorting:

  1. If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.
     
  2. If first element is +ve, that means there is no -ve number by which we can make a 0 triplet sum. Return empty vector of vectors.
     

In this approach, firstly, we will hash the indices of all elements in a hashMap. In case of repeated elements, the last occurence index would be stored in hashMap.

Steps of Algorithm

  1. Here also we fix a number (num[i]), by traversing the loop. But the loop traversal here for fixing numbers would leave last two indices. These last two indices would be covered by the nested loop.
     
  2. If number fixed is +ve, break there because we can't make it zero by searching after it.
     
  3. Make a nested loop to fix a number after the first fixed number. (num[j])
     
  4. To make sum 0, we would require the -ve sum of both fixed numbers. Let us say this required.
     
  5. Now, we will find the this required number in hashMap. If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet. Push it in answer vector.
     
  6. Update j to last occurence of 2nd fixed number to avoid duplicate triplets.
     
  7. Update i to last occurence of 1st fixed number to avoid duplicate triplets.
     
  8. Return answer vector.
  • C++

C++

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> threeSum(vector<int> &nums)

{

   sort(nums.begin(), nums.end()); // Sorted Array

   if (nums.size() < 3)

   { // Base Case 1

       return {};

   }

   if (nums[0] > 0)

   { // Base Case 2

       return {};

   }

   unordered_map<int, int> hashMap;

   for (int i = 0; i < nums.size(); ++i)

   { // Hashing of Indices

       hashMap[nums[i]] = i;

   }

   vector<vector<int>> answer;

   for (int i = 0; i < nums.size() - 2; ++i)

   { // Traversing the array to fix the number.

       if (nums[i] > 0)

       { // If number fixed is +ve, stop there because we can't make it zero by searching after it.

           break;

       }

       for (int j = i + 1; j < nums.size() - 1; ++j)

       {  // Fixing another number after first number

           int required = -1 * (nums[i] + nums[j]); // To make sum 0, we would require the -ve sum of both fixed numbers.

           if (hashMap.count(required) && hashMap.find(required)->second > j)

           { // If it exists in hashmap and its last occurrence index > 2nd fixed index, we found our triplet.

               answer.push_back({nums[i], nums[j], required});

           }

           j = hashMap.find(nums[j])->second; // Update j to last occurence of 2nd fixed number to avoid duplicate triplets.

       }

       i = hashMap.find(nums[i])->second; // Update i to last occurence of 1st fixed number to avoid duplicate triplets.

   }

   return answer; // Return answer vector.

}

int main()

{

   int n; // store the size of vector

   cin >> n;

   vector<int> nums(n); // vector of size n

   for (int i = 0; i < n; i++)

       cin >> nums[i];

   vector<vector<int>> ans = threeSum(nums);

   cout << "number of triplet with zero-sum: ";

   cout << ans.size() << endl;

   for (int i = 0; i < ans.size(); i++)

   {

       for (auto element : ans[i])

           cout << element << ' ';

       cout << endl;

   }

}

 Input: 

6
-1 0 1 2 -1 -4

 
Output: 

number of triplet with zero-sum: 2
-1 -1 2 
-1 0 1


Given a doubly linked list, we have reversed the given linked list.

Input:-

1<-> 2<-> 3<-> 4<->5

Output:-`

5<->4<->3<->2<->1

The simple approach for reversing the doubly linked list are: just swapping the next and prev address of nodes of its own; after that, all task gets completed, then previous of the last node with head to access the element in the reverse side then after our task is done for the reversing the Linked List.

  • Java

Java

public class ReverseDoublyLinkedList {
class Node{
int data;
Node next;
Node prev;
public Node(int data){
this.data=data;
}
}

Node head=null;
Node tail=null;
// Make a doubly Linked List
public void addNode(int data){
Node newNode=new Node(data);
if(head==null){
head=tail=newNode;
head.prev=null;
tail.next=null;
}
else{
tail.next=newNode;
newNode.prev=tail;
tail=newNode;
tail.next=null;
}
}

// Print the Doubly Linked List
public void print(){
Node curr=head;
if(curr==null){
System.out.println("The Linked List is empty !");
}
while(curr!=null){
System.out.print(curr.data+" ");
curr=curr.next;
}
}

// Function to reverse the Linked List
public void reverselist(){
Node temp=null;
Node curr=head;
// Start swapping the next and prev of nodes
while(curr!=null){
temp=curr.prev;
curr.prev=curr.next;
curr.next=temp;
curr=curr.prev;
}
// At last change the head position of Linked List to last node
if(temp!=null){
head=temp.prev;
}
}
public static void main(String[] args){
ReverseDoublyLinkedList rev=new ReverseDoublyLinkedList();
rev.addNode(2);
rev.addNode(7);
rev.addNode(1);
rev.addNode(13);
rev.addNode(17);
System.out.println("Doubly Linked List before reverse: ");
rev.print();
rev.reverselist();
System.out.println();
System.out.println("Doubly Linked List after reverse: ");
rev.print();
}
}

Output

Doubly Linked List before reverse: 
2 7 1 13 17 
Doubly Linked List after reverse: 
17 13 1 7 2 

The problem is to find the Equilibrium Point of an array. You are given N elements in an array, and you need to find the index such that the sum of the elements towards its left is equal to the sum of the element towards its right.

The naive approach to finding the Equilibrium Point of an array would be taking each element from the start of the array, and finding its left and the right sum. If both are equal, return the taken element index or perform the same steps with the next element.  

Time Complexity for finding left and right sum for one element chosen = n.

For n elements, it would take = n² time.

Optimized Approach: Two Pointers Approach

In two pointers approach, we will keep track of the left_sum and right_sum while traversing the array itself. Let us see its implementation to understand it in a better way.

  • C++

C++

#include <iostream>

using namespace std;

int equilibrium(int arr[], int n)

{

 int total_sum = 0;

 for(int i = 0; i < n; i++)

     total_sum += arr[i];

   

 int left_sum = 0;

 for(int i = 0; i < n; i++){

     int right_sum = total_sum - left_sum - arr[i];

     if(left_sum == right_sum)

        return i;

     left_sum += arr[i];

 }

 return -1;

}

int main()

{

 int arr[] = { 1, 7, 3, 6, 5, 6 };

 int arr_size = sizeof(arr) / sizeof(arr[0]);

 cout << "Equilibrium point is at index " << equilibrium(arr, arr_size) << endl;

 return 0;

}

Output

Equilibrium point is at index 3

Given an unsorted array of integers, and an integer k. The task is to find whether there exists a subarray(positive length) of the given array such that the sum of elements of the subarray equals to k or not”.

Brute Force approach: A possible approach could be to first generate all the subarrays, calculate the subarray sum and if it is equal to the given sum (i.e. the sum is equal to the given value k), return the starting and ending positions of that subarray; else return -1. This approach will work fine for both positive and negative elements in the array.

Optimized approach - Prefix Sum Technique : For an array with negative integers, A variation of the Prefix Sum technique can be used. The idea to approach the problem is if the prefix sum up to ith index is X, and the prefix sum up to jth index is Y and it is found that Y = X +k, then the required subarray is found with i as start index and j as end index. 

Steps

  • Declare a Hashmap where the key of hashmap will store the index value and the value will store the sum of elements up to that index.
     
  • Keep two variables, one to store the current sum and one to store the subarray sum.
     
  • Iterate through the array from start to end, at each iteration, update the sum variable as sum  = sum + arr[i]
     
  • If the subarray with given sum or a subarray with sum equal to k is found, then print that subarray from 0 to i
     
  • If there is any key in the hashmap that equals sum – k, then print the subarray from hashmap[sum – k] to i.
     
  • Print the sum and index in the hashmap as a key-value pair.
  • Java

Java

import java.util.HashMap;
public class Subarray
{
public static void subArraySum(int[] arr, int k)
{
int n = arr.length;
//cur_sum to keep track of cummulative sum till that point
int cur_sum = 0;

int start_point = 0; // to keep track of starting point of subarray
int end_point = -1; // to keep track of ending point

// creating a hash map whose key will be equal to the index
// and value will be equal to the sum till that index
HashMap<Integer, Integer> hm = new HashMap<>();

// Iterating the array from starting to ending position
for (int i = 0; i < n; i++)
{
/*
There are three possibilties for an element now :-

CASE 1) If the element is not present in Hashmap, simply add it.
CASE 2) If adding the current element gives the desired sub array (i.e. subarrat found between 0th and the
current position
CASE 3) If the hashmap already contains that value, means we already have the subarray, simply STOP at this point
*/

cur_sum = cur_sum + arr[i];

hm.put(cur_sum, i); // CASE 1,we are adding curr_sum as value and i as index in the hashmap

if (cur_sum - k == 0) // CASE 2
{
start_point = 0;
end_point = i;
break;
}

if (hm.containsKey(cur_sum - k)) // CASE 3
{
start_point = hm.get(cur_sum - k) + 1;
end_point = i;
break;
}

}
// if end is -1 : means we have reached end without the sum
if (end_point == -1)
{
System.out.println("No subarray with a sum equals to k in the input array");
}
else
{
System.out.println("The elements from position " + start_point + " to " + end_point + "form the required sub array");
}
}
public static void main(String[] args)
{
int[] arr1 = {10, 20, -45, 45, 60};
int k1 = 80;
subArraySum(arr1, k1);
int[] arr2 = {1, 2, 4, 15, 10};
int k2 = 30;
subArraySum(arr2, k2);
} // main method ends here

} // class ends here

Output

The elements from position 1 to 4form the required sub array
No subarray with a sum equals to k in the input array

Complexity Analysis

  • The time complexity of the above program is O(N) as we need to iterate through the array of size N once
     
  • The space complexity is O(N) because a hashmap of size N is needed.

Given an integer matrix of size N x M, where ‘N’ is the number of rows and ‘M’ is the number of columns, You task is to rotate all matrix elements in the clockwise direction. You will get a better understanding of the problem from the following example.

We are going to use loops to solve this problem. We will traverse in a spiral fashion and rotate all rings.

For rotating a single ring, follow these steps:

  1. Rotate the top row of the ring.

     
  2. Rotate the last column (on the right side) of the ring.

     
  3. Rotate the bottom row of the ring.

     
  4. Rotate the first column (on the left side) of the ring.

Implementation

Now let's look at the implementation of the above algorithm in C++, Java, and Python.

/* C++ program to rotate matrix elements */

  • C++

C++

#include <bits/stdc++.h>

# define R 3

# define C 3

using namespace std;

/* function to rotate matrix where m = R and n = C */

void rotatematrix(int m, int n, int mat[R][C]) {

   int row = 0;

   int col = 0;

   int prev;

   int curr;

   /* we will store starting row index in "row" while store starting column index in "col" */

   while (row < m && col < n) {

       if (row + 1 == m || col + 1 == n)

           break;

       /* "prev" will store the 1st element of next row */

       prev = mat[row + 1][col];

       /* Move 1st row elements from the remaining rows */

       for (int i = col; i < n; i++) {

           curr = mat[row][i];

           mat[row][i] = prev;

           prev = curr;

       }

       row++;

       /* Move last column elements from the remaining columns */

       for (int i = row; i < m; i++) {

           curr = mat[i][n-1];

           mat[i][n-1] = prev;

           prev = curr;

       }

       n--;

       /* Move last row elements from the remaining rows */

       if (row < m) {

           for (int i = n-1; i >= col; i--) {

               curr = mat[m-1][i];

               mat[m-1][i] = prev;

               prev = curr;

           }

       }

       m--;

       /* Move 1st column elements from the remaining rows */

       if (col < n) {

           for (int i = m-1; i >= row; i--) {

               curr = mat[i][col];

               mat[i][col] = prev;

               prev = curr;

           }

       }

       col++;

   }

   /* print the rotated matrix */

   for (int i=0; i<R; i++) {

       for (int j=0; j<C; j++)

           cout << mat[i][j] << " ";

       cout << endl;

   }

}

/* Main function */

int main() {

  

   /* Test case on which we are going to check our code */

   int a[R][C] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};



   /* function to rotate matrix and print the rotated matrix */

   rotatematrix(R, C, a);



   return 0;

}

Output

4 1 2 
7 5 3 
8 9 6 

There are ‘N’ people at a party. Each person has been assigned a unique id between 0 to 'N- 1’ (both inclusive). A celebrity is a person who is known to everyone but does not know anyone at the party. Your task is to find out the celebrity at the party. Print the id of the celebrity. If there is no celebrity at the party, then print -1.

Input:

MATRIX = { {0, 0, 1, 0},

           {0, 0, 1, 0},

           {0, 0, 0, 0},

           {0, 0, 1, 0} }

Output:id = 2

Explanation: The person with ID 2 does not know anyone, but everyone knows him

If for any pair (i, j)  such that ‘i’!= ‘j’, if  ‘knows(i, j)’ returns true, then it implies that the person having id ‘i’ cannot be a celebrity as it knows the person having id ‘j’. Similarly, if ‘knows(i, j)’ returns false, then it implies that the person having id ‘j’ cannot be a celebrity as it is not known by a person having id ‘i’. We can use this observation to solve this problem.

The algorithm is as follows:

  1. Create a stack and push all ids in it.
     
  2. Run a loop while there are more than one element in the stack and in each iteration do the following-:
    • Pop two elements from the stack. Let these elements be ‘id1’ and ‘id2’.
       
    • If the person with ‘id1’ knows the person with ‘id2,’ i.e. ‘knows(id1, id2)’ return true, then the person with ‘id1’ cannot be a celebrity, so push ‘id2’ in the stack.
       
    • Otherwise, if the person with ‘id1’ doesn't know the person with ‘id2,’ i.e. knows(id1, id2) return false, then the person with ‘id2’ cannot be a celebrity, so push ‘id1’ in the stack.
       
  3. Only one id remains in the stack; you need to check whether the person having this id is a celebrity or not, this can be done by running two loops. One checks whether this person is known to everyone or not, and another loop will check whether this person knows anyone or not.
     
  4. If this person is a celebrity, return his id; otherwise, return -1.

 Time complexity: O(N)

 Space complexity: O(N)

  • C++

C++

#include <bits/stdc++.h>

#include <list>

#include <stack>

using namespace std;

// Max # of persons in the party

#define N 4

bool MATRIX[N][N] = { { 0, 0, 1, 0 },{ 0, 0, 1, 0 },{ 0, 0, 0, 0 },{ 0, 0, 1, 0 } };

bool knows(int A, int B)

{

  return MATRIX[A][B];



}

int findCelebrity(int n) {

  // Create a stack and push all ids in it.

  stack<int> ids;

  for(int i = 0; i < n; i++) {

      ids.push(i);

  }

  // Finding celebrity.

  while(ids.size() > 1) {

      int id1 = ids.top();

      ids.pop();

      int id2 = ids.top();

      ids.pop();

    

      if(knows(id1, id2)) {

          // Because person with id1 can not be celebrity.

          ids.push(id2);

      }

      else {

          // Because person with id2 can not be celebrity.

          ids.push(id1);

      }

  }

  int celebrity = ids.top();

  bool knowAny = false, knownToAll = true;

  // Verify whether the celebrity knows any other person.

  for(int i = 0; i < n; i++) {

      if(knows(celebrity, i)) {

          knowAny = true;

          break;

      }

  }

  // Verify whether the celebrity is known to all the other person.

  for(int i = 0; i < n; i++) {

      if(i != celebrity and !knows(i, celebrity)) {

          knownToAll = false;

          break;

      }

  }

  if(knowAny or !knownToAll) {

      // If verificatin failed, then it means there is no celebrity at

the party.

      celebrity = -1;

  }

  return celebrity;

}

// Driver code

int main()

{

int n = 4;

int id = findCelebrity(n);

id == -1 ? cout << "No celebrity" : cout << "Celebrity ID " << id;

return 0;

}

Output:

Celebrity ID  2

In this problem, you will be given two strings. You have to find the length of the longest substring, which is common in the two given strings. 

Example

Assume the two given strings are:

s1 = “qdef”
s2 = “defq”

“q”, “d”,  “e”, “f”, “de”, “ef”, and “def” are the common substrings between s1 and s2. “def” is the longest common substring. So, the length of the longest common substring of s1 and s2 will be “3”.

Ans: The simplest approach is to generate all possible substrings of one string. Then check if each of them is a substring of the other string. This approach has a time complexity of O(n^3). n is the length of the longest input string. It is not efficient for large input sizes. It is mainly used for small instances or as a baseline for comparison.

Optimized Approach: Dynamic Programming Approach

 Create a matrix dp of size (m+1) x (n+1).
 

  • Initialize the first row and the first column of the matrix dp with zeros.
     
  • Initialize two variables: maxLength to store the length of the longest common substring and endIndex to store the ending index of the longest common substring.
     
  • Start a nested loop.
    • If i == 0 or j == 0, then dp[i][j] = 0.
       
    • If str1[i] == str2[j], then dp[i][j] = 1 + dp[i – 1][j – 1].
       
  • Keep track of the maximum value and return it.
  • C++

C++

#include <iostream>

#include <string.h>

using namespace std;

int lcsDP(string string_1, string string_2, int M, int N) {

// create a 2-D array named dp and intitialise all the values as zero.

int dp[M + 1][N + 1];

int count = 0;

/*

intitialise a nested loop

Check the base Case

*/

for (int i = 0; i <= M; i++) {

for (int j = 0; j <= N; j++) {

if (i == 0 || j == 0)

dp[i][j] = 0;

else if (string_1[i - 1] == string_2[j - 1]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

count = max(count, dp[i][j]);

}

else

dp[i][j] = 0;

}

}

return count;

}

// Driver code

int main() {

string str1 = "qdef";

string str2 = "defq";

cout << "Length of Longest Common Substring is " << lcsDP(str1, str2, str1.length(),str2.length());

return 0;

}

Output

Length of Longest Common Substring is 3

What is a binary search tree, and how is it implemented?

Ans: A binary search tree (BST) is a tree data structure where each node has at most two children, and the left child is always less than the parent, and the right child is greater than the parent. It allows for efficient searching, inserting, and deleting of elements in a sorted manner.

Here's an example implementation of a BST in C++:

  • C++

C++

#include <iostream>

using namespace std;

struct Node {

int data;

Node *left, *right;

};

class BST {

Node *root;

public:

BST() {

root = nullptr;

}

Node* get_root() {

return root;

}

Node* create_node(int value) {

Node *node = new Node;

node->data = value;

node->left = nullptr;

node->right = nullptr;

return node;

}

void insert(int value) {

root = insert_node(root, value);

}

Node* insert_node(Node *node, int value) {

if (node == nullptr) {

return create_node(value);

}

if (value < node->data) {

node->left = insert_node(node->left, value);

}

else {

node->right = insert_node(node->right, value);

}

return node;

}

void inorder_traversal(Node *node) {

if (node == nullptr) {

return;

}

inorder_traversal(node->left);

cout << node->data << " ";

inorder_traversal(node->right);

}

void preorder_traversal(Node *node) {

if (node == nullptr) {

return;

}

cout << node->data << " ";

preorder_traversal(node->left);

preorder_traversal(node->right);

}

void postorder_traversal(Node *node) {

if (node == nullptr) {

return;

}

postorder_traversal(node->left);

postorder_traversal(node->right);

cout << node->data << " ";

}

bool search(Node *node, int value) {

if (node == nullptr) {

return false;

}

if (node->data == value) {

return true;

}

else if (value < node->data) {

return search(node->left, value);

}

else {

return search(node->right, value);

}

}

};

int main() {

BST bst;

bst.insert(10);

bst.insert(5);

bst.insert(15);

bst.insert(3);

bst.insert(7);

bst.insert(12);

bst.insert(17);

cout << "Inorder traversal: ";

bst.inorder_traversal(bst.get_root());

cout << endl;

cout << "Preorder traversal: ";

bst.preorder_traversal(bst.get_root());

cout << endl;

cout << "Postorder traversal: ";

bst.postorder_traversal(bst.get_root());

cout << endl;

int value = 7;

bool found = bst.search(bst.get_root(), value);

if (found) {

cout << value << " found in the BST." << endl;

}

else {

cout << value << " not found in the BST." << endl;

}

return 0;

}

 Output:

Inorder traversal: 3 5 7 10 12 15 17 
Preorder traversal: 10 5 3 7 15 12 17 
Postorder traversal: 3 7 5 12 17 15 10 
7 found in the BST.

In this implementation, the binary search tree is defined as a class BST with a private variable root that points to the tree's root node. The Node struct defines the structure of each node in the tree, which has a data field and pointers to the left and right child nodes. The other operations are done accordingly.


How can you find the middle element of a linked list?

We can find the middle element of the linked list by traversing the linked list twice. First time for finding the length of the linked list and then traversing the linked list for (N/2) length.

A better approach would be using two-pointers.
 

  1. We will use two pointers, "slow" and "fast" Set both pointers to the head node at first.
     
  2. Traverse the linked list using a loop (fast!= NULL, and fast->next!= NULL) until the fast pointer reaches the last node of the linked list.
     
  3. The slow pointer moves one node per iteration, while the fast pointer moves two nodes.
     
  4. When the fast pointer reaches the last node, the slow pointer points to the middle node.
     
if(head == NULL){
return NULL;
}
struct node *slow, *fast;
slow = fast = head;
while(fast != NULL && fast->next != NULL) {
fast = fast->next->next;
slow = slow->next;
}
return slow->data;

Count the number of Longest Palindromic Substrings.Given a string s, find the length of the longest palindromic substring of the string and also see the number of palindromic substrings of that length.

Solution( Dynamic Programming)

Algorithm

The idea is to store the information of a substring from index i to index j in a dp array. So basically, the value of dp[i][j] will be 1 if the substring from index i to j is a palindrome. Otherwise, it will be 0. 

  • The recurrence relation will be that, for dp[i][j], we will check if s[i]==s[j] and dp[i+1][j-1]==1. Because for the substring from index i to j to be a palindrome, the last two characters should be equal, and also, the substring from i+1 and j-1 should be a palindrome in itself. In this way, we can find the value of all dp[i][j] for all i from 0 to n and all j from 0 to n (where n is the length of the string). 
     
  • The base case is all dp[i][i] =1 because the substring from index i to i will be a one character substring, and it will be a palindrome for sure. Also, we will have to initially find the value of dp[i][i+1] as a base case since the recurrence relation is not applicable here. So, we will traverse the whole string once, and, for each index i, we will see if s[i]==s[i+1]. If yes, then, dp[i][i+1]=1, otherwise 0.
     

Implementation

#include <bits/stdc++.h>
using namespace std;
bool isPalindrome(string temp){
    int n = temp.length();
    for (int i = 0; i < n/ 2; i++) {
        /* if the charcters at index i and n-i-1 are not equal, return false*/
        if (temp[i] != temp[n - i - 1]) {
            return false;
        }
    }
    
    /* Else return true*/
    return true;
}

/* This is the function that return the maximum length of the palindromic substring of this string */
int maxLengthOfPalindromicSubstring(string s) {
    int sz = s.size();

    // Base Case Length 1
    if(sz == 1) return 1;
    
    // Base Case Length 2
    if(sz == 2 && s[0] == s[1]) return 2;
    if(sz == 2 && s[0] != s[1]){
        return 2;
    }
    int longest = 1;
    /* Dp array for storing if the substring from index i to j is a palindrome or not*/
    bool dp[1000][1000] = {0,};  
    
    /* For all length 2 substrings */
    for(int i = 1;i<sz;++i){
        if(s[i-1]==s[i]){
            dp[i-1][i] = 1;
            longest = 2;
        }
        else{
            dp[i-1][i] = 0;
        }
    }   
    for(int i = sz-1;i>=0;i--){
        for(int j = i+1;j<sz;j++){    
            if(s[j] == s[i] && dp[i+1][j-1] == 1){
                dp[i][j] = 1;
                if(longest<(j-i+1)){
                    longest = j-i+1;
                }
            }
        }
    }
    return longest;
}

Before moving on, first, try this Problem on Coding Ninjas Studio.

You can visit Count the number of Longest Palindromic Substrings for other approaches to the problem.

You are given a reference or a pointer to the root of a binary search tree. Our task is to find the Lowest Common Ancestor in a Binary Search Tree.

 Solution(Recursion)

 Algorithm

  • Recursively visit the nodes.
     
  • If both given nodes are smaller than the root node, traverse the left subtree.
     
  • If both given nodes are greater than the root node, traverse the right subtree.
     
  • If cases (1) and (2) don’t satisfy, return the current subtree root node. 
     
  • If root is Null return Null.
     
#include <bits/stdc++.h>
using namespace std;
// struct Node to create Nodes in the Binary search tree
struct Node{
    int data;    // value of the node
    Node *left;  // left child
    Node *right; // right child
    Node(int d)
    {
        this->data = d;
        this->left = nullptr;
        this->right = nullptr;
    }

};

// function that finds the LCA of given 2 nodes present in the binary search tree
Node* findLCAinBST(Node* root, Node *nodeA, Node *nodeB){
    if(root==nullptr)   // base case
        return root;
    // if both nodes a and b are smaller than root node
    if(nodeA->data < root->data and nodeB->data < root->data)
        return findLCAinBST(root->left, nodeA, nodeB);   // go to the left subtree
    // if both nodes a and b are greater than root node
    if(nodeA->data > root->data and nodeB->data > root->data)
        return findLCAinBST(root->right, nodeA, nodeB);  // go to the right subtree
    // return the root since this is the LCA
    return root;
}


Before moving on, first, try this Problem on Coding Ninjas Studio.

You can visit Lowest Common Ancestor in a Binary Search Tree for the solution.

You have been given an array/list 'ARR' consisting of 'N' integers. Your task is to find the majority element in the array. If there is no majority element present, print no majority element. 

The majority element in the array is the element that occurs n/2 times. ( n denotes the size of the array.)

Naive Method

The most basic method is to use two loops and keep track of the total number of elements. Break the loops and return the element with the highest count if the maximum count exceeds n/2. The majority element does not exist if the maximum count does not exceed n/2.

Optimized Approach: Using Moore’s Voting Algorithm

This method consists of two methods :

  • The first step assigns an element to the array that may be the majority element. If an array contains a majority element, this step will yield the majority element; otherwise, it will return a candidate for the majority element.
     
  • Check to see if the element you got from the previous step is the majority element. This step is required since there may not be a majority element.

Algorithm

  • Loop through each element, keeping a count of the majority element and a max index for the majority index.
     
  • If the following element is the same as the previous one, the count should be increased. If the following element isn't the same as the previous one, the count is decremented.
     
  • If the count approaches 0, adjust the count to 1 and modify the max index to the current element.
     
  • Return to the array and count the number of majority elements discovered.
     
  • Print the element if the count is larger than half the array's size.
     
  • If there isn't a majority element, print "No Majority element."
  • C++

C++

#include <bits/stdc++.h>

using namespace std;

int findCandidate(int a[], int size) //finding candidate for majority

{

   int maj_index = 0, count = 1;

   for (int i = 1; i < size; i++) {

       if (a[maj_index] == a[i])

           count++;

       else

           count--;

       if (count == 0) {

           maj_index = i;

           count = 1;

       }

   }

   return a[maj_index];

}

bool isMajority(int a[], int size, int cand)

{

   int count = 0;

   for (int i = 0; i < size; i++)



       if (a[i] == cand)

           count++;

   if (count > size / 2) //if the element occurs more than n/2 times , it returns 1

       return 1;



   else

       return 0;

}

int main()

{

   int a[] = {8, 2, 2, 8, 1, 2, 2, 6, 2};

   int size = (sizeof(a)) / sizeof(a[0]);

   int cand = findCandidate(a, size);

   if (isMajority(a, size, cand)) //Checking whether the candidate element is majority or not.

       cout << cand;

   else

       cout << "No Majority Element";

   return 0;

}

Output:

2

Complexity

Time complexity :O(n)

Space Complexity : O(1) 

Given a 9x9 sudoku board. Determine whether the given sudoku board is valid or not. Only the filled cells need to be validated according to the following constraints:

  1. Each row must contain the digits 1-9 without repetition. 
     
  2. Each column must contain the digits 1-9 with repetition. 
     
  3. Each of the 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.
     
  • It should be noted that a Sudoku board (filled partially or fully) may or may not be solvable.
     
  • Check only the cells which are filled. Empty cells are to be ignored.
     
  • Each input will be a 2D char matrix. It will contain numbers and dots (.), where a dot represents a blank cell.

Ans : Let’s head straight to the approach of the Valid Sudoku problem.

  • Since we are dealing with sudoku, it is guaranteed that our input will always be a 2D matrix of 9x9 size. 
     
  • In the solution code provided, we will be traversing the input matrix row-wise. We will first check if the element is unique in its row, then the column, then the 3x3 grid.
     
  • For this purpose, we will be maintaining two 2D boolean vectors. These will track that at any given position, the elements do not repeat.
     
  • In the solution code, the two vectors are named cols and grid. The two vectors are initialized with false.
     
  • When traversing the sudoku board, three things need to be considered:
    • row-wise info: how many rows are to be checked?
       
    • column-wise info: how many columns are to be checked?
       
    • grid-wise info: how many grids are we supposed to check?
       
  • If we think about our approach, we are just looking one row at a time. So for that, a 1D vector is sufficient. For column-wise info, we will be traversing all nine columns, but each column has nine rows. So for that, we make the 2D vector cols. Finally, we will be storing the validation check for all nine 3x3 grids. We can use a map for that, but for simplicity, we will again use a 2D vector of size 9x9.
     
  • Now we start with the main idea. Start loop i from 0 up to 8. For each column i, create a 1D vector row and initialize it with false. Start another loop j from 0 up to 8. For each element in the row at position [i][j] check if it is a digit or not. We do this because we are only concerned with the numbers and not the dot (.) that denotes the blank cell. 
     
  • For each digit in a row, we create a variable idx. For our approach, the boolean value at each index of vector row denotes that element is present or not. For example, at ith index, we will store if the digit i is present in that row or not.
  • We then perform three checks to check if the element idx is already present in our sudoku or not.
     
  • We first check if idx is already present in that row or not. If present, we return false and exit the function. If not present, we set the idxth element in the row vector as true. 
     
  • Then, we check if idx is present in the column. To do so, we check the value at cols[j][idx]. If it is true, we return false and exit our function. Else, we update it to true.
     
  • Finally, we check if idx is present in the grid or not. For that, we find its grid index and store it in the variable gridIdx. To find the grid, we use the formula ((i/3)*3 + (j/3)). If the value at grid[gridInx][idx] is true, we return false and exit the function. Else, we update it to true.
     
  • After both our loops exhaust, we return true, which denotes that our sudoku board is correct and contains unique values at the required positions.   
     

 Before moving to the solution code, the readers can write pseudocode to understand the problem better. 

The readers can also practice the Valid Sudoku problem on our platform Coding Ninjas Studio by clicking hereSudoku? 

  • C++

C++

#include <iostream>

#include <vector>

using namespace std;

bool isValidSudoku(vector<vector<char>>& board){

   vector<vector<bool>> cols(9, vector<bool> (9, false));

   vector<vector<bool>> grid(9, vector<bool> (9, false));

   for(int i = 0; i < 9; ++i)

   {

       vector<bool> rows(9, false);

       for(int j = 0; j < 9; ++j)

       {

           if(!isdigit(board[i][j]))

               continue;

           int idx = board[i][j] - '1';

           if(rows[idx] == true)

               return false;      

           rows[idx] = true;

           if(cols[j][idx] == true)

               return false;                     

           cols[j][idx] = true;

           int gridIdx = ((i/3) * 3) + (j/3);         

           if(grid[gridIdx][idx] == true)

               return false;           

           grid[gridIdx][idx] = true;

       }

   }   

   return true;

}

int main(){

   vector<vector<char>> board1 = {

                                   {'5','3','.','.','7','.','.','.','.'},

                                   {'6','.','.','1','9','5','.','.','.'},

                                   {'.','9','8','.','.','.','.','6','.'},

                                   {'8','.','.','.','6','.','.','.','3'},

                                   {'4','.','.','8','.','3','.','.','1'},

                                   {'7','.','.','.','2','.','.','.','6'},

                                   {'.','6','.','.','.','.','2','8','.'},

                                   {'.','.','.','4','1','9','.','.','5'},

                                   {'.','.','.','.','8','.','.','7','9'} 

                               };

  if(isValidSudoku(board1)){

       cout << "The Sudoku in board1 is Valid !" << endl;

   }

   else{

       cout << "The Sudoku in board1 is NOT Valid !" << endl;

   }

 vector<vector<char>> board2 = {

                                   {'5','3','3','.','7','.','.','.','.'},

                                   {'6','.','.','1','9','5','.','.','.'},

                                   {'.','9','8','.','.','.','.','6','.'},

                                   {'8','.','.','.','6','.','.','.','3'},

                                   {'4','.','.','8','.','3','.','.','1'},

                                   {'7','.','.','.','2','.','.','.','6'},

                                   {'.','6','.','.','.','.','2','8','.'},

                                   {'.','.','.','4','1','9','.','.','5'},

                                   {'.','.','.','.','8','.','.','7','9'} 

                               };
   if(isValidSudoku(board2)){

       cout << "The Sudoku in board2 is Valid !" << endl;

   }

   else{

       cout << "The Sudoku in board2 is NOT Valid !" << endl;

   }

   return 0;

}

 Output:

The Sudoku in board1 is Valid !
The Sudoku in board2 is NOT Valid !

Time complexity

In the given approach, we traverse the whole sudoku board once and check each cell. Thus time complexity is,

T(n) = O(n2)

Space Complexity

In the given approach, we create a 2D boolean vector to store whether a number in a cell is unique or not.

How do you implement a breadth-first search?

Breadth-first search is an algorithm used to traverse and search a graph or a tree data structure. Here is an implementation of the Breadth-First Search algorithm in Python.

  • Python

Python

from collections import deque

class Node:

def __init__(self, val=None, left=None, right=None):

self.val = val

self.left = left

self.right = right

def bfs(root):

if not root:

return []

queue = deque([root])

result = []

while queue:

curr_node = queue.popleft()

result.append(curr_node.val)

if curr_node.left:

queue.append(curr_node.left)

if curr_node.right:

queue.append(curr_node.right)

return result

# Example usage

root = Node(1, Node(2), Node(3, Node(4), Node(5)))

bfs_result = bfs(root)

print(bfs_result)

 Output:

[1, 2, 3, 4, 5]


In this program, we define a Node class that represents a node in a binary tree. Each Node has a val attribute that stores the value at that node, and left, and right attributes that point to the left and right children, respectively.

We also define a bfs function that performs a breadth-first search on the binary tree and returns a list of node values in the order they were visited. We use a deque from the built-in collections module to keep track of the nodes to be visited next. We start with the root node and add it to the queue. Then, we repeatedly dequeue the front node, add its value to the result list, and enqueue its children (if they exist) to the back of the queue.

To use this program, we create a binary tree by instantiating Node objects and setting their valleft, and right attributes. We then call bfs on the root node and output the result.

Given a set of n nuts of different sizes and n bolts of different sizes. There is a one-one mapping between nuts and bolts. Match nuts and bolts efficiently. Constraint: Comparison of a nut to another nut or a bolt to another bolt is not allowed. It means nut can only be compared with bolt and bolt can only be compared with a nut to see which one is bigger/smaller.

The brute force idea is to traverse the bolts/nuts array for each of the nuts/bolt’s elements i.e., for each nut there will be n comparisons in the worst case and vice versa.

Optimized Approach : HashMap

Another way of solving this problem is by using a Hashmap. The idea here is to store the bolts and their corresponding pair of nuts in a map of key-value pairs. Although this increases the space complexity but reduces the time complexity to linear order.

  • C++

C++

#include <bits/stdc++.h>
using namespace std;
// function to match nuts and bolts
void solve(char *nut, char *bolt, int n)
{
unordered_map<char, int> mp;
//storing in the map
for (int i = 0; i < n; i++)
mp[nut[i]] = i;
for (int i = 0; i < n; i++)
if (mp.find(bolt[i]) != mp.end())
nut[i] = bolt[i];
}
int main() {
int t;
cin>>t;
while(t--){
int n;
cin>>n;
char *bolt = new char[n];
char *nut = new char[n];
for(int j = 0;j<n;j++)cin>>nut[j];
for(int i = 0;i<n;i++)cin>>bolt[i];
solve(nut,bolt,n);
for(int j = 0;j<n;j++)cout<<nut[j]<<" ";
cout<<endl;
for(int i = 0;i<n;i++)cout<<bolt[i]<<" ";
}
return 0;
}

Output

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


Time Complexity: O(n), where n is the number of elements in each array.

Space Complexity: O(n), where n is the number of elements in each array. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

How long are Google interviews?

Google interviews are generally 45 minutes - 1 hour. This also depends on the rounds and also on the specific role for which you have applied. 

Does Google hire Freshers?

Yes, Google hires freshers for various roles and in different domains. Google also visits campus to hire fresh graduates. It also recruits graduates off campus through referrals or from their career portal. 

Are Google Interviews hard?

Google's interview process can be hectic and hard. However, the interview structure is quite the same every time, making it much easier to prepare and minimizing surprises.

Conclusion

In this blog, we learned about Google Interview Questions. We discussed both the Data Structure Questions as well as programming Questions. 

Since we have discussed so much about the Google Interview Questions, you must be wondering where I can learn more stuff to stay ahead in the race.

To practice the important Questions, you can visit our platform Coding Ninjas Studio. It contains curated questions specifically targeting Google.

You can also participate in the Coding Ninjas Studio Weekly Tests every week to stay on the right track.

Previous article
Power Bi Interview Questions
Next article
Capgemini Interview Questions
Live masterclass