GReeky
BAN USERpublic static void replaceChars(String s)
{
if((s==null)||(s.length()==0))
{
return;
}
int count=0;
for(int i=0;i<s.length();i++)
{
if(s.charAt(i)=='?')
{
count++;
}
}
if(count>0)
{
replaceWithPermutations(s,count,0);
}
}
public static void replaceWithPermutations(String str, int count, int i)
{
if(count==0)
{
System.out.println(str);
}
else
{
if(str.charAt(i)=='?')
{
str = str.substring(0,i)+0+str.substring(i+1,str.length());
replaceWithPermutations(str,count-1,i+1);
str = str.substring(0,i)+1+str.substring(i+1,str.length());
replaceWithPermutations(str,count-1,i+1);
}
else
{
replaceWithPermutations(str,count,i+1);
}
}
}
- GReeky June 02, 2014I am passing n as the parameter which is the number of numbers forming the tree. It does not matter because the numbers are unique and we do not care about the order.
static int count =0;
public static int maxBST(int n)
{
if(n==0)
return 1;
if(n<3)
return n;
if(n==3)
return 5;
for(int i=0;i<n;i++)
{
count+= maxBST(i)*maxBST(n-i-1);
}
return count;
}
public String largestEvenPalindrome()
{
int low=0,high=0,count=0;
//values for the highest length palindrome
int pLow=0,pHigh=0,pHighestCount=0;
for(int i=0;i<s.length()-1;i++)
{
//low and high correspond to the adjacent cells
low=i;
high=i+1;
count=0;
while((low>=0)&&(high<=s.length()-1))
{
if(s.charAt(low)!=s.charAt(high))
break;
else
{
//if 2 adjacent cells have the same character, we move low and high //away from each other each time as long as there is a match
low--;
high++;
count+=2;
}
if(count>pHighestCount)
{
pHighestCount=count;
pLow=low+1;
pHigh=high-1;
}
}
}
if(pHigh!=0)
return s.substring(pLow, pHigh+1);
else
return null;
}
- GReeky January 16, 2014
This question was asked in my google interview. I could come up with the worst case complexity solution, but that is O(m^2 * n^2). He asked for a better complexity and I started with making a Point class with x,y coordinates and adding the points with 1 at the position in the ArrayList<ArrayList<Point>> list. Each index in this list denotes a new row. You can ignore the inner lists with size < 1. I messed up when I told the complexity though. He said I need to wrap up and his last question was complexity. The answer is: If there are maximum of k 1s in any row in mXn matrix, then it's (mC1 * kC2 * (m-1)C1 * kC2) which is O(m^2 * k^2). I instead told him its O(k1^4) where k1 is the total number of 1s. :(
- GReeky June 11, 2014