Google Center Head Interview Questions and Answers

Round duration - 180 minutes
Round difficulty - Medium

The online test consisted of 2 coding questions, 30 aptitude MCQs, 30 behavioral MCQs and 10 code snippets to debug. The coding questions were of medium level, aptitude MCQs were easy and the code snippets to debug was also of easy level. Each section had a time constraint.

Q1. 
Merge Two Sorted Linked Lists Problem Statement
You are provided with two sorted linked lists. Your task is to merge them into a single sorted linked list and return the head of the combined linked list.
...read more
Ans. 
Merge two sorted linked lists into a single sorted linked list without using additional space beyond constant space complexity.
• Create a dummy node to start the merged list

• Iterate through both linked lists and compare nodes to merge them in sorted order

• Update the next pointers accordingly

• Handle cases where one list is empty or both lists are empty

• Return the head of the merged linked list
Answered by AI
Add your answer
Q2. 
Minimum Path Sum Problem Statement
Consider a 2-dimensional grid 'GRID' with 'N' rows and 'M' columns in Ninjaland. Each cell in the grid has an associated cost. The goal is to determine the minimum path ...read more
Ans. 
The Minimum Path Sum Problem involves finding the minimum sum of costs along a path from the top-left to the bottom-right of a grid.
• Use dynamic programming to calculate the minimum path sum by considering the costs of moving down or right at each cell.

• Initialize a 2D array to store the minimum path sum values for each cell in the grid.

• Iterate through the grid to calculate the minimum path sum for each cell based on the...read more
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

My interview was at 9:00 am. The interview was conducted on Amazon Chime and my webcam was on. The interviewer also asked me to write the code on a document which can be edited by both me and the interviewer. The difficulty of the questions was of medium level. I was asked 3 coding questions along with 2 questions related to OOPS at the end. The interview ended with the discussion of one of my projects. The interviewer was good and also gave me hints wherever required.

Q1. 
Palindrome Partitioning Problem Statement
You are given a string S. Your task is to partition S such that every substring of the partition is a palindrome. Your objective is to return all possible palindr...read more
Ans. 
Given a string, partition it into palindromes and return all possible configurations.
• Use backtracking to generate all possible palindrome partitions

• Check if each substring is a palindrome before adding it to the partition

• Return all valid partitions as an array of strings
Answered by AI
Add your answer
Q2. 
Longest Increasing Subsequence Problem Statement
Given an array of integers with 'N' elements, determine the length of the longest subsequence where each element is greater than the previous element. This...read more
Ans. 
Find the length of the longest strictly increasing subsequence in an array of integers.
• Use dynamic programming to solve this problem efficiently.

• Initialize an array to store the length of the longest increasing subsequence ending at each index.

• Iterate through the array and update the length of the longest increasing subsequence for each element.

• Return the maximum value in the array as the result.
Answered by AI
Add your answer
Q3. 
Find Missing Number In String Problem Statement
You have a sequence of consecutive nonnegative integers. By appending all integers end-to-end, you formed a string S without any separators. During this pro...read more
Ans. 
Find the missing number in a string of consecutive nonnegative integers.
• Iterate through the string and check for missing numbers by comparing adjacent integers

• If a missing number is found, return it as the output

• Handle cases where there are multiple missing numbers or the string is invalid by returning -1
Answered by AI
Add your answer
Q4. What are the ACID properties in DBMS?
Ans. 
ACID properties in DBMS ensure data integrity and consistency.
• Atomicity: All operations in a transaction are treated as a single unit of work, either all succeed or all fail.

• Consistency: Database remains in a consistent state before and after the transaction.

• Isolation: Transactions are isolated from each other until they are completed.

• Durability: Once a transaction is committed, the changes made by it are permanent and...read more
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This was MCQ+Coding round.

Q1. How can you check if two strings are anagrams of each other?
Ans. 
Check if two strings are anagrams by comparing the sorted versions of the strings.
• Sort both strings and compare if they are equal.

• Use a hashmap to store the frequency of characters in each string and compare the maps.

• Ignore spaces and punctuation when comparing the strings.
Answered by AI
Add your answer

Round duration - 90 minutes
Round difficulty - Easy

This was face to face interview round.

Round duration - 90 minutes
Round difficulty - Easy

This was face to face interview round.

Round duration - 90 Minutes
Round difficulty - Medium

Interview started at 11:00 am. It was an online round. During the coding round I submitted optimized solution and got full acceptance of the solutions.

Q1. 
Detect Cycle in a Directed Graph
You are provided with a directed graph composed of 'N' nodes. You have a matrix called 'EDGES' with dimensions M x 2, which specifies the 'M' edges in the graph. Each edge...read more
Ans. 
Detect cycle in a directed graph using depth-first search (DFS) algorithm.
• Use DFS to traverse the graph and detect back edges indicating a cycle.

• Maintain a visited array to keep track of visited nodes during traversal.

• If a node is visited again during traversal and it is not the parent node, then a cycle exists.

• Return true if a cycle is detected, false otherwise.
Answered by AI
Add your answer

Round duration - 80 Minutes
Round difficulty - Medium

Interview started at 10:00 am. Interview went well, I was able to connect with the interviewer and enjoyed the whole interview

Q1. 
Next Smallest Palindrome Problem Statement
Find the next smallest palindrome strictly greater than a given number 'N' represented as a string 'S'.
Explanation:
You are given a number in string format, a...read more
Ans. 
Find the next smallest palindrome greater than a given number represented as a string.
• Convert the string to an integer, find the next greater palindrome, and convert it back to a string.

• Handle cases where the number is a palindrome or has all digits as '9'.

• Consider both odd and even length numbers when finding the next palindrome.
Answered by AI
Add your answer

Round duration - 80 Minutes
Round difficulty - Medium

Interview started at 11:00 am. Interview went well.

Q1. 
Boundary Traversal of a Binary Tree
Given a binary tree of integers, your task is to return the boundary nodes of the tree in Anti-Clockwise direction starting from the root node.
Input:
The first line ...read more
Ans. 
Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.
• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Handle cases where duplicates occur in the boundary nodes

• Implement the function without printing as printing is already managed
Answered by AI
Add your answer

Round duration - 120 minutes
Round difficulty - Medium

Evening test around 5
Platform :- SHL
Environment was amazing

Q1. 
Subtree of Another Tree Problem Statement
Given two binary trees, T and S, determine whether S is a subtree of T. The tree S should have the same structure and node values as a subtree of T.
Explanation:
...read more
Ans. 
Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.
• Check if the second tree is a subtree of the first tree by comparing their structures and node values.

• Use a recursive approach to traverse both trees and check for equality.

• Handle cases where one tree is null or the values do not match.

• Return true if S is a subtree of T, false otherwise.
Answered by AI
Add your answer
Q2. 
Search in a Row-wise and Column-wise Sorted Matrix Problem Statement
You are given an N * N matrix of integers where each row and each column is sorted in increasing order. Your task is to find the positi...read more
Ans. 
Given a sorted N*N matrix, find the position of a target integer X.
• Iterate over each row and column to find the target integer X

• Utilize the sorted nature of the matrix to optimize the search process

• Return the position of X if found, else return -1 -1
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

1 Hour 
Afternoon

Q1. 
Intersection of Linked List Problem
You are provided with two singly linked lists containing integers, where both lists converge at some node belonging to a third linked list.
Your task is to determine t...read more
Ans. 
Find the node where two linked lists merge, return -1 if no merging occurs.
• Traverse both lists to find their lengths and the difference in lengths

• Move the pointer of the longer list by the difference in lengths

• Traverse both lists simultaneously until they meet at the merging point
Answered by AI
Add your answer
Q2. 
Problem: Pair Sum in a Binary Search Tree
Given a Binary Search Tree (BST) and an integer 'S', your task is to find all pairs of nodes within the BST that total to 'S' and return these pairs. If no such p...read more
Ans. 
Find pairs of nodes in a BST that sum up to a given value 'S'.
• Traverse the BST in-order to get a sorted list of nodes.

• Use two pointers approach to find pairs with sum 'S'.

• Keep track of visited nodes to avoid using the same node twice in a pair.
Answered by AI
Add your answer

Round duration - 60 minutes
Round difficulty - Medium

Online Round held on Chime

Q1. 
Is Binary Heap Tree Problem Statement
You are given a binary tree of integers. Your task is to determine if it is a binary heap tree or not.
Input:
The first line of input contains an integer ‘T’ denoti...read more
Ans. 
Determine if a given binary tree is a binary heap tree or not based on certain properties.
• Check if the binary tree is a complete binary tree where every level, except the last level, is completely filled and the last level is as far left as possible.

• Ensure that every parent node is greater than all its children nodes, forming a max-heap.

• If any node does not have a left or right child, it should be represented as -1 in
Answered by AI
Add your answer
Q2. 
Edit Distance Problem Statement
Given two strings S and T with lengths N and M respectively, your task is to find the "Edit Distance" between these strings.
The Edit Distance is defined as the minimum nu...read more
Ans. 
The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.
• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the edit distances between substrings of the two input strings.

• Fill up the array based on the minimum of three possible operations: insert, delete, or replace.

• The final answer will be the value at...read more
Answered by AI
Add your answer