200+ SDE-2 Interview Questions and Answers

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

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.

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.

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

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.

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

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.

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

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.

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.