Longest Common Prefix (LCP) Problem
Write an efficient algorithm to find the longest common prefix (LCP) between a given set of strings.
Tag: Recursive
Find the odd occurring element in an array in logarithmic time
Given an array of n integers where every element appears an even number of times except one element, which appears an odd number of times, find that odd occurring element in logarithmic time and constant space.
Find the length of the longest path in a matrix with consecutive characters
Given an M × N matrix of characters, find the length of the longest path in the matrix starting from a given character. All characters in the longest path should be increasing and consecutive to each other in alphabetical order.
Replace all occurrences of 0 that are surrounded by 1 in a binary matrix
Given an M × N binary matrix, replace all occurrences of 0’s by 1’s, which are completely surrounded by 1’s from all sides (top, left, bottom, right, top-left, top-right, bottom-left, and bottom-right).
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.
Pots of Gold Game Problem using Dynamic Programming
There are two players, A & B, in the Pots of the gold game, and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot, and each player gets alternating turns in which the player can pick a pot from one of the ends of the line.
Reverse an array in C++
This post will discuss how to reverse an array in C++.
Print right view of a binary tree
Given a binary tree, write an efficient algorithm to print its right view. For example, the right view of a given binary tree is 1, 3, 6, 8.
Construct an ancestor matrix from a binary tree
Given a binary tree whose nodes are labeled from 0 to N-1, construct an N × N ancestor matrix. An ancestor matrix is a boolean matrix, whose cell (i, j) is true if i is an ancestor of j in the binary tree.
Construct a height-balanced BST from a sorted doubly linked list
Given a sorted doubly linked list, in-place convert it into a height-balanced Binary Search Tree (BST). The difference between the height of the left and right subtree for every node of a height-balanced BST is never greater than 1.
Find all employees who directly or indirectly reports to a manager
Given a map containing employee to manager mappings, find all employees under each manager who directly or indirectly reports him.
Find postorder traversal of a binary tree from its inorder and preorder sequence
Write an efficient algorithm to find postorder traversal on a given binary tree from its inorder and preorder sequence.