50+ Goldman Sachs Software Developer Intern Interview Questions and Answers

Replace each node in a binary tree with its depth starting from root as 0.

• Traverse the binary tree in inorder fashion and update each node's data with its depth.

• Start with depth 0 for the root node and increment the depth as you go down the tree.

• Handle cases where nodes do not have left or right child by taking -1 in their place.

• Print the inorder traversal of the tree with updated node data representing the depth.

Find the longest palindromic substring in a given string, returning the rightmost one if multiple substrings are of the same length.

• Use dynamic programming to check for palindromes within the string.

• Start by checking for palindromes of length 1 and 2, then expand to longer substrings.

• Keep track of the longest palindromic substring found so far and return the rightmost one if multiple substrings are of the same length.

Count the number of positive integral pairs (X, Y) that satisfy the given equation.

• Iterate through all possible values of X and calculate corresponding Y to check if the equation is satisfied.

• Optimize the solution by considering the constraints and properties of the equation.

• Handle special cases like when N is 1 or when X and Y are equal.

• Use mathematical properties to reduce the number of calculations needed.

• Consider edge cases like when N is a prime number.

The task is to find the shortest path of transformed 0s that connects two islands in a binary matrix.

• Identify the two islands in the binary matrix.

• Find the shortest path between the two islands by converting 0s to 1s.

• Output the minimal length of the bridge needed to connect the two islands.

Given a binary matrix, maximize the score by toggling rows or columns to convert them to binary numbers and summing them up.

• Iterate through each row and column to calculate the score of toggling that row or column

• Keep track of the maximum score obtained by toggling rows or columns

• Return the maximum score obtained

Implement a function to solve a Sudoku puzzle by filling empty cells with valid numbers.

• Iterate through each empty cell and try filling it with a valid number (1-9) that satisfies Sudoku rules.

• Use backtracking to backtrack and try different numbers if a cell cannot be filled with a valid number.

• Check rows, columns, and 3x3 sub-grids to ensure each digit appears only once in each.

• Recursively solve the puzzle by filling empty cells until a valid solution is found.

Given a string with wildcard characters, determine if it can be transformed to match another string under given rules.

• Iterate through both strings simultaneously, handling wildcard characters '?' and '*' accordingly.

• Use dynamic programming to keep track of matching characters.

• Handle '*' by considering all possibilities of matching sequences.

• Return true if at the end both strings match, false otherwise.

Group anagrams together in a list of strings.

• Iterate through the list of strings and sort each string to group anagrams together.

• Use a hashmap to store the sorted string as key and the original string as value.

• Return the values of the hashmap as the grouped anagrams.

Given 'N' types of umbrellas with different capacities, find the minimum number of umbrellas required to shelter exactly 'M' people.

• Iterate through the umbrella capacities and try to cover 'M' people using the minimum number of umbrellas.

• Sort the umbrella capacities in descending order to optimize the solution.

• If it is not possible to cover 'M' people exactly, return -1.

Convert a given integer number into its corresponding word representation.

• Implement a function that takes an integer as input and returns the word representation of the number in English lowercase letters.

• Break down the number into its individual digits and convert each digit into its corresponding word form.

• Handle special cases like numbers between 10 and 19, multiples of 10, and numbers with zeros in between.

• Concatenate the word forms of individual digits to form the final ...read more

The task is to distribute candies to students based on their performance while minimizing the total candies distributed.

• Create an array to store the minimum candies required for each student.

• Iterate through the students' ratings array to determine the minimum candies needed based on the adjacent ratings.

• Consider both left-to-right and right-to-left passes to ensure fair distribution.

• Keep track of the total candies distributed and return the sum as the output.

Level order traversal of a binary tree is returned for each test case.

• Implement a function to perform level order traversal of a binary tree

• Use a queue data structure to keep track of nodes at each level

• Print the node values in level order traversal

Given finish times of horses, find fastest horse in specified lane ranges for multiple queries.

• Iterate through each query and find the minimum finish time within the specified range.

• Use a loop to process each test case and query efficiently.

• Ensure to handle edge cases like empty ranges or invalid inputs.

• Optimize the solution to handle large input sizes efficiently.

Implement a function to determine a player's leaderboard rank for each game score.

• Iterate through the game scores and compare them with the leaderboard scores to determine the rank.

• Handle cases where players have identical scores by assigning them the same rank.

• Ensure the leaderboard scores are in descending order and game scores are in ascending order.

• Return the ranks for each game score in an array.

Flatten a multi-level linked list into a singly linked list and return the head of the flattened list.

• Traverse the linked list in level order

• Use a stack to keep track of nodes with child pointers

• Merge the child nodes into the main list

Identify the celebrity at a party where one person knows everyone but is not known by anyone.

• Use a two-pointer approach to eliminate non-celebrities.

• Start with two pointers at the beginning and end, move them based on 'knows' results.

• If A knows B, A cannot be the celebrity; move A pointer. If A does not know B, B cannot be the celebrity; move B pointer.

• Repeat until only one person remains, check if this person is known by everyone and knows no one.

• Return the ID of the celebri...read more

Design a HashSet data structure with add, contains, and remove functions.

• Implement a HashSet using an array of linked lists to handle collisions.

• Use a hash function to determine the index in the array for each element.

• For add function, check if the element already exists before inserting.

• For contains function, search for the element in the corresponding linked list.

• For remove function, find and remove the element from the linked list.

• Example: If Q=5, queries are [(1, 5), (2, ...read more

The task is to find the smallest number greater than the given number with the same set of digits.

• Iterate from right to left to find the first digit that can be swapped with a smaller digit to make the number greater.

• Swap this digit with the smallest digit to its right that is greater than it.

• Sort all digits to the right of the swapped digit in ascending order to get the smallest number.

Find the maximum sum of non-adjacent nodes in a binary tree.

• Use dynamic programming to keep track of the maximum sum at each node considering whether to include or exclude the current node.

• Recursively traverse the binary tree while keeping track of the maximum sum of non-adjacent nodes.

• Consider the cases where the current node is included in the sum or excluded from the sum to calculate the maximum possible sum.

Validate if a given binary tree is a Binary Search Tree (BST) or not.

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

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

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For a node with data 4, left subtree nodes should be less than 4 and right subtree nodes should be greater than 4.

Merge overlapping intervals and return sorted list of merged intervals.

• Identify overlapping intervals based on start and end times

• Merge overlapping intervals to form new intervals

• Sort the merged intervals in ascending order of start times

Given a string, find the longest palindromic substring, prioritizing the one with the smallest start index.

• Iterate through the string and expand around each character to find palindromes.

• Keep track of the longest palindrome found and its starting index.

• Return the longest palindromic substring with the smallest start index.

Sort an array of strings based on a new alphabetical order starting with a given character.

• Iterate through the array of strings and compare each string with the given character to determine the new order.

• Use a custom comparator function to sort the strings based on the new alphabetical order.

• Handle lowercase English alphabet characters and strings of varying lengths.

Compute the area of the largest rectangle that can be formed within the bounds of a given histogram.

• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle by considering the current height as the height of the rectangle and the width as the difference between the current index and the index at the top of the stack.

• Update the maximum area found so far and return it as the result.

Find the smallest substring in a given string that contains all characters from another string.

• Use a sliding window approach to find the smallest window in S that contains all characters in X.

• Keep track of the characters in X using a hashmap.

• Move the right pointer to expand the window until all characters in X are found, then move the left pointer to shrink the window while maintaining the condition.

• Return the smallest window found.

• Example: S = 'abdd', X = 'bd' -> Output: 'bd...read more

Determine if two nodes in a binary tree are cousins based on level and parent criteria.

• Traverse the tree to find the levels and parents of the given nodes.

• Check if the nodes are at the same level and have different parents.

• Return 'YES' if the nodes are cousins, 'NO' otherwise.

Count distinct pairs in an array whose sum equals a given target.

• Use two pointers approach to iterate through the array and find pairs with sum equal to target.

• Keep track of visited elements to avoid counting duplicate pairs.

• Return -1 if no such pair exists with the given target.

Reverse a linked list in groups of size K.

• Iterate through the linked list in groups of size K

• Reverse each group of nodes

• Handle cases where the number of elements in the last group is less than K

Calculate total area covered by overlapping rectangles given their coordinates.

• Iterate through each rectangle and calculate its area

• Check for overlaps between rectangles and calculate the overlapping area

• Sum up the areas of all rectangles and subtract the total overlapping area to get the final 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.

• Iterate through each denomination and update the array accordingly.

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

• Example: For N=3, D=[1, 2, 3], V=4, the output is 4 as there are 4 ways to make change for...read more

Count the total number of unique pairs in an array whose elements sum up to a given value.

• Use a hashmap to store the frequency of each element in the array.

• Iterate through the array and for each element, check if (Sum - element) exists in the hashmap.

• Increment the count of pairs if the complement exists in the hashmap.

Find the Lowest Common Ancestor (LCA) of two nodes in a Binary Search Tree (BST).

• Traverse the BST from the root node to find the LCA of nodes P and Q.

• Compare the values of nodes P and Q with the current node's value to determine the LCA.

• If both nodes are on the same side of the current node, move to that side; otherwise, the current node is the LCA.

• Handle cases where one node is the ancestor of the other or when one of the nodes is the current node.

The minimum number of swaps required to sort a given array of distinct elements in ascending order.

• Use a graph-based approach to find cycles in the array

• Count the number of swaps needed to fix each cycle

• Sum up the swaps needed for all cycles to get the total minimum swaps

Find the number of ways a given number can be expressed as the sum of two or more consecutive natural numbers.

• Use a sliding window approach to iterate through all possible consecutive sums.

• Keep track of the sum of the current window and adjust the window size accordingly.

• Count the number of valid consecutive sum representations of the given number.

• Example: For N = 9, valid representations are 2 + 3 + 4 and 4 + 5, so the output is 2.

Return the middle element of a singly linked list, or the one farther from the head if there are even elements.

• Traverse the linked list with two pointers, one moving twice as fast as the other

• When the fast pointer reaches the end, the slow pointer will be at the middle

• If there are even elements, return the one that is farther from the head node

• Handle edge cases like linked list of size 1 or empty list

Rearrange nodes in a singly linked list by grouping odd and even indices together while maintaining relative order.

• Create two separate linked lists for odd and even nodes

• Traverse the original list and append nodes to respective odd/even lists

• Connect the last node of odd list to the head of even list

• Return the head of the rearranged list

Given a string representing an Excel column title, determine the corresponding column number.

• Iterate through the characters of the string from right to left

• Calculate the corresponding value of each character based on its position and multiply by 26^position

• Sum up all the values to get the final column number

The total number of unique rectangles that can be formed in a grid with M rows and N columns.

• The total number of unique rectangles can be calculated using the formula: (M * (M + 1) / 2) * (N * (N + 1) / 2)

• Each rectangle can be formed by selecting two rows and two columns from the grid

• For example, for a grid with 3 rows and 4 columns, the total number of unique rectangles is 60

Check if two binary trees are mirrors of each other based on specific criteria.

• Compare the roots of both trees.

• Check if the left subtree of the first tree is the mirror of the right subtree of the second tree.

• Verify if the right subtree of the first tree is the mirror of the left subtree of the second tree.

The task is to connect houses at the same level in a binary tree structure using 'next' pointers.

• Traverse the binary tree level by level using BFS

• Connect nodes at the same level using 'next' pointers

• Use a queue to keep track of nodes at each level

Calculate the rank of a matrix based on the number of linearly independent column or row vectors.

• Determine the rank of the matrix by finding the maximum number of linearly independent column vectors or row vectors.

• Check for linear independence by verifying if there is a nontrivial linear combination that equates to the zero vector.

• Implement a function that takes the matrix dimensions and elements as input and returns the rank of the matrix.

Count the number of triangles in an undirected graph using adjacency matrix.

• Iterate through all possible triplets of vertices to check for triangles.

• For each triplet, check if there are edges between all three vertices.

• Increment the count if a triangle is found.

• Return the total count of triangles for each test case.

Find the maximum value of an equation involving coordinates of points in a 2D plane.

• Iterate through all pairs of points and calculate the equation value

• Keep track of the maximum value encountered

• Consider the constraint |xi - xj| ≤ K while calculating the equation value

The task is to determine the maximum profit that can be achieved by performing up to two buy-and-sell transactions on a given set of stock prices.

• Iterate through the array of stock prices and calculate the maximum profit that can be achieved by buying and selling at different points.

• Keep track of the maximum profit after the first transaction and the maximum profit overall by considering different combinations of buy and sell points.

• Consider edge cases where the stock prices ...read more

Search for integers in a rotated sorted array efficiently.

• Use binary search to find the pivot point where the array is rotated.

• Based on the pivot point, apply binary search on the appropriate half of the array.

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

• Example: For input N=5, A=[4, 5, 6, 7, 0, 1, 2], Q=3, Q[i]=[0, 3, 6], output should be 4, -1, 2.

Rearrange words in a sentence based on increasing order of their length.

• Split the sentence into words and calculate the length of each word.

• Sort the words based on their lengths, keeping the original order for words with the same length.

• Join the sorted words back into a sentence.

Convert Excel column title to corresponding column number.

• Map each letter to its corresponding value (A=1, B=2, ..., Z=26)

• Iterate through the input string from right to left, calculate the value of each letter based on its position and add it to the result

• Multiply the result by 26 for each additional letter to the left

Given a string, find and return the first non-repeating character. If none exists, return the first character of the string.

• Create a dictionary to store the count of each character in the string.

• Iterate through the string and populate the dictionary.

• Iterate through the string again and return the first character with count 1.

• If no such character exists, return the first character of the string.

Given the area of a rectangle, find the length and breadth such that the length is greater than the breadth and the difference between them is minimized.

• Iterate through possible combinations of length and breadth

• Calculate the area for each combination and check if length is greater than breadth

• Select the combination with minimal difference between length and breadth