editing distance
Finding the Minimum Window in S which Contains All Elements from T
Given a set T of characters and a string S, find the minimum window in S which will contain all the characters in T in complexity O(n).
eg,
S = “ADOBECODEBANC”
T = “ABC”Minimum window is “BANC”.
Finding the Minimum Window in S which Contains All Elements from T
Replace all occurrence of the given pattern to ‘X’.
For example, given that the pattern=”abc”, replace “abcdeffdfegabcabc” with “XdeffdfegX”. Note that multiple occurrences of abc’s that are contiguous will be replaced with only one ‘X’.
solution: keep a slow and a fast pointer.
Replace all occurrence of the given pattern to ‘X’
Kadane's Algorithm Largest sum sub-sequence and sub-matrix
- Problem 1 : Given a sequence of n integers ( +ve and/or -ve ) find a contiguous subsequence with the largest sum. By contiguous subsequence I mean if the i-th element and j-th element of the original sequence are in the subsequence for ( i \leq j ) then \forall k, i \leq k \leq j k-th element is in the subsequence.
Example : sequence : 1 5 -9 2 4 3 8
desired subsequence : 2 4 3 8
http://wordaligned.org/articles/the-maximum-subsequence-problem
if empty subsequence is not accounted as 0.
code refer http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html
void kadane(int input[], int n, int &x1, int &x2, int &max)
{
int cur, i;
max = 0;
cur = 0;
x1 = x2 = 0;
int lx1, lx2;
lx1 = 0;
for(int i = 0; i<n; i++)
{
cur = cur+input[i];
if(cur > max)
{
max = cur;
x2 = i;
x1 = lx1;
}
if (cur < 0)
{
cur = 0;
lx1 = i + 1;
}
}
}
- Problem 2 : Given a m x n matrix A, find a submatrix of A such that sum of all the elements of the submatrix is the largest amongst all possible submatrices.
Example :
1 2 -1
-3 -1 4
1 -5 -2
Desired sub matrix :
2 -1
-1 4
this idea behind this is : The idea behind the 2D algorithm is that we use brute force on one coordinate(row) and the 1D algorithm on the other.
code refer : http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html
#include<iostream>
using namespace std;
#define M 10
#define N 10
main()
{
int tmp[100], n, x1, x2;
int cur, max_sum, fx1, fx2, fy1, fy2;
int i,j,k;
int input[M][N];
fx1 = fx2 = fy1 = fy2 = max_sum = cur = -1;
for (i=0; i< M; i++)
{
for(k=0; k<N; k++)
tmp[k] = 0;
for (j=i; j<M; j++)
{
for(k=0; k<N; k++)
tmp[k] += input[j][k];
kadane(tmp, N, x1, x2, cur);
if (cur > max_sum)
{
fy1 = x1;
fy2 = x2;
fx1 = i;
fx2 = j;
max_sum = cur;
}
}
}
cout << "max Sum = " << max_sum << " from (" << fx1 << "," << fy1 << ") to ("
<< fx2 << "," << fy2 << ")" << endl;
}
http://discuss.joelonsoftware.com/default.asp?interview.11.784947.1
not sure the explaining is right or not. http://tech-queries.blogspot.com/2010/05/find-max-sum-in-2d-array.html