Find preorder traversal of a binary tree from its inorder and postorder sequence
Write an efficient algorithm to find a binary tree’s preorder traversal from its inorder and postorder sequence without constructing the tree.
Tag: Hard
Find all n-digit numbers with equal sum of digits at even and odd indices
Find all n–digit numbers with an equal sum of digits at even and odd index, where n varies from 1 to 9.
Design a stack that returns the minimum element in constant time
Design a stack to support an additional operation that returns the minimum element from the stack in constant time. The stack should continue supporting all other operations like push, pop, top, size, empty, etc., with no degradation in these operations’ performance.
Find the maximum sum path between two leaves in a binary tree
Given a binary tree, write an efficient algorithm to find the maximum sum path between any two leaves in it.
Find the index of a row containing the maximum number of 1’s in a binary matrix
Given a binary M × N row-wise sorted matrix, find a row that contains the maximum number of 1’s in linear time.
Find all nodes at a given distance from leaf nodes in a binary tree
Given a binary tree, write an efficient algorithm to find all nodes present at a given distance from any leaf node. We need to find only those nodes that are present in the root-to-leaf path for that leaf.
Fix a binary tree that is only one swap away from becoming a BST
Given a binary tree that is only one swap away from becoming a BST, convert it into a BST in a single traversal.
Find the maximum absolute difference between the sum of two non-overlapping subarrays
Given an array, find the maximum absolute difference between the sum of elements of two non-overlapping subarrays in linear time.
Reverse bits of an integer using a lookup table
Given an integer, reverse its bits using binary operators and lookup table in linear time.
Collect maximum value of coins in a matrix
Given an M × N matrix where each cell contains a coin of some denomination, collect the maximum value of coins by traversing the grid.
Find minimum operations required to transform a string into another string
Given two strings, determine if the first string can be transformed into the second string. The only operation allowed is moving a character from the first string to the front. If the string can be transformed, find the minimum number of operations required for the transformation.
Check if a string matches with the given wildcard pattern
Given a string and a pattern containing wildcard characters, write an efficient algorithm to check if the string matches with the wildcard pattern or not.