200+ SDE-2 Interview Questions and Answers

Find the number with the maximum frequency in an array of integers.

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

• Iterate through the array to update the frequency count.

• Find the element with the maximum frequency and return it.

• If multiple elements have the same maximum frequency, return the one with the lowest index.

Perform a series of reverse string operations on a given string based on specified indices.

• Iterate through the array of indices and reverse the substring of the string based on the given indices.

• Ensure to reverse the substring from the starting index to len(S) - starting index - 1.

• Continue the operations in the sequence specified by the array of indices to get the final string.

The task is to check whether the given words are sorted lexicographically in an alien language.

• Read the number of test cases

• For each test case, read the number of words, the words themselves, and the order string

• Check if the words are sorted lexicographically based on the given order string

• Print 'YES' if the words are sorted, else print 'NO'

Given an array of words and an integer k, return the k most frequent words sorted by frequency.

• Use a hashmap to count the frequency of each word

• Use a priority queue to keep track of the k most frequent words

• Sort the priority queue based on frequency and lexicographical order

The task is to determine the minimum number of characters needed at the beginning of a string to make it a palindrome.

• Iterate from both ends of the string and compare characters to find the number of characters needed to make it a palindrome.

• Use dynamic programming to optimize the solution by storing results of subproblems.

• Handle edge cases like an already palindrome string or an empty string.

• Example: For 'deed', no characters need to be added, but for 'aabaaca', 2 characters...read more

Find the largest non-negative integer whose square is less than or equal to a given integer.

• Use binary search to efficiently find the square root of the given integer.

• Start with a range from 0 to the given integer and iteratively narrow down the range based on the square of the middle value.

• Return the largest integer whose square is less than or equal to the given integer.

Find sum of elements in a sorted array less than or equal to each element in queries.

• Iterate through queries and for each query, find the sum of elements in arr less than or equal to the query element.

• Use binary search to efficiently find the index of the last element less than or equal to the query element.

• Keep track of cumulative sum while iterating through arr to avoid recalculating sums.

• Return the list of sums for each test case.

The task is to find the maximum possible sum of a non-empty subarray of an array.

• Iterate through the array and keep track of the maximum sum encountered so far

• If the current element is greater than the sum so far, start a new subarray

• If the current element plus the sum so far is greater than the maximum sum, update the maximum sum

• Return the maximum sum

Find pairs of elements in an array that sum up to a given value, sorted in a specific order.

• Sort the array in non-decreasing order.

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

• Return pairs in sorted order based on first value, with smaller second value coming first.

Find the unique element in a sorted array where all other elements appear twice.

• Use XOR operation to find the unique element in the sorted array.

• Iterate through the array and XOR all elements, the result will be the unique element.

• Time complexity of O(n) can be achieved by iterating through the array once.

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 using different denominations.

• Iterate through each denomination and update the array based on the number of ways to make change for each value.

• Return the value at the last cell of the array as the final result.

The task is to connect N ropes into one rope with minimum cost.

• Sort the array of rope lengths in ascending order.

• Initialize a variable to keep track of the total cost.

• While there are more than one rope, take the two shortest ropes and connect them.

• Add the cost of connecting the two ropes to the total cost.

• Replace the two shortest ropes with the connected rope.

• Repeat the above steps until only one rope remains.

• Return the total cost.

Find the maximum sum of the path from the root to any leaf node in an n-ary tree.

• Traverse the tree from root to leaf nodes, keeping track of the sum along the path.

• At each node, calculate the sum of the path from the root to that node and update the maximum sum found so far.

• Consider using depth-first search (DFS) to traverse the tree efficiently.

• Handle cases where nodes are absent (-1) by appropriately updating the path sum.

• Return the maximum sum found for each test case.

Count the number of islands in a 2D matrix of 1s and 0s.

• Use Depth First Search (DFS) or Breadth First Search (BFS) to traverse the matrix and identify connected groups of 1s.

• Maintain a visited array to keep track of visited cells to avoid revisiting them.

• Increment the island count each time a new island is encountered.

• Consider all eight possible directions for connectivity between cells.

• Handle edge cases like out of bounds indices and water cells (0s).

Implement a function to print the zigzag traversal of a Binary Tree.

• Traverse the Binary Tree level by level, alternating the direction of traversal for each level.

• Use a queue to keep track of nodes at each level and a flag to switch the direction of traversal.

• Print the values of nodes in the zigzag order as described in the problem statement.

Find the minimum possible value of the maximum number of balls in a bag after performing a given number of operations.

• Iterate through the bags and split them to minimize the maximum number of balls.

• Keep track of the maximum number of balls after each operation.

• Return the minimum possible value of the maximum number of balls.

Determine total number of valid shopping combinations within budget

• Iterate through all possible combinations of items from each array

• Check if the total cost of the combination is within the budget

• Return the count of valid combinations

Boundary traversal of a binary tree to find left boundary, right boundary, and leaf nodes in an anti-clockwise direction.

• Perform a pre-order traversal to get the left boundary nodes

• Perform an in-order traversal to get the leaf nodes

• Perform a post-order traversal to get the right boundary nodes

• Combine the results in the required order to get the boundary nodes

The diameter of a binary tree is the length of the longest path between any two end nodes in the tree.

• The diameter of a binary tree can be calculated by finding the maximum of the following three values: 1) the diameter of the left subtree, 2) the diameter of the right subtree, and 3) the longest path that passes through the root node.

• To find the diameter of a binary tree, we can use a recursive approach where we calculate the height of each node and update the diameter at ea...read more

Find all pairs of elements in an array that add up to a given target.

• Iterate through the array and use a hashmap to store the difference between the target and each element.

• Check if the current element exists in the hashmap, if so, print the pair.

• If no pair is found, print (-1, -1).

Find longest continuous patch on a 12 km road with updates in patches

• Maintain a variable to keep track of current patch length

• Update the variable whenever a new patch is added

• Maintain a variable to keep track of longest patch so far

• Compare current patch length with longest patch length and update if necessary

• Use a sorted data structure like a binary search tree to store the patches for efficient search

• Time complexity: O(nlogn) where n is the number of updates by the contracto...read more

Given N meetings with start and end times, determine which meetings can be organized in a single room to maximize the number of meetings.

• Sort the meetings based on their end times.

• Iterate through the sorted meetings and select the first meeting that does not overlap with the previous one.

• Repeat the process until all meetings are considered.

• Return the selected meetings in the order they are organized.

Find the smallest subarray with exactly K distinct integers in an array.

• Use a sliding window approach to keep track of the subarray with K distinct integers.

• Use a hashmap to store the frequency of each integer in the current window.

• Update the window size based on the number of distinct integers found.

• Keep track of the smallest subarray meeting the criteria.

• Return the starting and ending indices of the smallest subarray with K distinct integers.

Find the minimum number of character deletions needed to make each character's frequency unique in a given string.

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

• Identify characters with the same frequency and calculate the minimum deletions needed to make them unique.

• Return the total minimum deletions for each test case.

Given an integer, find the sum of even and odd digits separately.

• Iterate through each digit of the integer and check if it is even or odd

• Keep track of the sum of even and odd digits separately

• Return the sums of even and odd digits

Generate all possible combinations of balanced parentheses for a given number of pairs.

• Use backtracking to generate all valid combinations of balanced parentheses.

• Keep track of the number of open and close parentheses used in each combination.

• Recursively build the combinations by adding open parentheses if there are remaining, and then adding close parentheses if the number of open parentheses is greater than the number of close parentheses.

• Return the list of valid combinatio...read more

Clone a linked list with random pointers and return the head of the copied list.

• Create a deep copy of the linked list by iterating through each node and creating a new node with the same value.

• Update the random pointers of the new nodes based on the random pointers of the original list.

• Use a hashmap to keep track of the mapping between original nodes and their corresponding new nodes.

• Return the head of the copied list.