Google Interview Questions, Process, and Tips for Freshers

Round duration - 60 Minutes
Round difficulty - Easy

It was a hangout video call. The interviewer asked me these questions. Tell me about yourself and 1 coding question.

Q1. Special Numbers
You are given an integer, ‘MAXVAL’. Your task is to determine the total number of special numbers present in the range, 1 to ‘MAXVAL’.
Note:
A special number is a number, which when rotat...read more
Ans. Check all numbers independently
The approach is to loop through all the numbers in the given range one by one and check whether this number is a special number or not. We can check if a number is special or not, by rotating it. This can be achieved by reversing the string representation of the number and thereafter, replacing every ‘6’ by ‘9’ and vice versa. 
 
Steps:
 
• Initialize a variable, say count = 0. T...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 60 Minutes
Round difficulty - Easy

This was an On-site (Behavioural Round) interview. He asked me these questions.

Q1. Basic HR Questions
1. Tell me about yourself
2. Why Google?
3. Which product of Google you like most? Why? Any competing products in the market?
4. If I asked your current organization for feedback then what w...read more
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

This was another On-site ( DS & Algo) algorithm.

Q1. Covid Vaccination
We are suffering from the Second wave of Covid-19. The Government is trying to increase its vaccination drives. Ninja wants to help the Government to plan an effective method to help incr...read more
Ans. Brute force
The idea is to choose a peak value at the ‘dayNumber’ th index. Then we can create the array like a mountain with the peak of the mountain being at the  ‘dayNumber’ th index. The sum of the elements of this array must be less than or equal to maxVaccines.If we find that the sum is greater, then we have chosen a high peak value, and if it is less, then it means we have chosen a smaller peak value. So we ...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 60 Minutes
Round difficulty - Easy

Another On-site ( DS & Algo) interview.

Q1. Painter's Partition Problem
Given an array/list of length ‘N’, where the array/list represents the boards and each element of the given array/list represents the length of each board. Some ‘K’ numbers of p...read more
Ans. Dynamic Programming
All we need to do is to Divide the boards into k of fewer partitions such that the maximum sum of the elements in a partition, overall partitions is minimized.
 
We can put the (k - 1)th divider between the ith and (i + 1)th element where i is between 1 and N.
 
Now the recursive function will just require two conditions that can lead to the result and that will be out the maximum total cost:
• Th...read more
Answered by CodingNinjas
View 3 more amswers
Q2. Chocolate Problem
Given an array/list of integer numbers 'CHOCOLATES' of size 'N', where each value of the array/list represents the number of chocolates in the packet. There are ‘M’ number...read more
Ans. Recursion
The idea is that generate all the possible subsets of size ‘M’ and checks the minimum difference that can be possible from all subsets. 
 
1. This problem can be solved using recursion and the idea behind this is to generate all the possible minimum differences from the given array.
2. To store minimum difference we use a variable (say, ‘minVal’) and the initial value is ‘INFINITE’
3. For each element we will hav...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 60 Minutes
Round difficulty - Easy

Another On-site ( DS & Algo) interview.

Q1. Minimize the Maximum
You are given an array of N integers and an integer K. For each array element, you are allowed to increase or decrease it by a value k. The task is to minimize the difference between t...read more
Ans. Brute Force
 For every element, we have two choices either increase it by k or decrease it by k. 
 
• Initialize a global variable ans to the maximum value.
• Call a helper function that takes an array, k, index, and min and max as arguments, where min will be initialized to maximum value and minimum will be initialized to the minimum value.
• Check for the base condition if the whole array is processed then update...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 60 minutes
Round difficulty - Easy

On-site ( DS & Algo) interview.
Google mainly focuses on logic and how you are coming with a solution. It notes down each and every small mistake. Interviewers are really very helpful. They expect clear code with an optimal approach.

Q1. Farthest Distance From Lands
You are given a binary square matrix ‘ARR’ with N rows and N columns, in which 0 represents the water and 1 represents the land.
You have to find a water cell such that its d...read more
Ans. BFS
The idea here is to calculate the distance from each land cell and update every water cell to the minimum distance via any land cell.
We declare a 2d matrix minDistance[][] initially set to Infinity, and then run BFS from every land cell and calculate the shortest distance to each water cell, and update the minDistance[][] to the minimum shortest distance to a water cell. The maximum value which is not equal to infin...read more
Answered by CodingNinjas
View 1 more amswer

Q1. What is your experience
Add your answer
Q2. What is your digree nothing else start
Add your answer

Round duration - 60 Minutes
Round difficulty - Medium

For the online coding test, we got two coding questions out of which I was only able to solve one and the other one partially, where only some test cases passed. 

Q1. Find all anagrams
You have been given a string STR and a non-empty string PTR. Your task is to find all the starting indices of PTR’s anagram in STR.
An anagram of a string is another string which contai...read more
Ans. Brute Force Approach
We have a brute force solution to this problem. We find all substrings of STR of length M (length of PTR) and store indices of those substrings in ‘ANAGRAM_INDICIES’ which are the anagrams of given string PTR.
 
Here is the complete algorithm - 
 
1. We store the count of characters of ‘PTR’ in array ‘PTR_MAP’. Index of a character ‘CH’ is given by 'CH’ - ‘A’.
2. Now, we traverse ‘STR’ and find ...read more
Answered by CodingNinjas
Add your answer
Q2. Binary strings with no consecutive 1s
You have been given an integer K.
Your task is to generate all binary strings of length K such that there are no consecutive 1s in the string. This means that the bi...read more
Ans. Recursive Approach
Since we need to generate all substring which does not have consecutive 1s we can simply start adding new characters to the string until the length of the string is ‘K’ taking care that if the last character of the current string is ‘1’ we cannot add another ‘1’ as it will result in consecutive ‘1s.’ Otherwise, if the last character is ‘0’ we have 2 options either to add ‘1’ or ‘0’. We explore both th...read more
Answered by CodingNinjas
Add your answer

Round duration - 45 Minutes
Round difficulty - Easy

The interview started with a brief discussion of one of the projects mentioned in my resume, then the interviewer fast-forwarded to a coding problem. I was coding on a Google Doc which the interviewer was examining at the same time. The solution to the question involved knowledge of stack, and built-around logic definitely. I was able to solve this question but was asked to optimize it further. I couldn’t think about the optimization part before a small hint was given to me by the interviewer itself. I coded the additional optimization logic too as I could grasp the hint quickly.
In the end, the interviewer gave me the chance to ask him a question. And with this, the interview ended leaving me with no positive or negative feedback about my performance.

Q1. Minimum Character Deletion
You are given a string ‘STR’. You need to find and return the minimum number of characters to be deleted from ‘STR’ so that the frequency of each character in the string becomes ...read more
Ans. Brute Force
As we are only allowed to delete the character, thus the resulting string after deletion of some character would be the subsequence of the string. So, we have to find such a subsequence which has the unique frequency of each character. 
 
Initialise a variable ‘ans’ that will store the minimum number of characters that are needed to remove from the string. Create all the subsequences of the string an...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 50 minutes
Round difficulty - Medium

The interviewer straight-forwardly jumped into the question.
PS: There were 2 interviewers in this round.

Q1. Convert binary tree to mirror tree
Given a binary tree, convert this binary tree into its mirror tree.
A binary tree is a tree in which each parent node has at most two children.
Mirror of a Tree: Mirr...read more
Ans. Recursive approach.
The idea is to traverse the binary tree and swap the left and right subtrees.
 
The steps are as follows:
 
1. Call mirror function as mirror(node->left)  to access the left subtree.
2. Call mirror function as mirror(node->right) to access the right subtree.
3. Swap left and right subtrees using:
• ‘TEMP’ = leftSubtree
• leftSubtree = rightSubtree
• rightSubtree = ‘TEMP’
Space Complexity: O(n)Explanation...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 90 mintues
Round difficulty - Medium

Time — 45 minutes
Questions asked — 2

Q1. Check If The String Is A Palindrome
You are given a string 'S'. Your task is to check whether the string is palindrome or not. For checking palindrome, consider alphabets and numbers only and ignor...read more
Ans. Reverse and Compare
• A palindrome string is a sequence of characters which reads the same backward as forward. We use this property of palindrome to check whether the given string is a palindrome or not.
• First off, we convert the given string to lowercase, this would make it easier for us to check for palindrome.
• Now, the idea is to reverse the given string and store it in another variable.
• We need to compare the original s...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Intersection of Linked List
You are given two Singly Linked List of integers, which are merging at some node of a third linked list.
Your task is to find the data of the node at which merging starts. If ...read more
Ans. Brute Force
• For each node in the first list, traverse the entire second list
• Check if any node in the second list coincides with the first list
  • If it does, return that node’s data
  • If it doesn’t, return -1
Space Complexity: O(1)Explanation:
O(1)
 
Since we only use constant space.
Time Complexity: O(m*n) - For 2d arraysExplanation:
O(N * M), where N and M are the lengths of the first and second linked lists respectively.&n...read more
Answered by CodingNinjas
View 2 more amswers