30+ Google Software Developer Intern Interview Questions and Answers

Given a sequence of room bookings and freeings, find the room that is booked the most times.

• Create a hashmap to store the count of each room booking.

• Iterate through the sequence of bookings and freeings, updating the count in the hashmap.

• Find the room with the highest count and return it. In case of a tie, return the lexicographically smaller room.

• Example: For input n = 6, Arr[] = {"+1A", "+3E", "-1A", "+4F", "+1A", "-3E"}, the output would be "1A".

Given an array, remove K elements from beginning or end to maximize sum of remaining elements.

• Iterate through all possible combinations of removing K elements from beginning and end

• Calculate sum of remaining elements for each combination

• Return the maximum sum obtained

Assign subjects to friends to minimize maximum workload, find minimum time for most loaded friend.

• Sort subjects in descending order

• Assign subjects to friends one by one until all subjects are assigned

• The maximum workload will be the sum of problems assigned to the friend with the most problems

• Return the maximum workload as the minimum time required

Calculate and print the sum of least common multiples (LCM) for each integer from 1 to N with N.

• Iterate from 1 to N and calculate LCM of each number with N

• Sum up all the calculated LCMs to get the final result

• Implement a function to calculate LCM of two numbers

Find the path from a leaf node to the root node in a binary tree with the maximum sum.

• Traverse the binary tree from leaf to root while keeping track of the sum along the path.

• Compare the sums of all root-to-leaf paths and return the path with the maximum sum.

• Use recursion to traverse the tree efficiently and update the sum as you go.

• Consider edge cases like null nodes and negative values in the tree.

BFS traversal of an undirected and disconnected graph starting from vertex 0.

• Implement BFS algorithm to traverse the graph starting from vertex 0.

• Use a queue to keep track of visited nodes and their neighbors.

• Ensure to print the nodes in numerical sort order when multiple neighbors are present.

• Handle disconnected components by checking for unvisited nodes.

• Output the BFS traversal sequence for each test case in a separate line.

Delete all leaf nodes with value X in a binary tree until no such leaves exist.

• Traverse the tree in postorder fashion to delete leaf nodes with value X

• Recursively call the function on left and right subtrees

• Update the root of the tree after removing leaf nodes with value X

Given a string representing time with some digits as '?', fill in '?' to get maximum time.

• Iterate through each digit of the input string and replace '?' with the maximum possible digit based on the position.

• For the first digit (hours), if it is '?', replace it with '2' if the second digit is also '?', else replace it with '1'.

• For the second digit (hours), if it is '?', replace it with '3' if the first digit is '2', else replace it with '9'.

• For the third digit (minutes), if it...read more

Calculate sum of bit differences among all pairs in an array of integers.

• Iterate through all pairs of elements in the array

• Convert each pair of elements to binary representation

• Count the differing bits in the binary representations

• Sum up the differing bits for all pairs to get the final result

Search for integers in a rotated sorted array efficiently using binary search.

• Use binary search to efficiently find the index of each query integer in the rotated sorted array.

• Handle the rotation of the array by finding the pivot point first.

• Check which half of the array the query integer falls into based on the pivot point.

• Return the index of the query integer if found, else return -1.

Implement a function to find the minimum steps to reduce a positive integer to 1 using given operations.

• Use dynamic programming to store the minimum steps for each number from 1 to N.

• Iterate through each number from 1 to N and calculate the minimum steps based on the given operations.

• Consider the cases where N is divisible by 2 or 3, and also when subtracting 1 is the only option.

• Return the minimum steps required to reduce N to 1.

Determine the number of good quality bulbs remaining after 'N' rounds of a unique technique.

• In each round, bulbs are toggled based on their position (e.g. every second bulb, every third bulb, etc.)

• At the end of 'N' rounds, count the bulbs that remain on to determine the number of good quality bulbs.

• Example: For N = 4, bulbs 1 and 4 remain on, so the output is 2.

Given a dictionary and queries with wildcard characters, determine how many words in the dictionary can match each query.

• Iterate through each query and dictionary word to check for matches

• Replace '?' with all possible lowercase letters and compare with dictionary words

• Count the number of matches for each query

Find the size of the smallest subset with maximum OR value among all subsets of an array of positive integers.

• Iterate through all possible subsets of the array

• Calculate the OR value for each subset

• Track the size of the smallest subset with maximum OR value

The problem involves finding the number of distinct ways to climb N stairs by taking 1 or 2 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 for N=0 and N=1 separately.

• Consider using modulo operation to avoid overflow for large values of N.

Given a singly linked list of integers and a reference to a node, delete the specified node from the linked list.

• Traverse the linked list to find the node to be deleted.

• Update the pointers to skip over the node to be deleted.

• Print the modified linked list after deletion.

• Ensure the node to be deleted is not the tail node.

Find the maximum sum of a contiguous subarray within an array of integers.

• Use Kadane's algorithm to find the maximum subarray sum efficiently.

• Initialize two variables: maxEndingHere and maxSoFar.

• Iterate through the array and update the variables accordingly.

• Return the maxSoFar as the result.

The task is to find the total number of ways to make change for a specified value using given denominations.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of ways to make change for each value up to the specified value.

• Initialize the array with base cases and then iterate through the denominations to fill up the array.

• The final answer will be in the last cell of the array.

• Example: For N=3, D=[1, 2, 3], V=4, the output should be...read more

Find all possible paths for a rat in a maze to reach its destination, given a matrix representation of the maze.

• Use backtracking to explore all possible paths from the starting position to the destination.

• Keep track of the current path and explore all possible directions at each step.

• Terminate the exploration when reaching the destination and add the path to the result list.

• Sort the result list of paths in alphabetical order before returning.

Count distinct values obtained by applying bitwise OR operation on all possible subarrays of an array of positive integers.

• Use a set to store distinct values obtained by bitwise OR operation on all subarrays.

• Iterate through all subarrays efficiently to calculate distinct values.

• Optimize the solution to handle large input sizes efficiently.

House Robber problem - determine maximum amount of money to rob without triggering alarm in circular arrangement of houses.

• Use dynamic programming to keep track of maximum money robbed at each house.

• Consider two cases: robbing the first house and not robbing the first house.

• Handle circular arrangement by considering the first and last house separately.

• Example: For arr[] = {2, 3, 2}, the output is 3. Mr. X robs house 2.

• Example: For arr[] = {1, 2, 3, 1}, the output is 4. Mr. X ...read more

Validate if a binary tree is a Binary Search Tree (BST) based on given properties.

• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Verify if the right subtree of a node contains only nodes with data greater than the node's data.

• Ensure that both the left and right subtrees are also binary search trees.

• Traverse the tree in level order form to validate the BST properties.

• Return true if the binary tree is a BST, otherwise return false.

The problem involves finding the maximum element in each sliding window of size 'K' in an array of integers.

• Use a deque to store indices of elements in the current window in decreasing order of their values.

• Remove indices that are out of the current window from the front of the deque.

• Add the maximum element (at the front of the deque) to the result for each window.

Implement a Sudoku solver for a 9x9 grid with constraints on row, column, and 3x3 grid.

• Create a recursive function to solve the Sudoku puzzle by trying out different numbers in empty slots.

• Use backtracking to backtrack and try different numbers if a conflict is encountered.

• Ensure each number appears only once in each row, column, and 3x3 grid.

• Implement a function to check if a number can be placed in a particular position based on Sudoku rules.

• Test the solver with different S...read more

Count the number of palindrome words in a given string.

• Split the string into words using whitespace as delimiter.

• Check each word if it is a palindrome by comparing it with its reverse.

• Increment a counter for each palindrome word found.

• Output the final count of palindrome words for each test case.