Google Interview Questions, Process, and Tips for Freshers

Round duration - 60 minutes
Round difficulty - Medium

Q1. Min Steps to one using DP
You are given a positive integer 'N’. Your task is to find and return the minimum number of steps that 'N' has to take to get reduced to 1.
You can perform any one o...read more
Ans. 
Tip 1 : First think of the brute force approach and then optimise it . 
Tip 2 : Analysis if problems is very important.
Tip 3 : First Question was of dynamic programming so I guess in such Questions recursive solution is easier and I would go for it.
Answered by CodingNinjas
View 2 more amswers

Round duration - 100 minutes
Round difficulty - Medium

My interview was held from 3 to 3:50 and 4 to 4:50 in the evening . I sat in a silent place of my room with no disturbances in my room. 
The interviewer first asked me to introduce myself then he did the same, he then gave me a problem of sliding window and we discussed to reach on a optimal solution then I wrote the code for it . Then he asked me to ask if I had any questions , I asked some questions regarding their work culture , what do they expect from me and what work will I be given there as an SDE -intern. Second interview was almost the same the problem was of dynamic programming .

Q1. Maximum In Sliding Windows Of Size K
Given an array/list of integers of length ‘N’, there is a sliding window of size ‘K’ which moves from the beginning of the array, to the very end. You can only see the ...read more
Ans. Brute Force
Our intuition here is to go through each sliding window and keep track of the maximum element in each sliding window. To implement the same we run two nested loops, where the outer loop which will mark the starting point of the subarray of length k, the inner loop will run from the starting INDEX to INDEX + K, K elements from starting index and store the maximum element among these K elements into the answer...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 50 minutes
Round difficulty - Medium

I have already given the description in the previous round.

Q1. Remove K Corner Elements
Given an array ‘arr’ consisting of ‘N’ integer elements. You have to remove ‘K’ elements from the beginning or end of the array. Return the maximum possible sum of the remaining a...read more
Ans. Brute Force
For each possible combination of removing elements from the array, calculate the sum of the remaining elements. Finally, return the maximum sum calculated over all the possible ways.
The steps are as follows:
1. Initialize ans = 0.
2. Run a for loop for stPos from 0 to K.
3. Calculate the sum of array from stPos to N - 1 - (K - stPos).
4. If sum is greater than ans, then set ans equal to the value of sum.
5. Return the final val...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 60 minutes
Round difficulty - Easy

Timing: Between 3-5 pm we could take the test anytime
The test environment was hackerrank. Great user interface and I did not suffer anyt problems.
There was no interviewer as it was coding test. 
There were 2 coding questions asked.

Q1. Subset OR
You are given an array/list ‘ARR’ of ‘N’ positive integers’. Your task is to find out the size of the smallest subset with the maximum OR possible. That means that among all subsets that have OR ...read more
Ans. Recursion

 
The maximum possible OR of any subset is the OR of the whole array. So let the OR of the whole array be equal to ‘K’.
The idea is to generate all possible subsets and check if any of them OR up to ‘K’. This can be done through recursion.
Here is the algorithm:
subsetOR(N , ARR):
1. Initialize the variable ‘K’ = OR of the complete array.
2. Initialize integer variable ‘ANS’ = ‘helper(ARR, N, K, 0)’. Here ‘helper’ is...read more
Answered by CodingNinjas
View 2 more amswers
Q2. Wildcard Queries
You are given a dictionary ‘D’ consisting of ‘N’ words. Each word of the dictionary is of fixed size ‘L’ and contains only lowercase English alphabets.
Now you have to answer ‘Q’ queries...read more
Ans. Backtracking To Generate All Possible Words
Store the dictionary words in a hash-map for a constant lookup time, now for each query word, try replacing each ‘?’ with every possible lowercase alphabet and generating all possible words that can be formed by the query word, for each of them: search whether it exists in the dictionary or not.
The steps are as follows:
1. Initialize finalAnswer array to store the answer to each q...read more
Answered by CodingNinjas
View 2 more amswers

Round duration - 45 minutes
Round difficulty - Medium

Timing was late at night ie 9:30 PM for this round.
The environment was nice. It was on Google meet.
The interviewer was very friendly and explained the question well

Q1. Rat In A Maze
You are given a starting position for a rat which is stuck in a maze at an initial point (0, 0) (the maze can be thought of as a 2-dimensional plane). The maze would be given in the form of a...read more
Ans. Bactracking
Approach: We can start the traversal of the paths from the rat’s starting position, i.e. (0,0) keeping track of the visited cells during the traversal. We will recursively go through all the paths possible until the last index of the grid (destination) is reached, and add the path information using which the rat successfully reached the end.
 
Algorithm is as follows:
 
1. Take the starting position of th...read more
Answered by CodingNinjas
Add your answer
Q2. BFS in Graph
You are given an undirected and disconnected graph G(V, E) having V vertices numbered from 0 to V-1 and E edges. Your task is to print its BFS traversal starting from the 0th vertex.
BFS or ...read more
Ans. Using queue
Let us consider a function BFS that accepts a list of edges, EDGES, and the number of vertices VERTEX as a parameter and do: 
1. Create ADJACENCYMATRIX from EDGES.
2. Define a boolean array VISITED to store nodes that are already visited.
3. Iterate over VISITED[i] for each 0<= i < VISITED.LENGTH, and check:
   1. If VISITED[i] is FALSE, call BFSHELPER function for ADJACENCYMATRIX, i and VISITED.
Now, the function BF...read more
Answered by CodingNinjas
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Q1. Technical Questions
How to align a text in a larger web page context?
OOPS Concepts
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

Q1. Alien dictionary
You have been given a sorted (lexical order) dictionary of an alien language. Write a function that finds the order of characters in the alien language. This dictionary will be given to yo...read more
Ans. Permutations Approach
Approach:
• Find all the distinct characters present in all the words.
• Generate all permutations of these distinct characters.
• Treat each of the permutations as a correct sequence of alphabets. Now check if the given words are sorted according to this sequence. In order to do this, we will:-
  • For all words from 1 to n - 1, let the current word be ‘currWord’ and the next word be ‘nextWord’.
  • One by one compa...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Shopping Spree
Preeti has decided to go to the Grand Mall to buy some stuff for her father’s birthday. On reaching the place, she found a fascinating shop that has an unlimited quantity of each item they s...read more
Ans. Recursion
• The idea is to use recursion to reduce the big problem into several small subproblems.
• We will call a helper function that returns us the possible number of ways to shop.

Now, let us understand how to break the big problem into small subproblems with an example let's say, for N = 2 and K = 3 and let the items be {R, G} we can see that this can be found out if:
 
• We know the possible answer for buying at most ...read more
Answered by CodingNinjas
View 3 more amswers

Round duration - 60 Minutes
Round difficulty - Easy

Basic DBMS problems.

Q1. DBMS Question
RDBMS vs Non RDBMS
Why SQL is very popular?
How do you get second largest salary
What is stored procedure?
Add your answer

Round duration - 30 Minutes
Round difficulty - Easy

He asked basic Database and oops questions and discussion about my projects.

Q1. OS Questions
Sleeping barber problem.
Disk scheduling algos
Process Scheduling algos
Turnaround time
Threads
Add your answer

Round duration - 50 Minutes
Round difficulty - Easy

It was evening. Since it was a telephonic interview so all at the home. NOthing different. About my soft skills, resume, and some basic coding stuff. Why google? Where do you see yourself in 5 years?

Q1. Count Ways To Reach The N-th Stairs
You have been given a number of stairs. Initially, you are at the 0th stair, and you need to reach the Nth stair. Each time you can either climb one step or two steps. Y...read more
Ans. Brute Force
One basic approach is to explore all possible steps which can be climbed with either taking one step or two steps. So at every step, we have two options to climb the stairs either we can climb with one step, or we can climb with two steps. So the number of ways  can be recursively defined as :
countDistinctWayToClimbStair ( currStep, N ) = countDistinctWayToClimbStair ( currStep+1, N ) + countDistinctWay...read more
Answered by CodingNinjas
View 3 more amswers

Dsa questions started with arrays goes till graphs

Q1. What is your salary expectation
Ans. I have told them my expectation and we negotiated on that
Answered by Being DHakad
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

Timing : Evening

Q1. Distance between two nodes of a Tree
Given a binary tree and the value of two nodes, find the distance between the given two nodes of the Binary Tree.
Distance between two nodes is defined as the minimum...read more
Ans. Naive Approach
In any rooted tree, the distance between two nodes 'U' and 'V' can be found by finding the lowest common ancestor (LCA), ‘x’ of two nodes. The lowest common ancestor (LCA) between nodes 'U' and 'V' is defined as the lowest node in the tree that has both 'U' and 'V' as descendants, where we define each node to be a descendant of itself (so if 'U' has a direct connection from 'V', 'V' is the lowest common a...read more
Answered by CodingNinjas
View 1 more amswer
Q2. Delete Leaf Nodes with Value X
You are given a binary tree, in which the data present in the nodes are integers. You are also given an integer X.
Your task is to delete all the leaf nodes with value X. I...read more
Ans. DFS
We do a depth-first traversal to travel the tree :
 
• Base case: If the root is NULL, we will return NULL
• If the root's left is not NULL, then we will update the root's left by using recursion and deleting all leaf nodes in the left subtree
• If the root's right is not NULL, then we will update the root's right by using recursion and deleting all leaf nodes in the right subtree
• Finally, we will check whether the root i...read more
Answered by CodingNinjas
Add your answer

Round duration - 45 minutes
Round difficulty - Easy

Timing : 10:00 pm

Q1. Maximum sum path from the leaf to root
You are given a binary tree of 'N' nodes.
Your task is to find the path from the leaf node to the root node which has the maximum path sum among all the ro...read more
Ans. Recursive Subproblem
The idea here is that we will do a recursive solution by asking the children of the current node for the max sum path and then choose the path with the max sum. 
 
The approach will be as follows:
1. Get the max sum path for the left subtree.
2. Get the max sum path for the right subtree.
3. Select the one with the max sum from both and insert current node's data into it.
4. Return the updated path.
    
Al...read more
Answered by CodingNinjas
View 1 more amswer

Round duration - 45 minutes
Round difficulty - Easy

Timimg : 11:00 pm

Q1. Ninja and the bulbs
Ninja owns an electronic shop. In the shop, Ninja has 'N' bulbs. To sell these bulbs, Ninja has to check if they are of good quality. To check bulbs, Ninja uses a unique techniq...read more
Ans.  Brute Force
Approach:
A brute force solution to this problem is to turn on and off the bulbs N time, then at last check the number of bulbs that are on.

 
Algorithm:
• Take a boolean array of ‘BULBS’ of size N+1.
• Itertate on ‘i’ from 1 to ‘N’
  • Iterate on ‘j’ form ‘i’ to ‘N’ and each time increment ‘j’ as ‘j’ += ‘i’.
    • if(BULBS[j] == true) then make it false.
    • If (BULBS[j]==false) then make it true.
• Intialise a variable ‘COUNT’ =...read more
Answered by CodingNinjas
View 2 more amswers