careerup007tm
BAN USERFarthest is not very clear. In below tree if we compare N7-N9 vs N7-N6 which pair is farthest?
N1
/ \
N2 N3
/ /\
N4 N5 N6
/\ /\
N7 N8 N9 N10
public static int findSubStringMaxLength(String master, String scan)
{
int currLen = 0, maxLen = 0;
char charBeforeStar = '~';// ~ is just a falg to indicate we are out of the * mode
int i = 0, j = 0, k = 0;
int masterLen = master.length();
int scanLength = scan.length();
// We need to search starting from each index of master, this is to find the max length match.
for (k = 0; k < masterLen; ++k)
{
// Loop on the scan and try to match from master starting from index k
charBeforeStar = '~';
currLen = 0;
for (i = 0, j = k; i < scanLength; ++i)
{
if (j >= masterLen)// This means we hit the end of master but not yet done with the scan
break;
// check if next char is '*' if yes increment pointer i by 2 and conitnue to search
if (i < scanLength - 1)
{
if (scan.charAt(i + 1) == '*')
{
charBeforeStar = scan.charAt(i);
i++;
continue;
}
}
// If it match increment both pointer i and j by one and also the length and
// change the flag for charBeforeStar back to ~, meaning we are
// not in the star mode.
if (scan.charAt(i) == '.' || scan.charAt(i) == master.charAt(j))
{
++j;
++currLen;
if (i == scanLength - 1)// This means we found a match capture the length
{
if (currLen > maxLen)
maxLen = currLen;
}
if (charBeforeStar != '~' && i == scanLength - 1 && j < masterLen)//Match found but need to continue to find longer match
;
else
{
charBeforeStar = '~';
continue;
}
}
// We are in starMode and we move in master but not in scan
if (charBeforeStar != '~')
{
if (charBeforeStar == '.' || charBeforeStar == master.charAt(j))
{
++j;
++currLen;
--i;// to make sure we dont move in scan String
continue;
} else
charBeforeStar = '~';
}
// we are here means the search has failed or not started yet.
break;
}// end of for loop
if (currLen > maxLen && i == scanLength)
{
maxLen = currLen;
}
currLen = 0;
if(masterLen-k<maxLen)
break;
}// outer for loop
return maxLen;
}
public static void updateMatrix(int a[][]) {
int N = a.length;
int M = a[0].length;
//additional array space = N+M
int a1[] = new int[N];// N
int b1[] = new int[M];// M
int i = 0, j = 0;
//We store the 'OR' of rows in a1 and 'OR' of coulmns in b1
for (i = 0; i < N; ++i)
for (j = 0; j < M; ++j) {
a1[i] |= a[i][j];
b1[j] |= a[i][j];
}
//update the original array with a1|b1
for (i = 0; i < N; ++i)
for (j = 0; j < M; ++j) {
a[i][j] = a1[i] | b1[j];
}
}
public static boolean listPalindromeCheck(LinkedList<Character> list)
{
int sz = list.size()/2;
char[] arr1=new char[sz];
ListIterator<Character> itr=list.listIterator();
int i=0;
for (i=0;i<sz;++i)
arr1[i]=itr.next();
if(list.size()%2>0)
itr.next();
for(--i;i>=0;--i)
{
if(arr1[i] != itr.next().charValue())
return false;
}
return true;
}
public static int[] addArray(int[] ar1, int ar2[])
{
int counter1=ar1.length-1;
int counter2=ar2.length-1;
int counter3= (counter1>counter2?counter1:counter2 )+1;
int[] ar3 = new int[counter3+1];
int carry=0;
while(counter3>-1)
{
if(counter1>=0) carry+=ar1[counter1--];
if(counter2>=0) carry+=ar2[counter2--];
ar3[counter3--]=carry%10;
carry /= 10;
}
return ar3;
}
When they ask you to write code, do you have to write them on a piece of paper or you have a PC file editor?
- careerup007tm May 26, 2012
Input:
- careerup007tm June 01, 2012090m90mm90mmm90mm90m909
0m*9
Output:
5
5 is correct for this pattern. 21 is wrong.