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
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
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
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
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
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
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
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
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
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 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 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
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
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
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.
46+ registered 