Google Software Developer Interview Questions, Process, and Tips

Round duration - 60 minutes
Round difficulty - Medium

This round was held on Hackerearth from 2:00 PM to 3:00 PM
This round had 2 questions of easy/medium difficulty. Both were based on concepts of DP.
The use of offline IDE was prohibited so we were supposed to code it on Hackerearth IDE itself.

Q1. 
Min Steps to One Using Dynamic Programming
Given a positive integer N, your task is to determine the minimum number of steps required to reduce N to 1.
Allowed Operations:
1) Subtract 1 from it: n = n -...read more
Ans. 
Find the minimum number of steps to reduce a positive integer to 1 using dynamic programming.
• Use dynamic programming to keep track of the minimum steps for each number from 1 to N.

• Consider the three allowed operations and their impact on the number of steps.

• Start from N and work backwards to 1, updating the minimum steps for each number.

• Optimize the solution by storing the minimum steps for previously calculated number
Answered by AI
Add your answer
Q2. 
Find the Longest Palindromic Substring
Given a string ‘S’ composed of lowercase English letters, your task is to identify the longest palindromic substring within ‘S’.
If there are multiple longest palin...read more
Ans. 
Find the longest palindromic substring in a given string, returning the rightmost one if multiple exist.
• Use dynamic programming to check for palindromes within the string.

• Keep track of the longest palindromic substring found so far.

• Return the rightmost longest palindromic substring if multiple exist.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

The round was held on Google Meet and I was given 2 coding problems for which first I had to explain my approach and then I had to write code in Shared Google Docs and dry run on sample test cases and discuss Time and Space Complexity.
There were 2 interviewers and both were very friendly and helpful and tried to bring us to our comfort level first.

Q1. 
Pattern Matching Problem Statement
Given a pattern as a string and a set of words, determine if the pattern and the words list align in the same sequence.
Input:
T (number of test cases)
For each test ca...read more
Ans. 
Given a pattern and a list of words, determine if the words align with the pattern.
• Create a mapping between characters in the pattern and words in the list.

• Check if the mapping preserves the order of characters in the pattern.

• Return 'True' if the sequence of words matches the order of characters in the pattern, otherwise return 'False'.
Answered by AI
Add your answer
Q2. 
Running Median Problem
Given a stream of integers, calculate and print the median after each new integer is added to the stream.
Output only the integer part of the median.
Example:
Input:
N = 5  
Stre...read more
Ans. 
Calculate and print the median after each new integer is added to the stream.
• Use two heaps - a max heap to store the smaller half of the numbers and a min heap to store the larger half.

• Keep the sizes of the two heaps balanced or differ by at most 1 to get the median efficiently.

• When a new integer is added, compare it with the current median and insert it into the appropriate heap.

• If the sizes of the heaps differ by mor...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Medium

This round was also virtual. It has some difficult questions when compared to the previous rounds.
This was also held on Google Meet with shared docs for writing code.
There were 2 interviewers and both were helpful.

Q1. 
Shortest Alternate Colored Path Problem
Given a directed graph consisting of 'N' nodes labeled from '0' to 'N-1'. Each edge in the graph is colored either 'red' or 'blue'. The graph may include self-edges...read more
Ans. 
The task is to compute the shortest path from node '0' to each node in a directed graph with alternating colored edges.
• Create a graph using the given red and blue edges.

• Use Breadth First Search (BFS) to find the shortest path from node '0' to each node.

• Alternate between red and blue edges while traversing the graph.

• If no path exists, set the answer to -1.

• Return the array of shortest path lengths for each node.
Answered by AI
Add your answer
Q2. 
Spell Checker Problem Statement
You are provided with a list of strings, DICTIONARY[], representing the correct spellings of words, and a query string QUERY that may contain misspelled words. Your task is...read more
Ans. 
Given a list of correct spellings and a query string, return a list of suggestions if the query is misspelled.
• Iterate through the dictionary and check for matches with the query string using a prefix search algorithm.

• Return a list of suggestions if the query is misspelled, otherwise return an empty list.

• Handle multiple test cases by looping through each case and performing the spell check operation.
Answered by AI
Add your answer
Q3. 
The Skyline Problem
Compute the skyline of given rectangular buildings in a 2D city, eliminating hidden lines and forming the outer contour of the silhouette when viewed from a distance. Each building is ...read more
Ans. 
Compute the skyline of given rectangular buildings in a 2D city, eliminating hidden lines and forming the outer contour of the silhouette.
• Iterate through the buildings and create a list of critical points (x, y) where the height changes.

• Sort the critical points based on x-coordinate and process them to form the skyline.

• Merge consecutive horizontal segments of equal height into one to ensure no duplicates in the output.
Answered by AI
Add your answer

Round duration - 45 minutes
Round difficulty - Medium

The interview was with a Korean employee. 

Q1. 
Bridge in Graph Problem Statement
Given an undirected graph with V vertices and E edges, your task is to find all the bridges in this graph. A bridge is an edge that, when removed, increases the number of...read more
Ans. 
Find all the bridges in an undirected graph.
• Use Tarjan's algorithm to find bridges in the graph.

• A bridge is an edge whose removal increases the number of connected components.

• Check for bridges by removing each edge and checking the number of connected components.

• Return the edges that are bridges in non-decreasing order.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Medium

Interviewer was an Indian employee. 

Q1. 
Longest Palindromic Substring Problem Statement
You are provided with a string STR of length N. The goal is to identify the longest palindromic substring within this string. In cases where multiple palind...read more
Ans. 
Identify the longest palindromic substring in a given string.
• Iterate through the string and expand around each character to find palindromes

• Keep track of the longest palindrome found

• Return the longest palindrome with the smallest start index
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee.

Q1. 
Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictiona...read more
Ans. 
Given a sorted alien dictionary in an array of strings, determine the character order of the alien language.
• Iterate through the words in the dictionary to build a graph of character dependencies.

• Perform a topological sort on the graph to determine the character order.

• Return the character order as a list of characters.
Answered by AI
Add your answer

Round duration - 45 Minutes
Round difficulty - Hard

Interviewer was an Indian employee. 

Q1. 
Problem: Ninja's Robot
The Ninja has a robot which navigates an infinite number line starting at position 0 with an initial speed of +1. The robot follows a set of instructions which includes ‘A’ (Acceler...read more
Ans. 
Determine the minimum length of instruction sequence for a robot to reach a given target on an infinite number line.
• Start at position 0 with speed +1, update position and speed based on 'A' and 'R' instructions

• For each test case, find the shortest sequence of instructions to reach the target

• Consider both positive and negative positions for the robot
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Round duration - 90 minutes
Round difficulty - Easy

Q1. 
Alien Dictionary Problem Statement
You are provided with a sorted dictionary (by lexical order) in an alien language. Your task is to determine the character order of the alien language from this dictiona...read more
Ans. 
Given a sorted alien dictionary, determine the character order of the alien language.
• Create a graph data structure to represent the relationships between characters based on the given dictionary.

• Perform a topological sort on the graph to determine the character order of the alien language.

• Return the character array obtained from the topological sort as the final output.
Answered by AI
Add your answer
Q2. 
Shopping Spree Problem Statement
Preeti plans to shop for her father's birthday at a store with unlimited quantities of N different items. She has a budget that allows her to buy a maximum of K items. Hel...read more
Ans. 
Calculate the number of ways Preeti can purchase items within budget, considering distinct ways.
• Use dynamic programming to calculate the number of ways to purchase items within budget

• Consider different scenarios where Preeti buys different quantities of each item

• Return the result modulo 10^9 + 7 to handle large answers
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Basic DBMS problems.

Round duration - 30 Minutes
Round difficulty - Easy

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

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 Stair Problem Statement
You are provided with a number of stairs, and initially, you are located at the 0th stair. You need to reach the Nth stair, and you can climb one or tw...read more
Ans. 
Count the number of distinct ways to climb to the Nth stair by climbing one or two steps at a time.
• Use dynamic programming to solve the problem efficiently.

• The number of ways to reach the Nth stair is the sum of the number of ways to reach the (N-1)th stair and the (N-2)th stair.

• Handle base cases where N=0 and N=1 separately.

• Apply modulo 10^9+7 to avoid overflow in the final result.
Answered by AI
Add your answer

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 Problem Statement
Your task is to find the total count of special numbers within a range from 1 to a given integer, 'MAXVAL'. A special number is defined as a number whose digits, when rot...read more
Ans. 
Count the total number of special numbers within a given range by rotating digits 180 degrees.
• Create a function to check if a number is a special number by rotating its digits.

• Iterate through the range from 1 to MAXVAL and count the special numbers.

• Handle the digit rotation mapping for 0, 1, 6, 8, 9.

• Return the count of special numbers for each test case.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

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

Round duration - 60 Minutes
Round difficulty - Easy

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

Q1. 
Covid Vaccination Distribution Problem
As the Government ramps up vaccination drives to combat the second wave of Covid-19, you are tasked with helping plan an effective vaccination schedule. Your goal is...read more
Ans. 
Given constraints, find max vaccines administered on a specific day during a vaccination drive.
• Iterate through each test case and calculate the maximum number of vaccines distributed on the specified day.

• Distribute vaccines evenly across days while maximizing the number on the specified day.

• Ensure that the sum of vaccines administered does not exceed the maximum allowed.

• Consider edge cases like when the number of days ...read more
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Another On-site ( DS & Algo) interview.

Q1. 
Painter's Partition Problem Statement
Given an array/list representing boards, where each element denotes the length of a board, and a number ‘K’ of available painters, determine the minimum time required...read more
Ans. 
Determine the minimum time required to paint all boards with given constraints.
• Use binary search to find the minimum and maximum possible time to paint all boards.

• Iterate through the boards and assign them to painters based on the time constraints.

• Calculate the total time taken to paint all boards with the assigned painters.
Answered by AI
View 1 more answer
Q2. 
Chocolate Distribution Problem
You are given an array/list CHOCOLATES of size 'N', where each element represents the number of chocolates in a packet. Your task is to distribute these chocolates among 'M'...read more
Ans. 
Distribute chocolates among students to minimize the difference between the largest and smallest number of chocolates.
• Sort the array of chocolates.

• Use sliding window technique to find the minimum difference between the largest and smallest number of chocolates.

• Return the minimum difference as the output.
Answered by AI
Add your answer

Round duration - 60 Minutes
Round difficulty - Easy

Another On-site ( DS & Algo) interview.

Q1. 
Problem Statement: Minimize the Maximum
You are given an array of integers and an integer K. For each array element, you can adjust it by increasing or decreasing it by a value of K. Your goal is to minim...read more
Ans. 
Given an array of integers and an integer K, minimize the difference between the maximum and minimum elements after adjusting each element by +/- K.
• Sort the array in non-decreasing order.

• For each element, calculate the difference between the current element and the next element.

• Adjust the element by adding or subtracting K to minimize the difference.

• Return the minimum possible difference between the maximum and minimum
Answered by AI
Add your answer

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 Problem Statement
Given a binary square matrix 'ARR' with 'N' rows and 'N' columns, where '0' represents water and '1' represents land.
Determine the water cell whose distanc...read more
Ans. 
Find the water cell farthest from land in a binary matrix using Manhattan distance.
• Iterate through the matrix to find all land cells and water cells

• Calculate the Manhattan distance of each water cell to the nearest land cell

• Return the maximum distance found
Answered by AI
Add your answer