200+ SDE-2 Interview Questions and Answers

Find two lines to form a container with maximum water area on a Cartesian plane.

• Iterate through the array from both ends to find the maximum area.

• Calculate the area using the formula: (min(height[left], height[right]) * (right - left)).

• Update the pointers based on the height of the lines to maximize the area.

Find the minimum cost to reduce an array to a single element by merging adjacent elements with their sum.

• Iteratively merge adjacent elements to minimize total cost

• Choose pairs to merge strategically to reduce cost

• Calculate sum of adjacent elements and update array size

Count the number of subsequences with odd and even sums in a given array of positive integers modulo 10^9 + 7.

• Use dynamic programming to keep track of the count of subsequences with odd and even sums.

• Consider the parity of each element in the array to determine the count of subsequences with odd and even sums.

• Apply modulo 10^9 + 7 to handle large resulting numbers.

• Example: For input [1, 2, 3], there are 3 subsequences with odd sums and 4 subsequences with even sums.

Sort an array of 0s and 1s in linear time without using additional arrays.

• Use two pointers approach to swap 0s to the left and 1s to the right.

• Keep track of the leftmost index of 1s to place 0s before it.

• Iterate through the array once and swap elements accordingly.

The problem involves finding the minimum number of jumps required to reach the last index of an array, where each element indicates the maximum distance that can be jumped from that position.

• Use a greedy approach to keep track of the farthest reachable index and the current end of the jump.

• Iterate through the array, updating the farthest reachable index and incrementing the jump count when necessary.

• Return the jump count as the minimum number of jumps needed to reach the last...read more

The task is to sort an array of 0s, 1s, and 2s in increasing order.

• Use a three-pointer approach to partition the array into three sections: 0s, 1s, and 2s.

• Initialize three pointers: low, mid, and high. low points to the start of the array, mid points to the current element being processed, and high points to the end of the array.

• While mid <= high, if ARR[mid] is 0, swap ARR[low] and ARR[mid], increment low and mid. If ARR[mid] is 1, increment mid. If ARR[mid] is 2, swap ARR[m...read more

Find the maximum depth of a binary tree given its level order traversal.

• Traverse the tree level by level and keep track of the depth using a queue data structure.

• For each level, increment the depth by 1 until all nodes are processed.

• Return the maximum depth encountered during traversal as the final result.

• Example: For input [5, 10, 15, 20, -1, 25, 30, -1, 40, -1, -1, -1, -1, 45], the maximum depth is 7.

Reverse a singly linked list by altering the links between nodes.

• Iterate through the linked list and reverse the links between nodes

• Use three pointers to keep track of the current, previous, and next nodes

• Update the links between nodes to reverse the list

• Return the head of the reversed linked list

Implement a wildcard pattern matching algorithm to determine if a given wildcard pattern matches a text string completely.

• Create a dynamic programming matrix to store intermediate results

• Handle cases for '?' and '*' characters separately

• Check if the characters in the pattern and text match accordingly

• Return 'True' if the text matches the pattern, otherwise 'False'

Maximize profit by scheduling jobs within their deadlines.

• Sort the jobs based on their profits in descending order.

• Iterate through the sorted jobs and schedule them based on their deadlines.

• Keep track of the maximum profit achievable by scheduling jobs within their deadlines.

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 values less than the node's value.

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

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

• Traverse the tree in-order and check if the elements are in sorted order.

• Use a recursive function to validate each node's value against its sub...read more

The problem involves finding the minimum number of moves a knight requires to reach a target position from a starting position on a chessboard.

• Use Breadth First Search (BFS) algorithm to find the shortest path from starting position to target position.

• Consider all possible moves of the knight from its current position to explore the chessboard.

• Keep track of visited positions to avoid revisiting the same position.

• Calculate the minimum number of steps needed to reach the target...read more

Calculate the time in minutes required to completely burn a binary tree starting from a given node.

• Start burning from the given node and spread fire to adjacent nodes each minute

• Track the time taken for each node to burn completely

• Return the maximum time taken to burn the entire tree

Find the smallest element in a rotated sorted array.

• Use binary search to find the pivot point where rotation occurs.

• Compare the element at the pivot point to determine the smallest element.

• Handle cases where the array is not rotated or has only one element.

• Time complexity should be O(log(N)) and space complexity O(1).

Calculate the minimum number of moves a Knight requires to reach a specified target position on a chessboard.

• Use breadth-first search (BFS) algorithm to find the shortest path for the Knight.

• Consider all possible moves of the Knight on the chessboard.

• Keep track of visited positions to avoid revisiting them.

• Return the minimum number of moves required to reach the target position.

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 - current element) exists in the hashmap.

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

• Divide the count by 2 to avoid counting duplicates like (arr[i], arr[j]) and (arr[j], arr[i]) separately.

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.

Check if a given undirected graph can be divided into exactly two disjoint cliques.

• Create an adjacency list to represent the graph

• Use BFS or DFS to check if the graph is bipartite

• If the graph is bipartite, it can be divided into two disjoint cliques

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.

Given a string, rearrange its characters so that no two adjacent characters are the same.

• Iterate through the string and count the frequency of each character.

• Use a priority queue to rearrange the characters based on their frequency.

• Check if it's possible to rearrange the string without any two adjacent characters being the same.

• Return 'Yes' if possible, 'No' otherwise.

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.