## Introduction

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

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?

- 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:**

- If array size is < 3, means no triplet would exist from that array. Return empty vector of vectors.

- 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

- 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.

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

- Make a nested loop to fix a number after the first fixed number. (num[j])

- To make sum 0, we would require the -ve sum of both fixed numbers. Let us say this required.

- 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.

- Update j to last occurence of 2nd fixed number to avoid duplicate triplets.

- Update i to last occurence of 1st fixed number to avoid duplicate triplets.

- Return answer vector.

**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.

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.

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.

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:

- Rotate the top row of the ring.

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

- Rotate the bottom row of the ring.

- 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 */**

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:

- Create a stack and push all ids in it.

- 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.

- Pop two elements from the stack. Let these elements be ‘id1’ and ‘id2’.
- 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.

- If this person is a celebrity, return his id; otherwise, return -1.

**Time complexity: O(N)**

** Space complexity: O(N)**

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].**

- If
- Keep track of the maximum value and return it.

**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++:

**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.**

- We will use two pointers, "slow" and "fast" Set both pointers to the head node at first.

- 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.

- The slow pointer moves one node per iteration, while the fast pointer moves two nodes.

- 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."

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:

- Each row must contain the digits 1-9 without repetition.

- Each column must contain the digits 1-9 with repetition.

- 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 idx
^{th}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 here**: *__Sudoku?__* *

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.

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 **val**, **left**, 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.

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.