Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below. For example, given the following triangle [2], [3,4], [6,5,7], [4,1,8,3] The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11). But […]
Category Archives: Algorithms
Given a random string S and another string T with unique elements, find the minimum consecutive sub-string of S such that it contains all the elements in T. For example: S=adobecodebanc T=abc answer=’banc’ The problem is similar to find all anagram of a string as substring of another given string. Please read my previous article here to […]
Given a binary tree, find out the minimum length sum path form root to leaf with sum S. What about finding minimum length sum path for BST? How does BST improve the search? For example, the min length path for sum S=13 in T1 is 2 (6–>7 not, 6–>4–>3). For T2 min length path for […]
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems. […]
Given that integers are read from a data stream. Find median of elements read so for in efficient way. For example, median of the stream, A = [1, 5, 3, 2, 6, 2, 3] is = 3. Note that we need to find the running median at any time of the stream. That is each […]
Given a 2D array with rows sorted in ascending order. Find the median of the whole 2D array. For example, A= 2, 4, 5, 6 1, 2, 2 ,4 3, 4, 4, 5 1, 2 , 3, 3 Then the merged array would be [1, 1, 2, 2 ,2, 2, 3, 3, 3, 4, 4, […]
For an array of integers, a surpasser of an integer element is an element on its right hand side that is larger than it. Given an array of integers, Output the max number of surpassers. For example, {10,3,4,5,2}, the surpassers of 3 is 4 and 5, and 10 doesn’t have any surpasser. Basically, we need […]
Given an array of integer. Find the maximum sum subsequence such that elements are not consecutive. For example, A = [−2, 1, −3, 4, −1, 2, 1, −5, 4] then max sum=11 with the subarray [1, 4, 2, 4]. First of all, lets solve the problem with less constraint. Suppose we need to find out […]
Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time. For example – { (0,2), (3, 7), (4,6), (7,8), (1,5) }. The maximum number of intervals overlapped is 3 during (4,5). A very simple solution would be check the ranges pairwise. This is certainly very […]
Given n non-negative integers representing the height of bars of width one of a histogram, find the maximum area rectangle of histogram i.e. the maximum area rectangle contained in the histogram. For example, H = [4, 2, 1, 8, 6, 8, 5, 2] then the histogram has a rectangle of area of 20 showed in […]