100+ Amazon Software Developer Interview Questions and Answers for Freshers

Find the maximum sum of any contiguous subarray within an array of integers.

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

• At each index, decide whether to include the current element in the subarray or start a new subarray.

• Use Kadane's algorithm to efficiently find the maximum subarray sum in O(N) time complexity.

Check if a permutation of one string is a substring of another string.

• Create a frequency map of characters in str1.

• Iterate through str2 with a window of size N and check if the frequency map matches.

• Return 'Yes' if a permutation is found, 'No' otherwise.

Remove alternate nodes from a singly linked list of integers.

• Traverse the linked list and skip every alternate node while updating the next pointers.

• Make sure to handle cases where there are less than 3 nodes in the list.

• Update the next pointers accordingly to remove alternate nodes.

• Example: Input: 10 20 30 40 50 60 -1, Output: 10 30 50

Find the maximum sum of non-adjacent elements in an array.

• Use dynamic programming to keep track of the maximum sum at each index, considering whether to include the current element or skip it.

• At each index, the maximum sum is either the sum of the current element and the element two positions back, or the sum at the previous index.

• Iterate through the array and update the maximum sum at each index accordingly.

• Return the maximum sum obtained at the last index as the final resul...read more

Calculate the sum of minimum and maximum elements of all subarrays of size K in an array.

• Iterate through the array and maintain a deque to store the indices of elements in the current window of size K.

• Keep track of the minimum and maximum elements in the current window using the deque.

• Calculate the sum of minimum and maximum elements for each subarray of size K and return the total sum.

The problem involves selecting the smallest character from the first 'K' characters of a string and appending it to a new string until the 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.

• If fewer than 'K' characters remain, sort and append them in order.

• Repeat the process until the original string is empty.

The goal is to determine the maximum profit that can be achieved by buying and selling stocks on different days.

• Iterate through the stock prices and buy on days when the price is lower than the next day, and sell on days when the price is higher than the next day.

• Calculate the profit by summing up the differences between buying and selling prices.

• Repeat the process for each test case and output the maximum profit achieved.

• Example: For prices [7, 1, 5, 3, 6, 4], buy on day 2 a...read more

Detect cycle in a directed graph using depth-first search (DFS) algorithm.

• Use DFS to traverse the graph and detect back edges indicating a cycle.

• Maintain a visited array to keep track of visited nodes during traversal.

• If a node is visited again during traversal and it is not the parent node, then a cycle exists.

• Return true if a cycle is detected, false otherwise.

Sort an array of 0s, 1s, and 2s in linear time complexity.

• Use three pointers to keep track of 0s, 1s, and 2s while traversing the array.

• Swap elements based on the values encountered to sort the array in a single scan.

• Final array will have 0s on the left, 1s in the middle, and 2s on the right.

Count the total number of derangements possible for a set of 'N' elements.

• A derangement is a permutation where no element appears in its original position.

• Use the formula for derangements: !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!).

• Return the answer modulo (10^9 + 7) as the result could be very large.

Calculate the number of distinct numbers that can be formed by pressing 'N' buttons on a mobile keypad following specific rules.

• Use dynamic programming to keep track of the number of distinct numbers that can be formed at each step.

• Consider the possible transitions from each button to calculate the total number of distinct numbers.

• Implement a solution that efficiently handles large values by using modulo arithmetic.

• Ensure that the solution runs within the given time limit of ...read more

Tarjan's Algorithm is used to find strongly connected components in an unweighted directed graph.

• Tarjan's Algorithm is a depth-first search based algorithm.

• It uses a stack to keep track of vertices in the current SCC.

• The algorithm assigns a unique id to each vertex and keeps track of the lowest id reachable from the current vertex.

• Once a SCC is identified, the vertices in the stack form that SCC.

• The algorithm runs in O(V + E) time complexity.

• Example: For the input graph with ...read more

Sort an array of 0s, 1s, and 2s in linear time with a single scan approach.

• Use three pointers to keep track of the positions of 0s, 1s, and 2s in the array.

• Iterate through the array once and swap elements based on their values and the pointers.

• After the single scan, the array will be sorted in the required order.

Evaluate postfix expressions by applying operators after operands. Return result modulo (10^9+7).

• Iterate through each character in the postfix expression

• If character is an operand, push it onto the stack

• If character is an operator, pop two operands from stack, apply operator, and push result back

• Continue until end of expression, return final result modulo (10^9+7)

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

• Create a function to check if tree S is a subtree of tree T by comparing their structures and node values.

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

• Use recursion to check if the current nodes of T and S are equal, and then recursively check their left and right subtrees.

• If S is found as a subtree of T, return true; otherwise, return f...read more

Implement a stack with push, pop, top, isEmpty, and getMin operations in O(1) time complexity without using extra space for storing additional stack data structures.

• Use two stacks - one to store the actual elements and another to store the minimum element at each level.

• When pushing an element, compare it with the current minimum and update the minimum stack accordingly.

• For getMin operation, simply return the top element of the minimum stack.

• Ensure all operations like push, po...read more

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.

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

• Use binary search to find the first occurrence of the element.

• Use binary search to find the last occurrence of the element.

• Handle cases where the element is not present in the array.

Find the length of the longest decreasing subsequence in an array of integers.

• Use dynamic programming to keep track of the length of the longest decreasing subsequence ending at each index.

• Initialize an array to store the length of the longest decreasing subsequence for each element.

• Iterate through the array and update the length of the longest decreasing subsequence for each element based on previous elements.

• Return the maximum length of the longest decreasing subsequence fo...read more

Deep copy a linked list with random pointers and return its head.

• Create a deep copy of the linked list by creating new nodes rather than copying references.

• Ensure the random pointers are correctly pointing to the corresponding nodes in the cloned list.

• Implement the function to clone the linked list and return its head.

• Consider the constraints and input format provided in the problem statement.

• Explore if the cloning can be achieved without utilizing extra space.

Software testing is the process of evaluating a software item to detect differences between given input and expected output.

• Software testing ensures that the software is working as expected

• It helps to identify defects and errors in the software

• Testing can be done manually or using automated tools

• Types of testing include functional, performance, security, and usability testing

The problem involves finding the total number of unique paths from the top-left corner to the bottom-right corner of an M x N matrix by moving only right or down.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell in the matrix.

• Initialize the first row and first column with 1 as there is only one way to reach each cell in those rows and columns.

• For each cell (i, j), the number of unique paths is the sum...read more

Find the row and column in a binary matrix where all elements in the row are 0 and all elements in the column are 1.

• Iterate through each row and column to check for the conditions mentioned in the problem statement.

• If a row has all 0s and the corresponding column has all 1s, return the index of that row/column.

• If no such row/column exists, return -1.

Calculate the total amount of rainwater that can be trapped within given elevation map.

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

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

• Sum up the trapped water above each bar to get the total trapped water for the elevation map.

Find the most frequent and lexicographically smallest word in string 'A' that is not present in string 'B'.

• Split strings 'A' and 'B' into words

• Count frequency of each word in 'A'

• Check if word is not in 'B' and is the most frequent and lexicographically smallest

• Return the word or -1 if no such word exists

The task is to find pairs of elements in an array that sum up to a given target value.

• Iterate through the array and for each element, check if the complement (target - current element) exists in a hash set.

• If the complement exists, add the pair to the result list.

• Ensure pairs are sorted based on the criteria mentioned in the question.

Count the total number of inversions in an integer array.

• Iterate through the array and for each pair of elements, check if the conditions for inversion are met.

• Use a nested loop to compare each element with all elements to its right.

• Keep a count of the inversions found and return the total count at the end.

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

• Use a trie data structure to efficiently store and search for words in the dictionary.

• When solving a query, traverse the trie starting from the most recently queried character.

• Return true if a valid word is found in the trie, otherwise return false.

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

• Handle the case where the number of nodes left is less than K

Find the minimum number of jumps Bob needs to make from shop 0 to reach the final shop, or return -1 if impossible.

• Use Breadth First Search (BFS) to find the minimum number of jumps needed.

• Keep track of the maximum reachable index at each step.

• If the maximum reachable index is less than the current index, return -1 as it's impossible to reach the last shop.

Given a sorted doubly linked list of distinct nodes, find and count triplets with a sum equal to a given value 'X'.

• Iterate through the 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 and return it at the end.

• Handle edge cases like when the list has less than 3 nodes or no triplets are found.

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.

The Weighted Job Scheduling problem involves maximizing profit by scheduling non-overlapping jobs with start time, end time, and profit given.

• Sort the jobs based on their end times in ascending order.

• Use dynamic programming to keep track of the maximum profit that can be earned by including or excluding each job.

• For each job, find the maximum profit that can be earned by including it and excluding it.

• Choose the maximum profit from the two options for each job.

• Repeat the proce...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

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.

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

Check if two strings are anagrams of each other by comparing their sorted characters.

• Sort the characters of both strings and compare them.

• Use a dictionary to count the frequency of characters in each string and compare the dictionaries.

• Ensure both strings have the same length before proceeding with the comparison.

Find the length of the longest strictly increasing subsequence of heights of students in a row.

• Iterate through the heights array and for each element, find the length of the longest increasing subsequence ending at that element.

• Use dynamic programming to keep track of the longest increasing subsequence length for each element.

• Return the maximum length found in the dynamic programming array as the result.

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

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.

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.

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

Add two numbers represented as linked lists and return the sum as a linked list.

• Traverse both linked lists simultaneously while keeping track of carry.

• Create a new linked list to store the sum.

• Handle cases where one linked list is longer than the other.

• Ensure to update the carry for the next iteration.

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.

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

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.

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.

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.

Return the bottom view of a binary tree when viewed from left to right.

• Traverse the tree in level order and keep track of the horizontal distance and depth of each node

• For each horizontal distance, update the node in the map if it is deeper than the current node

• Return the values of the map in sorted order of horizontal distance

Find the length of the longest common subsequence between two given strings.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the lengths of common subsequences.

• Iterate through the strings to fill the array and find the longest common subsequence length.

Merge two sorted linked lists into a single sorted linked list without using additional space beyond constant space complexity.

• Create a dummy node to start the merged list

• Iterate through both linked lists and compare nodes to merge them in sorted order

• Update the next pointers accordingly

• Handle cases where one list is empty or both lists are empty

• Return the head of the merged linked list

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.

Count the number of islands in a grid of 0s and 1s connected horizontally, vertically, or diagonally.

• Iterate through the grid and perform depth-first search (DFS) to mark visited land cells and count islands

• Use a visited array to keep track of visited cells to avoid double counting

• Check all neighboring cells (horizontally, vertically, and diagonally) of a land cell during DFS

• Increment island count whenever a new island is encountered

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

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 from the starting cell to the last cell.

• Maintain a queue to keep track of the cells to be visited next.

• Consider the effect of snakes and ladders on the movement of the player.

• Return the minimum number of dice throws required to reach the last cell, or -1 if unreachable.

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

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.

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.

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

The task is to calculate the total number of unique paths from the top-left to bottom-right corner of an M x N matrix by moving only right or down.

• Use dynamic programming to solve this problem efficiently.

• Create a 2D array to store the number of unique paths for each cell in the matrix.

• Initialize the first row and first column with 1 as there is only one way to reach each cell in the first row and column.

• For each cell (i, j), the number of unique paths is the sum of the paths...read more

Check if a given singly linked list of integers is a palindrome or not.

• Traverse the linked list to find the middle element using slow and fast pointers.

• Reverse the second half of the linked list.

• Compare the first half with the reversed second half to check for palindrome.

• Handle odd and even length linked lists separately.

• Example: For input 1 2 1 -1, the linked list is a palindrome.

Merge two sorted linked lists into a single sorted linked list.

• Create a dummy node to start the merged list

• Compare nodes from both lists and add the smaller one to the merged list

• Move the pointer of the merged list and the list with the smaller node

• Handle cases where one list is exhausted before the other

• Return the head of the merged list

Implement a program to compress a string by replacing consecutive duplicates with the count of repetitions.

• Iterate through the string and keep track of consecutive characters and their counts.

• Replace consecutive duplicates with the count of repetitions.

• Ensure the count of repetitions is ≤ 9.

• Return the compressed string.

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.

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.

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

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

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For a node with data 4, left subtree nodes (2, 1, 3) are smaller and right subtree node (5) is larger.

Flatten a linked list of sorted child linked lists into a single sorted linked list.

• Traverse the linked list and maintain a priority queue to keep track of the next smallest element.

• Merge the child linked lists into the priority queue while traversing the main linked list.

• Pop elements from the priority queue to create the final flattened linked list.

Search for integers in a rotated sorted array efficiently.

• Use binary search to find the pivot point where the array is rotated.

• Based on the pivot point, apply binary search on the appropriate half of the array.

• Return the index of the integer if found, else return -1.

Find the maximum element between two nodes in a Binary Search Tree (BST) path.

• Traverse the BST to find the path between NODE1 and NODE2.

• Keep track of the maximum element encountered in the path.

• Return the maximum element found, or -1 if NODE1 or NODE2 are not in the BST or no elements exist between them.

Convert a Binary Search Tree to a Greater Sum Tree by replacing each node's value with the sum of all node values greater than the current node's value.

• Traverse the BST in reverse inorder (right, root, left) to visit nodes in descending order.

• Keep track of the running sum of visited nodes and update each node's value with this sum.

• Modify the BST in place without creating a new tree.

• Example: Input BST: 4 1 6 0 2 5 7 -1 -1 -1 3 -1 -1 -1 -1. Output Greater Sum Tree: 26 30 21 36 ...read more

Calculate the height of a Binary Tree using Inorder and Level Order traversals without constructing the tree.

• Use the properties of Inorder and Level Order traversals to determine the height of the Binary Tree.

• The height of a Binary Tree is the number of edges on the longest path from the root to a leaf node.

• Consider edge cases like a single node tree or empty tree while calculating the height.

Generate a pattern of numbers in rows following a specific sequence based on powers of 2.

• Start with 1 number in the first row, 2 numbers in the second row, 4 numbers in the third row, and so on based on powers of 2.

• Fill the pattern with numbers in increasing sequence from 1 to 9, recycling back to 1 after reaching 9.

• Output the pattern for a given number 'N' of rows.

• Example: For N = 4, the pattern would be 1, 23, 4567, 89123456.

Find pairs of nodes in a BST that sum up to a given value 'S'.

• Traverse the BST in-order to get a sorted list of nodes.

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

• Keep track of visited nodes to avoid using the same node twice in a pair.

Find the maximum element in the path from NODE1 to NODE2 in a Binary Search Tree.

• Traverse the BST from NODE1 to NODE2 while keeping track of the maximum element encountered.

• If NODE1 or NODE2 does not exist in the BST, return -1.

• The path does not include the values of NODE1 and NODE2 themselves, except when no intermediary nodes exist.

Given a matrix of characters, determine if a word can be formed by selecting adjacent characters.

• Parse input to get matrix dimensions, characters, and queries

• For each query, search for the word in the matrix by checking adjacent characters

• Output '1' if word is present, '0' if not

Find the length of the longest substring without repeating characters in a given string.

• Use a sliding window approach to keep track of the longest substring without repeating characters.

• Use a hashmap to store the index of each character as it appears in the string.

• Update the start index of the window when a repeating character is found.

• Calculate the maximum length of the window as you iterate through the string.

• Return the maximum length as the result.

Identify missing numbers within the range of smallest and largest elements in an array.

• Find the smallest and largest elements in the array.

• Generate a list of numbers within the range of smallest and largest elements.

• Remove the numbers that are present in the array to get the missing numbers.

• Sort and return the missing numbers.

Given a string, partition it into palindromes and return all possible configurations.

• Use backtracking to generate all possible palindrome partitions

• Check if each substring is a palindrome before adding it to the partition

• Return all valid partitions as an array of strings

Print all possible paths from top-left to bottom-right in a matrix by moving only right or down.

• Use backtracking to explore all possible paths from top-left to bottom-right in the matrix.

• At each cell, recursively explore moving right and down until reaching the bottom-right corner.

• Keep track of the current path and add it to the result when reaching the destination.