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.

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

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'

The task is to remove consecutive duplicate characters from a given string and return the new string.

• Iterate through the characters of the string

• Compare each character with the next character

• If they are the same, skip the next character

• If they are different, append the current character to the new string

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

Count and return the total number of pairs in the array whose elements add up to a given sum.

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

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 problem involves finding the number of distinct ways to climb to the Nth stair by taking one or two steps at a time.

• Use dynamic programming to solve this 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 large inputs by taking modulo 10^9+7 of the result.

• Example: For N=3, there are 3 ways to climb to the third stair: (0, 1, 2, 3), (0, 2, 3), and (0, 1, 3).

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

Implement a function to find all palindromic numbers from 1 to N.

• Iterate from 1 to N and check if each number is a palindrome

• Use string manipulation to check if a number is a palindrome

• Consider single-digit numbers as palindromes as well

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).

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).

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.

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

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 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

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.

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.

Implement a Least Recently Used (LRU) cache data structure that supports get and put operations efficiently.

• Design a data structure that maintains a cache with a specified capacity.

• Implement get(key) function to return value associated with key or -1 if key doesn't exist.

• Implement put(key, value) function to insert/update key-value pair in cache.

• Invalidate least recently used item when cache reaches its capacity.

• Handle different types of operations efficiently based on input....read more

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

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.

Sliding window maximum problem where we find maximum element in each window of size K.

• Use a deque to store indices of elements in decreasing order within the window.

• Pop elements from the deque that are out of the current window.

• Add the maximum element to the result for each window.

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.

The problem involves finding all possible paths for a rat to reach its destination in a maze.

• Use backtracking to explore all possible paths in the maze.

• Mark visited cells to avoid revisiting them.

• Return the path once the destination is reached.

• Handle edge cases like blocked cells and out-of-bounds movements.

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.