## Google Recruitment Process

**Application Review**

After you submit your application, Google’s recruiters review your resume to see if your skills and experience match the job requirements. If your profile is a good fit, they will reach out to schedule an initial call.

**Recruiter Call**

The recruiter will contact you for a phone interview. This call typically covers your background, your interest in the role, and some basic technical questions or problem-solving scenarios. It’s also your chance to ask questions about the role and company.

**Technical Phone Interview**

You will have one or more technical phone interviews with a Google engineer. Expect to solve coding problems, data structures, and algorithms on the spot. You may use a collaborative coding platform like Google Docs or a shared coding environment.

**On-site Interviews**

If you pass the phone interviews, you’ll be invited to an on-site interview (or a virtual equivalent). This usually includes several rounds with different interviewers, covering a range of topics:

**Technical Interviews:** Solve coding problems, demonstrate your understanding of algorithms, data structures, and system design.**Behavioral Interviews:** Discuss your past experiences and how you handle various work situations. Google looks for "Googleyness," which encompasses cultural fit and problem-solving abilities.**Role-Specific Interviews:** These focus on the specific skills required for the role, such as design patterns or domain-specific knowledge.

**Feedback and Decision**

After the interviews, the interview panel will discuss your performance and decide whether to extend an offer. The recruiter will inform you of the outcome, and if you receive an offer, you’ll negotiate terms and start preparing for your new role.

## Google Interview Preparation Tips

**Understand the Role**

To excel in your interview, it’s crucial to thoroughly understand the role you're applying for. Start by carefully reading the job description and noting the required skills and qualifications. Research the specific team and department to grasp their objectives and projects. This will help you tailor your answers and show how your skills and experiences align with the role’s needs. Additionally, exploring Google’s work culture and values can help you understand what qualities they are looking for. This preparation will allow you to effectively demonstrate how you can contribute to the team and solve the problems they face.

**Master Data Structures and Algorithms**

Google’s interviews heavily focus on your ability to solve complex problems using data structures and algorithms. Spend ample time practicing coding problems related to arrays, linked lists, trees, graphs, and algorithms such as sorting, searching, and dynamic programming. Use platforms like LeetCode, HackerRank, and CodeSignal to work through a variety of problems. Aim to understand the underlying principles behind these problems rather than just memorizing solutions. This will help you apply your knowledge to different problems and improve your problem-solving skills. Regular practice and understanding problem-solving strategies will be key to performing well in technical interviews.

**Practice Coding on a Whiteboard**

Coding interviews at Google often require you to write code on a whiteboard or in a shared document, which can be quite different from coding in an IDE. Practice solving problems on a whiteboard or using a simple text editor to simulate this experience. Focus on clearly explaining your thought process as you write your code. This includes outlining your approach, writing code step-by-step, and checking for errors. Whiteboard coding tests your ability to think on your feet and communicate your problem-solving approach effectively. Regular practice in this format will help you become more comfortable and articulate during the actual interview.

**Prepare for Behavioral Questions**

Behavioral questions at Google often explore how you handle different work situations and your past experiences. Use the STAR method (Situation, Task, Action, Result) to structure your answers. Start by describing the context of the situation, what tasks you were responsible for, the actions you took to address the tasks, and the results of your actions. Reflect on various experiences where you demonstrated problem-solving, leadership, or teamwork. This method helps you provide clear, concise, and impactful responses that highlight your skills and accomplishments. Practicing these responses will make you more confident and effective in conveying your experiences during the interview.

**Brush Up on System Design**

For senior or specialized roles, system design questions are a crucial part of the interview process. Prepare by studying concepts like scalability, load balancing, database design, and system architecture. Practice designing systems that handle large-scale data, high traffic, and complex interactions. Think about trade-offs and design decisions, and be prepared to explain your reasoning. Consider using design patterns and principles to structure your answers. Understanding how to create efficient and scalable systems will show your ability to handle real-world challenges. Use resources such as books, online courses, and mock interviews to refine your system design skills.

**Research Google’s Culture**

Google’s unique work culture and values are an integral part of their hiring process. Research Google’s culture by reading about their values, work environment, and what they look for in employees, known as “Googleyness.” This includes qualities such as innovation, collaboration, and a growth mindset. Reflect on how your personal values and work style align with Google’s culture. During the interview, demonstrate how your experiences and approach fit within their culture. Showing that you understand and align with their values will help you stand out as a candidate who is not only technically skilled but also a good cultural fit.

**Mock Interviews**

Conducting mock interviews can significantly enhance your preparation for Google’s interview process. Engage in mock interviews with friends, mentors, or through online platforms that simulate real interview conditions. Focus on practicing both technical and behavioral questions. This will help you get accustomed to the format and timing of interviews, as well as receive constructive feedback on your performance. Use this feedback to identify areas for improvement and adjust your preparation strategy. Mock interviews also help reduce anxiety and build confidence, making you more prepared and poised for the actual interview.

**Ask Questions**

During your interview, it’s important to ask thoughtful questions about the role, team, and company. Prepare questions that show your interest in the position and help you understand the team dynamics, projects, and growth opportunities. Asking insightful questions demonstrates your enthusiasm for the role and helps you gather important information to make an informed decision if you receive an offer. Consider asking about the team’s current challenges, future projects, or the company’s direction. This not only shows that you are proactive but also helps you gauge whether the role and company are a good fit for your career goals.

**Most Asked Google Interview Questions and Answers**

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

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

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

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

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

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

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

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

}

}

You can also try this code with Online C++ Compiler

Run Code
**Input: **

```
6
-1 0 1 2 -1 -4
```

**Output: **

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

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

`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();

}

}

You can also try this code with Online Java Compiler

Run Code
Output

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

### 8. 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++

`#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;

}

You can also try this code with Online C++ Compiler

Run Code
Output

`Equilibrium point is at index 3`

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

`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

You can also try this code with Online Java Compiler

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

### 10. 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 */**

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

}

You can also try this code with Online C++ Compiler

Run Code
Output

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

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

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

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

}

You can also try this code with Online C++ Compiler

Run Code
Output:

`Celebrity ID 2`

### 12. 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++

`#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;

}

You can also try this code with Online C++ Compiler

Run Code
**Output**

`Length of Longest Common Substring is 3`

### 13. 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++

`#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;

}

You can also try this code with Online C++ Compiler

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

### 14. 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;
```

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

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

### 17. 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++

`#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;

}

You can also try this code with Online C++ Compiler

Run Code
Output:

`2`

**Complexity**

Time complexity :O(n)

Space Complexity : O(1)

### 18. 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?__* *

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

}

You can also try this code with Online C++ Compiler

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

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

`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)

You can also try this code with Online Python Compiler

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

### 20. 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++

`#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;

}

You can also try this code with Online C++ Compiler

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

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

### How many rounds are there in Google Interview?

The Google interview process typically includes 4 to 5 rounds. This generally consists of a phone screen, one or two technical interviews, and an onsite interview with additional technical and behavioral questions.

### Why do you want to join Google?

Joining Google offers the chance to work on innovative projects with a global impact. Google's culture of collaboration, cutting-edge technology, and opportunities for growth are appealing to those passionate about solving complex problems and driving technological advancements.

### Can I apply for multiple roles at Google?

Yes, you can apply for multiple roles at Google. It’s a good idea to tailor your resume and application to each role to highlight relevant skills and experiences. Google reviews applications to match candidates with the best-fit positions.

### What is Googleyness?

Googleyness is a term used to describe qualities that align with Google’s culture, such as creativity, problem-solving skills, and a collaborative spirit. It reflects a candidate's fit with Google’s values and ability to thrive in its unique work environment.

## Conclusion

In this blog, we covered a range of Google interview questions, including those focused on data structures and programming. With this detailed overview, you might be curious about where to further enhance your skills and stay competitive.

To practice the important Questions, you can visit our platform __Code360____.__ 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.