200+ SDE-2 Interview Questions and Answers

Find the maximum sum submatrix in a given matrix.

• Iterate over all possible submatrices and calculate their sums

• Use Kadane's algorithm to find the maximum sum subarray in each row

• Combine the sums of rows to find the maximum sum submatrix

Given an array of digits, find the maximum number that can be achieved by performing at most one swap.

• Iterate through the array to find the maximum digit.

• If the maximum digit is already at the beginning, find the next maximum digit and swap them.

• If the maximum digit is not at the beginning, swap it with the digit at the beginning.

Find the largest area of a submatrix containing only 1's in a binary matrix.

• Iterate over each cell in the matrix and calculate the maximum area of submatrix with all 1's ending at that cell.

• Use dynamic programming to keep track of the maximum area ending at each cell.

• Update the maximum area as you iterate through the matrix.

• Return the overall maximum area found in the matrix.

Find median of integers in a data stream as they are read.

• Use two heaps - max heap for lower half of numbers and min heap for upper half.

• Keep the size of two heaps balanced to find the median efficiently.

• Handle even and odd number of elements separately to calculate median.

• Return vector of medians after each element is read from the stream.

Determine the maximum amount of money a thief can steal from houses without looting two consecutive houses.

• Use dynamic programming to keep track of the maximum money that can be stolen up to each house.

• At each house, the thief can either choose to steal from the current house or skip it and steal from the previous house.

• The maximum amount of money that can be stolen without looting two consecutive houses is the maximum of the two options.

Count the number of trailing zeros in the factorial of a given number.

• Count the number of factors of 5 in the factorial of the given number N.

• Divide N by 5, then by 25, then by 125, and so on, and sum up the quotients to get the total number of trailing zeros.

• Example: For N=10, 10/5=2, so there are 2 factors of 5 in 10!, hence 2 trailing zeros.

Find the best insert position for a target in a sorted array to maintain order.

• Use binary search to find the correct position for the target integer in the sorted array.

• If the target is already present in the array, return its index.

• Maintain the sorted order of the array after inserting the target integer.

• Handle edge cases like empty array or target being smaller than the first element or larger than the last element.

Flatten a multi-level linked list into a single linked list by rearranging the pointers.

• Traverse the linked list and whenever a node has a child, flatten the child list and append it after the current node.

• Update the 'next' and 'child' pointers accordingly while flattening the list.

• Continue this process until all nodes are rearranged into a single linked list.

House Robber problem - find maximum amount of money Mr. X can rob without triggering alarm in circular street.

• 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 houses separately.

• Return the maximum amount of money that can be robbed without triggering the alarm.

Find the minimum cost to reduce an array to one element by merging adjacent elements.

• Iterate through the array and merge adjacent elements with the smallest sum each time.

• Keep track of the total cost as you merge elements.

• Repeat the merging process until only one element remains in the array.

The task is to find the next greater element for each element in an array to its right, if no greater element exists, return -1.

• Use a stack to keep track of elements for which the next greater element is not found yet.

• Iterate through the array from right to left and pop elements from the stack until a greater element is found.

• Store the next greater element for each element in a separate array.

• If the stack is empty after iterating through the array, it means there is no greate...read more

Return all possible permutations of a given input string.

• Use recursion to generate all possible permutations of the input string.

• Swap characters at different positions to generate permutations.

• Handle duplicate characters by skipping swapping if the characters are the same.

Reverse the letters of a string while keeping non-alphabet characters in their original position.

• Iterate through the string and store the non-alphabet characters in their original positions.

• Reverse the letters of the string using two pointers approach.

• Combine the reversed letters with the non-alphabet characters to get the final reversed string.

The task is to find all distinct triplets in an array that sum up to a specified number.

• Iterate through all possible triplets using three nested loops.

• Check if the sum of the triplet equals the target sum.

• Print the triplet if found, else print -1.

Given a sentence and a dictionary, construct and return all possible sentences by inserting spaces to form words from the dictionary.

• Use backtracking to generate all possible combinations of words from the dictionary to form sentences.

• Check if a substring of the sentence matches any word in the dictionary, if so, recursively call the function with the remaining substring.

• Continue this process until the entire sentence is segmented into words from the dictionary.

• Return all val...read more

Find the equilibrium index of an array where sum of elements on left equals sum on right.

• Iterate through the array and calculate prefix sum and suffix sum at each index.

• Compare prefix sum and suffix sum to find equilibrium index.

• Return the left-most equilibrium index found.

The task is to print the left view of a binary tree, which contains the nodes visible when the tree is viewed from the left side.

• Traverse the tree level by level and keep track of the leftmost node at each level

• Use a queue for level order traversal and a map to store the leftmost nodes

• Print the values of the leftmost nodes stored in the map as the left view of the tree

Find the peak element in an array of integers.

• Iterate through the array and check if the current element is greater than its neighbors.

• Handle edge cases for the first and last elements of the array.

• Return the peak element found.

Given a string, select smallest character from first K characters, remove it, and append to new string until original string is empty.

• Iterate through the string, selecting the smallest character from the first K characters each time.

• Remove the selected character from the original string and append it to the new string.

• Repeat the process until the original string is empty.

• Return the final new string formed after the operations.

The Word Ladder problem involves finding the shortest transformation sequence from one word to another by changing one letter at a time.

• Use breadth-first search to find the shortest transformation sequence.

• Create a graph where each word is a node and edges connect words that differ by one letter.

• Keep track of visited words to avoid revisiting them.

• Return -1 if no transformation sequence is possible.

Convert a binary tree into its mirror tree by interchanging left and right children of non-leaf nodes.

• Traverse the tree in a recursive manner and swap the left and right children of each node.

• Use a temporary variable to swap the children of each node.

• Ensure to modify the tree in place without creating a new tree.

• Example: For the input tree 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, the mirror tree will have inorder traversal as 7 4 2 1 6 3 5.

Implement a function to find any topological sorting of a Directed Acyclic Graph (DAG).

• Use Depth First Search (DFS) to find the topological ordering of the vertices.

• Start by visiting a vertex and recursively visit its adjacent vertices before adding it to the result array.

• Maintain a visited array to keep track of visited vertices and avoid cycles.

• Once all vertices are visited, reverse the result array to get the topological sort.

• Example: For a DAG with edges 0->1, 0->3, 1->2,...read more

Check if the given string containing only parentheses is balanced or not.

• Use a stack to keep track of opening parentheses.

• Iterate through the string and push opening parentheses onto the stack.

• When a closing parenthesis is encountered, pop from the stack and check if it matches the corresponding opening parenthesis.

• If at the end the stack is empty, return 'YES' else return 'NO'.

Check if a given string is a palindrome or not.

• Iterate through the string from both ends and compare characters.

• If all characters match, return 1 indicating a palindrome.

• If any characters don't match, return 0 indicating not a palindrome.

Identify starting indices of anagram substrings of 'PTR' in 'STR'.

• Use a sliding window approach to check for anagrams of 'PTR' in 'STR'.

• Create a frequency map of characters in 'PTR' and 'STR' to compare.

• Slide the window along 'STR' and check if the frequency maps match.

• Return the starting indices where anagrams are found.

Determine if it is feasible to complete all courses with prerequisites.

• Create a graph representation of the courses and prerequisites.

• Check for cycles in the graph using topological sorting.

• If there are no cycles, all courses can be completed.

• Example: For input N=2, prerequisites=[[1, 2]], the output is 'Yes'.

Find and return the sum of all the left leaf nodes in a binary tree.

• Traverse the binary tree using depth-first search (DFS)

• Check if a node is a leaf node and a left child

• Sum up the values of all left leaf nodes

Find the length of the longest pair chain that can be formed using the provided pairs.

• Sort the pairs based on the second number in each pair.

• Iterate through the sorted pairs and keep track of the maximum chain length.

• Update the maximum chain length based on the conditions given in the problem statement.

Find the median of two sorted arrays by merging them and calculating the median of the combined array.

• Merge the two sorted arrays into one sorted array.

• Calculate the median of the combined array based on the total number of elements.

• Return the median as the result.

Return the middle node of a singly linked list, or the latter of the two middle nodes if the number of elements is even.

• 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 node.

• If the number of elements is even, return the latter of the two middle nodes.

• Handle cases where there is only one node or no midpoint exists.

Find the minimum cost to connect all sticks into one by joining two sticks at a time.

• Sort the array of stick lengths in non-decreasing order.

• Keep adding the two smallest sticks at a time to minimize cost.

• Repeat until all sticks are connected into one.

The minimum number of operations required to make all elements of the given array equal is calculated by finding the median of the array elements.

• Calculate the median of the array elements to determine the target value for all elements to be equal.

• Find the absolute difference between each element and the target value, sum these differences to get the minimum number of operations.

• For odd length arrays, the median is the middle element. For even length arrays, the median is the...read more

The problem is to determine if it is possible to partition an array into two subsets with equal sum.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the subset sum possibilities.

• Check if the total sum of the array is even before attempting to partition.

• Iterate through the array and update the subset sum array accordingly.

• Return true if the subset sum array contains a sum equal to half of the total sum.

The Ninja Port Problem involves finding the minimum time for a ninja to travel between colonies and houses using secret paths and teleportation.

• Calculate the minimum time considering teleportation within colonies, traveling between colonies, and secret paths.

• Keep track of the number of secret paths used and ensure they are one-way.

• Consider the constraints provided to optimize the solution.

• Example: N=2, K=3, S=1, P=1, sourceHouse=1, sourceColony=1, destinationHouse=3, destinat...read more

Add two numbers represented by linked lists and return the head of the sum list.

• Traverse both linked lists simultaneously while keeping track of carry from previous sum

• Create a new linked list to store the sum of the two numbers

• Handle cases where one linked list is longer than the other by padding with zeros

• Update the sum and carry values accordingly while iterating through the linked lists

Implement update and rangeSum operations on an integer array based on given queries.

• Implement update(l, r, val) by adding (val + i) to arr[l + i] for all i in range (0, r - l).

• Implement rangeSum(l, r) to return the sum of elements in the array from index l to r.

• Handle queries using 1-based indexing.

• Ensure constraints are met for input values.

• Output the sum of arr[l..r] for each rangeSum operation.

Clone a binary tree with random pointers and verify if cloning was successful by printing inorder traversal.

• Create a deep copy of the binary tree with random pointers.

• Print the inorder traversal of the cloned binary tree.

• Verify cloning success by printing '1' if successful, '0' otherwise.

Given courses with prerequisites, determine a valid order to complete all courses.

• Create a graph with courses as nodes and prerequisites as edges.

• Use topological sorting to find a valid order to complete all courses.

• Return an empty list if it's impossible to complete all courses.

Given a string, find and print all distinct palindromic substrings within it.

• Iterate through all possible substrings of the input string

• Check if each substring is a palindrome

• Store distinct palindromic substrings in a set and then sort them before printing

Find all nodes at distance K from a given node in a binary tree.

• Perform a depth-first search starting from the target node to find nodes at distance K.

• Use a recursive function to traverse the tree and keep track of the distance from the target node.

• Maintain a set to store visited nodes to avoid revisiting them.

• Return the list of nodes found at distance K from the target node.

• Example: If the target node is 5 and K is 2 in the given tree, the output should be [7, 4, 0, 8].

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.

Implement a priority queue using a heap data structure with push, pop, getMaxElement, and isEmpty functions.

• Implement a priority queue using a max heap data structure.

• Use the provided class structure and complete the push, pop, getMaxElement, and isEmpty functions.

• For push operation, insert the element into the heap and maintain the heap property.

• For pop operation, remove the largest element from the heap.

• For getMaxElement operation, return the largest element from the heap.

• F...read more

The problem involves finding the length of the longest increasing path in a 2-D matrix starting from a given cell.

• Use dynamic programming to keep track of the longest increasing path starting from each cell.

• Implement a recursive function to explore all possible paths from a cell.

• Update the length of the longest path for each cell based on the maximum path length from its neighbors.

• Consider edge cases such as boundary conditions and handling negative values in the matrix.

Find the maximum sum by traversing through common elements in two sorted arrays.

• Start with the array containing the smaller first common element

• Switch arrays at common elements to maximize the sum

• Continue adding elements until the end of the arrays

Find the maximum product of a contiguous subarray in an array of integers.

• Iterate through the array and keep track of the maximum and minimum product ending at each index.

• Update the maximum product by considering the current element, the maximum product ending at the previous index multiplied by the current element, and the minimum product ending at the previous index multiplied by the current element.

• Update the minimum product similarly.

• Return the maximum product found durin...read more

The task is to find the rectangle within a matrix that has the greatest sum of its elements.

• Iterate through all possible rectangles within the matrix

• Calculate the sum of each rectangle and keep track of the maximum sum

• Return the maximum sum obtained from any rectangle within the matrix

Given N events with start and end times, determine if each event can be added to the calendar without causing a triple booking.

• Iterate through each event and check if adding it causes a triple booking by comparing its interval with previous events

• Use a data structure like a list or dictionary to keep track of booked intervals

• Return 'True' if the event can be added without causing a triple booking, 'False' otherwise