2000+ Amazon Interview Questions and Answers

The task is to determine the number of possible ways to roll all the dice such that the sum of the face-up numbers equals the given 'target' sum.

• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the number of ways to achieve each sum with different number of dice.

• Iterate through the dice and sum possibilities to fill up the array.

• Return the result modulo 10^9 + 7.

• Optimize the solution to use no more than O(S) extra space by using rolling arra...read more

Find all triplets in a binary tree whose sum is greater than a given integer X, with a grandparent-parent-child relationship.

• Traverse the binary tree to find all possible triplets with the required relationship.

• Keep track of the sum of each triplet and compare it with the given integer X.

• Return the triplets that satisfy the condition in any order.

• Ensure each triplet follows the format (grand-parent, parent, child).

The minimum number of swaps required to sort a given array of distinct elements in ascending order.

• Use graph theory and cycle detection to find the minimum number of swaps

• Count the number of cycles in the permutation

• Each cycle requires (cycle_length - 1) swaps to sort

Find the next smallest palindrome greater than a given number represented as a string.

• Convert the string to an integer, find the next greater palindrome, and convert it back to a string.

• Handle cases where the number is a palindrome or has all digits as '9'.

• Consider both odd and even length numbers when finding the next palindrome.

Generate all possible subsequences of a given string.

• Use recursion to generate all possible subsequences by including or excluding each character in the string.

• Maintain the order of characters while generating subsequences.

• Handle base cases where the string is empty or has only one character.

• Store the generated subsequences in an array of strings.

A customer service associate is responsible for providing assistance and support to customers, addressing their inquiries and resolving any issues they may have.

• Assisting customers with their inquiries and providing accurate information

• Resolving customer complaints and issues in a timely and satisfactory manner

• Maintaining a positive and professional attitude while interacting with customers

• Processing customer orders, returns, and exchanges

• Providing product recommendations and...read more

Determine the minimum number of platforms needed at a railway station so that no train has to wait.

• Sort the arrival and departure times arrays in ascending order.

• Initialize two pointers, one for arrival times and one for departure times.

• Increment the platform count when a train arrives and decrement when it departs.

• Keep track of the maximum platform count needed.

• Return the maximum platform count as the minimum number of platforms needed.

Compute square root of integer with specified decimal precision.

• Implement a function to calculate square root using binary search or Newton's method.

• Keep track of the precision required and stop when the difference is within the limit.

• Handle multiple test cases efficiently to meet the time limit.

• Ensure the output is formatted to the specified decimal places.

• Consider edge cases like maximum input values and precision requirements.

Reverse groups of K nodes in a doubly linked list

• Iterate through the linked list in groups of K nodes

• Reverse each group of K nodes

• Update the pointers accordingly

• Handle cases where the number of remaining nodes is less than K

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

Cloning a linked list with random pointers by creating new nodes rather than copying references.

• Create a deep copy of the linked list by iterating through the original list and creating new nodes with the same values.

• Update the random pointers of the new nodes by mapping the original node's random pointer index to the corresponding new node.

• Ensure the cloned linked list is an exact copy of the original by validating the values and random pointers.

• The cloning process can be ac...read more

Print the left view of a binary tree, containing nodes visible from the left side.

• Traverse the tree level by level and print the first node of each level.

• Use a queue to keep track of nodes at each level.

• Handle null nodes represented by -1 in the input.

Find the largest subtree sum in an arbitrary binary tree.

• Traverse the binary tree to calculate the subtree sum of each node.

• Keep track of the maximum subtree sum encountered so far.

• Recursively calculate the subtree sum for each node by considering its left and right children.

• Consider edge cases like when the tree is empty or has only one node.

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

• Iterate through the matrix and perform depth-first search (DFS) to find connected 1s.

• Use a visited array to keep track of visited cells to avoid counting the same island multiple times.

• Increment the island count whenever a new island is encountered.

Find the k-th smallest element in an unsorted array of distinct integers.

• Sort the array and return the k-th element.

• Use a min-heap to find the k-th smallest element efficiently.

• Implement quickselect algorithm to find the k-th smallest element in linear time.

Count the number of triplets in a sorted doubly linked list such that their sum equals a given integer 'X'.

• Iterate through the linked list and for each node, use two pointers to find the other two nodes that sum up to 'X'.

• Keep track of the count of triplets found while traversing the list.

• Return the final count of triplets that sum up to 'X'.

Distribute chocolates among students to minimize difference between largest and smallest packets.

• Sort the array of chocolates packets.

• Use sliding window technique to find the minimum difference between packets distributed to students.

• Return the minimum difference as the output.

Find the overall median of a matrix with sorted rows.

• Merge all elements of the matrix into a single sorted array

• Calculate the median of the merged array

• Handle odd number of elements by directly finding the middle element

Count triplets in a sorted doubly linked list that sum up to a given value.

• Iterate through the list and for each node, find pairs that sum up to X-nodeValue.

• Use two pointers approach to find pairs efficiently.

• Keep track of count of triplets found while iterating through the list.

Given two binary trees T and S, determine if S is a subtree of T with the same structure and node values.

• Traverse both trees and check if S is a subtree of T at each node

• Use recursion to compare subtrees

• Handle edge cases like empty trees or null nodes

Verify if two strings are anagrams of each other by rearranging the letters.

• Create character frequency maps for both strings.

• Compare the frequency of characters in both maps to check if they are anagrams.

• Return 'True' if the frequencies match, else return 'False'.

Return the boundary nodes of a binary tree in an anti-clockwise direction starting from the root node.

• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Avoid repeating nodes in the output

• Example: For input 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1, output should be 1 2 4 7 6 3

The Minimum Path Sum Problem involves finding the minimum sum of costs along a path from the top-left to the bottom-right of a grid.

• Use dynamic programming to calculate the minimum path sum by considering the costs of moving down or right at each cell.

• Initialize a 2D array to store the minimum path sum values for each cell in the grid.

• Iterate through the grid to calculate the minimum path sum for each cell based on the previous cells.

• Return the minimum path sum for the bottom...read more

The task is to find the number of islands present in a 2-dimensional array filled with ones and zeroes.

• Iterate through each cell in the array

• If the cell is land (1) and not visited, perform a depth-first search to find all connected land cells

• Increment the count of islands for each connected component found

Given a binary tree, a target node, and an integer K, find all nodes at distance K from the target node.

• Traverse the binary tree to find the target node.

• Use BFS to traverse the tree from the target node to nodes at distance K.

• Keep track of the distance while traversing the tree.

• Return the values of nodes at distance K in any order.

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 amount of money that can be stolen up to each house.

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

• Return the maximum amount of money that can be stolen at the last house.

Find the first and last positions of an element in a sorted array efficiently.

• Use binary search to find the first occurrence of X in the array.

• Use binary search to find the last occurrence of X in the array.

• Handle cases where X is not present or present only once.

• Return the first and last positions as 0-based indices.

Determine if there exists a path from the top-left cell to the bottom-right cell of a maze with N doors and 1 key.

• Use depth-first search (DFS) or breadth-first search (BFS) to explore possible paths through the maze.

• Keep track of the cells visited and use the key only once to open doors.

• Check if the bottom-right cell is reachable after traversing the maze.

• Handle edge cases such as the top-left and bottom-right cells having doors.

• Return 'YES' if reachable, 'NO' otherwise.

Calculate total number of distinct paths from a given source node to all other nodes in a directed graph.

• Use dynamic programming to keep track of the number of paths from the source node to each node.

• Consider the modulo operation to handle large numbers efficiently.

• Start by initializing the number of paths from the source node to itself as 1.

• Iterate through all edges and update the number of paths for each destination node.

• Return the total number of distinct paths modulo 10^9...read more

Rearrange the array elements to form the largest possible number by concatenating them.

• Sort the array elements in a custom comparator function to get the largest number.

• Convert the sorted array elements to strings and concatenate them to form the final number.

• Handle cases where the numbers have the same prefix by comparing the concatenated forms.

Find pairs of integers in a BST whose sum is equal to a given number.

• Traverse the BST and store the values in a hash set.

• For each node, check if (X - node.value) exists in the hash set.

• If yes, add the pair (node.value, X - node.value) to the result.

• Continue traversal until all nodes are processed.

Implement a class to check if a string formed by the last queried characters exists in a dictionary of words.

• Initialize the class with the dictionary of words.

• Implement a method to check if the string formed by the last queried characters exists in the dictionary.

• Use appropriate data structures to efficiently solve the problem.

• Ensure the class handles multiple test cases and character queries.

• Example: DICTIONARY[] = ['app', 'apple', 'banana'], Query Stream: ['a', 'p', 'p', 'l...read more

Seller Support provides assistance to Amazon sellers with their account and product related issues.

• Seller Support helps sellers with account registration, product listing, order management, and payment issues.

• They also provide guidance on Amazon policies and best practices for selling on the platform.

• Seller Support can be accessed through phone, email, or chat support.

• They work closely with other Amazon teams to resolve seller issues and improve the overall selling experience...read more

Find the minimum cost to purchase a specific weight of oranges given the cost of different weight packets.

• Iterate through the list of costs and find the minimum cost to achieve the desired weight

• Keep track of the total cost while considering available packet weights

• Return -1 if it is not possible to buy exactly the desired weight

Given a string of consecutive nonnegative integers with one missing number, find the missing integer.

• Iterate through the string and check for missing numbers by comparing adjacent integers

• Calculate the sum of the original sequence and the sum of the integers in the string to find the missing number

• Handle cases where there are multiple missing numbers or the string is invalid

Design a data structure to efficiently return the k-th largest number from an infinite stream of numbers.

• Implement a max heap to store the numbers in the stream.

• Keep the heap size limited to k to efficiently find the k-th largest number.

• Update the heap when adding new numbers or querying for the k-th largest number.

Find the number of states of cities connected by roads in a matrix.

• Iterate through each city and perform depth-first search to find connected cities.

• Use a visited array to keep track of visited cities.

• Increment state count whenever a new state is found.

Implement a function to return the spiral order traversal of a binary tree.

• Traverse the binary tree level by level, alternating between left to right and right to left.

• Use a queue to keep track of nodes at each level.

• Append nodes to the result list in the order they are visited.

Given a string of lowercase characters, rearrange it so that no two adjacent characters are identical. Return the rearranged string or 'NO SOLUTION'.

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

• Sort the characters based on their frequency in non-increasing order.

• Place the characters with highest frequency first, alternating with other characters.

• If there are more than half of the characters with the same frequency, 'NO SOLUTION' is returned.

Sort a Singly Linked List based on actual values instead of absolute values.

• Traverse the linked list and store the nodes in an array.

• Sort the array based on the actual values of the nodes.

• Reconstruct the linked list using the sorted array.

Determine the gender of the Kth child in the Nth generation based on a unique family structure.

• Every male member has a male child first followed by a female child, and every female member has a female child first followed by a male child.

• Given generation number N and position of the child K, determine the gender of the Kth child in the Nth generation.

• Output 'Male' if the child is male, otherwise 'Female'.

• Start the family tree from the male member, Aakash.

Clone a linked list with random pointers by creating deep copy of the original list without duplicating references.

• Create a deep copy of the linked list by instantiating new nodes for each node in the original list.

• Ensure that the random pointers in the cloned list point to the corresponding nodes in the new list.

• Do not duplicate references to original nodes while creating the clone.

• Implement the function to clone the linked list without using additional space.

• Verify that the...read more

Find maximum element in every contiguous subarray of size K in an array.

• Iterate through the array and maintain a deque to store the indices of elements in decreasing order.

• Remove indices from the deque that are outside the current window of size K.

• The front of the deque will always have the index of the maximum element in the current window.

Calculate the fraction when one integer is divided by another, with repeating decimal parts enclosed in parentheses.

• Divide the first integer by the second integer to get the fraction

• Identify if the fractional part is repeating and enclose it in parentheses

• Return the fraction for each test case

Identify the celebrity at a party where one person knows everyone but is not known by anyone.

• Use a two-pointer approach to eliminate non-celebrity candidates.

• Start with two pointers at the beginning and end of the party.

• If A knows B, A cannot be the celebrity; move A to B.

• If A does not know B, B cannot be the celebrity; move B to A.

• Repeat until only one person remains; check if this person is known by everyone.

• Return the ID of the celebrity or -1 if none exists.

The task is to determine the number of nodes that can be reached from each node in a graph.

• Create an adjacency list to represent the graph.

• Use Depth First Search (DFS) to traverse the graph and count reachable nodes from each node.

• Initialize a count array to store the number of reachable nodes for each node.

• Update the count array while traversing the graph using DFS.

• Output the count array for each test case.

Given an integer representing a binary sequence, find the maximum consecutive ones by flipping one bit.

• Iterate through the binary representation of the integer to find the longest sequence of ones.

• Track the positions of zeros to determine where to flip a bit for maximizing consecutive ones.

• Update the count of consecutive ones after flipping a zero to one.

• Return the maximum length of consecutive ones obtained by flipping one bit.

Given a set of stations connected by trains, find the cheapest fare from a source to a destination with a maximum number of stops allowed.

• Iterate through all possible routes with up to 'K' stops using a graph traversal algorithm like DFS or BFS.

• Keep track of the cost for each route and return the minimum cost found.

• If no route is found within the maximum stops allowed, return '-1'.

Find the row with the maximum number of 1's in a grid of 0's and 1's.

• Iterate through each row of the grid and count the number of 1's in each row.

• Keep track of the row index with the maximum number of 1's seen so far.

• Return the index of the row with the maximum number of 1's.

Calculate the probability that a knight remains on an N x N chessboard after making K moves.

• Use dynamic programming to calculate the probability of the knight staying on the board after each move.

• Consider all possible moves the knight can make from its current position.

• Keep track of the probabilities at each position on the board after each move.

• Normalize the probabilities at the end to get the final result accurate to six decimal places.

Find the number of starting indices from which a Ninja can reach the last stone by following specific jump rules.

• Iterate through the array and keep track of the indices that satisfy the jump rules.

• Use dynamic programming to efficiently determine the number of starting indices.

• Consider odd and even jumps separately to handle the different conditions.

• Example: For the input [10, 13, 12, 14, 15], the Ninja can start at indices 0 and 1 to reach the last stone.

If a problem, the call should not be prolonged and should be resolved as soon as possible.

• It is important to actively listen to the customer's problem and provide a solution quickly.

• If the problem cannot be resolved immediately, provide a timeline for resolution and follow up with the customer.

• Avoid transferring the call multiple times as it can frustrate the customer.

• If necessary, escalate the issue to a supervisor or manager for further assistance.

Find the area of the largest rectangle that can be formed within the bounds of a given histogram.

• Iterate through the histogram bars and maintain a stack to keep track of increasing heights.

• Calculate the area of the rectangle formed by each bar as the smallest height in the stack times the width.

• Update the maximum area found so far and return it as the result.

Detect if an array contains a Pythagorean triplet.

• Iterate through all possible triplets in the array and check if they form a Pythagorean triplet.

• Use a nested loop to generate all possible combinations of three numbers in the array.

• Check if the sum of squares of two numbers is equal to the square of the third number.

Find the largest palindrome number strictly less than the given palindrome number.

• Iterate from the middle towards the start of the number and copy the digits to the left side to create the next smaller palindrome.

• Handle cases where the middle digit is not 0 by decrementing it and mirroring the left side to the right side.

• If the number is all 9s, change the first and last digits to 1 and fill the middle with 0s.

Check if a binary tree is 'special' if every node has zero or two children.

• Traverse the binary tree and check if each non-leaf node has exactly two children.

• Use a recursive approach to check each node's children.

• Handle NULL nodes represented by -1 in the input.

Group anagrams in an array of strings based on their characters.

• Iterate through the array of strings and sort each string to group anagrams together.

• Use a hashmap to store the sorted string as key and the list of anagrams as value.

• Return the values of the hashmap as the grouped anagrams.

Construct the largest number by concatenating positive integers in the array exactly once.

• Sort the array of integers in a way that the concatenation of the numbers forms the largest possible number.

• Use a custom comparator function to sort the numbers based on their concatenation value.

• Join the sorted array elements to form the final largest number.

Convert infix expression to postfix expression.

• Use a stack to keep track of operators and operands.

• Follow the rules of precedence for operators (* and / before + and -).

• Handle parentheses by pushing them onto the stack and popping when necessary.

Return the level order traversal of a binary tree given in level order with null nodes represented by -1.

• Create a queue to store nodes for level order traversal

• Start with the root node and enqueue it

• While the queue is not empty, dequeue a node, print its value, and enqueue its children

• Repeat until all nodes are traversed in level order

Determine if a given binary tree is a binary heap tree or not based on certain properties.

• Check if the binary tree is a complete binary tree where every level, except the last level, is completely filled and the last level is as far left as possible.

• Ensure that every parent node is greater than all its children nodes, forming a max-heap.

• If any node does not have a left or right child, it should be represented as -1 in the input.

Calculate bitwise 'AND' and 'XOR' of subarrays of size at most K in an array efficiently.

• Iterate through all subarrays of size at most K and calculate bitwise 'AND'.

• Calculate the 'XOR' of all the bitwise 'AND' results to get the final output.

• Optimize the solution to handle large input sizes efficiently.

Implement a function to find critical connections in a network with system nodes and connections.

• Create an adjacency list to represent the network connections.

• Use Tarjan's algorithm to find critical connections in the network.

• Output the count of critical connections and the pairs of nodes involved.

• Handle multiple test cases efficiently.

• Ensure that the removal of a critical connection disrupts network connectivity.

Maximize memory usage by pairing downloads and games within memory limit 'K'.

• Sort the downloads and games in descending order.

• Iterate through the sorted arrays to find the optimal pairs within memory limit 'K'.

• Return the indices of the selected download and game pairs.

To check if a number k lies in a sequence formed by adding previous 2 elements, start with a=0 and b=1 and iterate until k is found or exceeded.

• Start with a=0 and b=1

• Iterate through the sequence until k is found or exceeded

• If k is found, return true. If exceeded, return false

Traverse a 2D array row-wise and return elements in a wave pattern.

• Traverse the 2D array row-wise and store elements alternately in a wave pattern.

• For each row, store elements from left to right for odd rows and from right to left for even rows.

• Return the final 1D array representing the wave pattern of elements.

Find the minimum number of dice throws required to reach the last cell on a 'Snake and Ladder' board.

• Use Breadth First Search (BFS) algorithm to find the shortest path on the board.

• Keep track of visited cells and the number of dice throws required to reach each cell.

• Consider the presence of snakes and ladders while calculating the next possible moves.

• Return -1 if the last cell is unreachable.

Given an array of integers, generate a new array with the squares of each element sorted in increasing order.

• Iterate through the array and square each element

• Sort the squared elements in increasing order

• Return the sorted array

Determine if a given string consisting of '(' , ')' and '*' is valid based on certain rules.

• Iterate through the string and keep track of the count of left parentheses, right parentheses, and stars.

• Use a stack to keep track of the positions of left parentheses.

• If at any point the count of right parentheses exceeds the count of left parentheses + stars, the string is invalid.

• If the stack is not empty at the end, the string is invalid.

• Otherwise, the string is valid.

Convert a binary tree to a sum tree by replacing each node with the sum of its left and right subtrees.

• Traverse the tree in postorder fashion.

• For each node, calculate the sum of its left and right subtrees and update the node's value.

• Set leaf nodes to zero.

• Return the level order traversal of the modified tree.

Identify the duplicate integer in an array containing numbers between 1 and N-1.

• Iterate through the array and keep track of the frequency of each number using a hashmap.

• Return the number with a frequency greater than 1 as the duplicate integer.

• Time complexity can be optimized to O(N) using Floyd's Tortoise and Hare algorithm.

• Example: For input [1, 2, 3, 4, 4], the output should be 4.

Determine if a binary string can be sorted in decreasing order by removing non-adjacent characters.

• Check if the count of '1's in the string is equal to the length of the string, as it can be sorted in decreasing order by removing non-adjacent characters.

• If the count of '1's is not equal to the length of the string, check if the string can be rearranged to form a decreasing order by removing non-adjacent characters.

• Consider edge cases like all '0's or all '1's in the string.

Given an array of integers and a target sum, find a contiguous subarray with the sum equal to the target.

• Iterate through the array while keeping track of the current sum and start index.

• Use a hashmap to store the cumulative sum and its corresponding index.

• If the current sum - target sum exists in the hashmap, a subarray with the target sum is found.

• Return the start index and current index as the end index of the subarray.

Return the boundary nodes of a binary tree in Anti-Clockwise direction starting from the root node.

• Traverse the left boundary nodes in a top-down manner

• Traverse the leaf nodes from left to right

• Traverse the right boundary nodes in a bottom-up manner

• Handle cases where duplicates occur in the boundary nodes

• Implement the function without printing as printing is already managed

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

Create a deep copy of a linked list with random pointers.

• Iterate through the original linked list and create a new node for each node in the list.

• Store the mapping of original nodes to new nodes in a hashmap to handle random pointers.

• Update the random pointers of new nodes based on the mapping stored in the hashmap.

• Return the head of the copied linked list.

Sort a linked list containing values 0, 1, and 2 exclusively.

• Use three pointers to keep track of nodes with values 0, 1, and 2 separately.

• Traverse the linked list and move nodes to their respective positions based on their values.

• Finally, concatenate the three lists in the order 0 -> 1 -> 2 to get the sorted linked list.

Given a 2D matrix with sorted rows and columns, determine if a given integer is present in the matrix.

• Iterate through the matrix starting from the top right corner or bottom left corner to efficiently search for the target integer.

• Use the sorted property of rows and columns to eliminate rows or columns based on the comparison with the target integer.

• If the target integer is greater than the current element, move down in the matrix. If it is smaller, move left.

• Continue this pr...read more

Find the smallest sum achievable by selecting one element from each row of a 2D matrix, following certain constraints.

• Iterate through each row and find the minimum element that does not violate the constraints.

• Keep track of the minimum sum achieved by selecting elements from each row.

• Avoid selecting elements directly beneath previously selected elements.

The minimum number of swaps required to make a string K-periodic by replacing characters with elements from an array.

• Iterate through the string and check if each character matches the character K positions ahead.

• Count the number of characters that need to be swapped to make the string K-periodic.

• Use the array elements to swap characters in the string.

• Return the total number of swaps needed for each test case.

Given a number represented as a string, find the smallest number greater than the original with the same set of digits.

• Iterate from right to left to find the first digit that can be swapped with a larger digit to make the number greater.

• Swap this digit with the smallest digit to its right that is larger than it.

• Sort the digits to the right of the swapped digit in ascending order to get the smallest number greater than the original.

• If no such number exists, return -1.

• Example: ...read more

Rearrange array elements in a zig-zag manner where every odd index element is greater than its neighbors.

• Iterate through the array and swap elements to satisfy the zig-zag condition.

• Ensure that for every odd index i, ARR[i] > ARR[i-1] and ARR[i] > ARR[i+1].

• Multiple correct answers may exist for a given array.

Determine if a robot can reach a specified destination in a matrix by moving only downwards or rightwards.

• Start at (0,0) and move towards the destination (x, y) only downwards or rightwards.

• Check if the path is clear (1) and avoid obstacles (0) while staying within matrix boundaries.

• Return true if the robot can reach the destination, false otherwise.

• Example: For input matrix [[1, 0, 1], [1, 1, 1], [1, 1, 5]] with destination (2, 2), the output is true.

Implement a BSTIterator class to traverse a Binary Search Tree in inorder manner.

• Implement a constructor to initialize the iterator with the root of the BST.

• Implement next() and hasNext() methods to traverse the BST in inorder.

• Implement prev() and hasPrev() methods to access the previous element in the inorder traversal.

• Use level-order traversal format to represent the tree input.

• Output the inorder traversal of the binary search tree for each test case.

Calculate the distance between two nodes in a binary tree.

• Traverse the tree to find the paths from the root to each node

• Find the lowest common ancestor of the two nodes

• Calculate the distance by adding the distances from the LCA to each node

Reverse a linked list in groups of size K by reversing nodes in each group.

• Iterate through the linked list in groups of size K

• Reverse each group of nodes

• Handle cases where the last group may not have K elements

Calculate the total amount of rainwater that can be trapped between given elevations in an array.

• Iterate through the array and calculate the maximum height on the left and right of each bar.

• Calculate the amount of water that can be trapped at each bar by taking the minimum of the maximum heights on the left and right.

• Sum up the trapped water at each bar to get the total trapped water for the entire array.

Identify the K most frequent words in a list, sorted by frequency and lexicographical order.

• Use a hashmap to store word frequencies

• Use a min heap to keep track of K most frequent words

• Sort the heap based on frequency and lexicographical order

Find the K closest points to the origin in a 2-D plane using Euclidean Distance.

• Calculate the Euclidean Distance of each point from the origin

• Sort the points based on their distances from the origin

• Return the first K points as the closest points

Find the Lowest Common Ancestor (LCA) of two nodes in a binary tree.

• Traverse the binary tree to find the paths from the root to nodes X and Y.

• Compare the paths to find the last common node, which is the LCA.

• Handle cases where one node is an ancestor of the other.

• Consider edge cases like when X or Y is the root node.

• Implement a recursive or iterative solution to find the LCA efficiently.

Implement a binary tree class from scratch to handle insert, delete, and random retrieval queries.

• Create a binary tree class with insert and delete methods.

• Implement a method to randomly retrieve a node from the tree.

• Ensure equal chance of selection for each node during random retrieval.

• Handle different types of queries ('I', 'D', 'R') on the binary tree.

• Return the value of the randomly chosen node for each test case.

Find all the bridges in an undirected graph.

• Use Tarjan's algorithm to find bridges in the graph.

• A bridge is an edge whose removal increases the number of connected components.

• Check for bridges by removing each edge and checking the number of connected components.

• Return the edges that are bridges in non-decreasing order.

Implement functions to calculate mean, median, and mode of an integer array.

• Calculate mean by summing all elements and dividing by total count

• Calculate median by sorting array and finding middle element(s)

• Calculate mode by finding element with highest frequency

Compute the maximum length of a string that can be formed by joining given strings based on a condition.

• Iterate through each string and store the count of strings ending with 'R' and 'B'.

• Check if there are any strings ending with 'R' and 'B' that can be combined to form a longer string.

• Return the maximum length of the string that can be formed or 0 if no combination is possible.

Return all prime numbers less than or equal to a given positive integer N.

• Iterate from 2 to N and check if each number is prime using a helper function.

• A number is prime if it is not divisible by any number from 2 to its square root.

• Return the prime numbers in increasing order for each test case.

Construct a binary tree from preorder traversal and leaf node information.

• Create a binary tree using preorder traversal and leaf node information.

• Use a stack to keep track of nodes and their children.

• Handle leaf nodes appropriately to construct the tree.

• Traverse the preorder list to construct the binary tree.

Rotate a matrix to the right 'K' times by shifting each column to the right 'K' times.

• Iterate 'K' times to perform right rotation on the matrix

• Shift each column to the right by one position in each rotation

• Handle the edge cases where 'K' is greater than the number of columns

Find the node where two linked lists merge, return -1 if no merging occurs.

• Traverse both lists to find their lengths and the difference in lengths

• Move the pointer of the longer list by the difference in lengths

• Traverse both lists simultaneously until they meet at the merging point

The task is to find the minimum number of operations required to convert one string into another using delete, replace, and insert operations.

• Use dynamic programming to solve the problem efficiently.

• Create a 2D array to store the edit distances between substrings of the two input strings.

• Fill up the array based on the minimum of three possible operations: insert, delete, or replace.

• The final answer will be the value at the bottom right corner of the array.

• Example: For strings...read more