Reyhan JB
BAN USERWell, I believe the solution is very simple. You just need to compare suffixes of reverse string with prefixes of input string and find the longest in common. there is no need to construct a prefix/suffix tree (You can, but I didn't for sake of simplicity). Here is the code in Java, with O(n). Note that you can combine the last three loops in one, and avoid using additional space I used for tmp1[] and tmp2[].
public static int getMinCharToPalindrom2(String input){
//Create the reverse of input string
StringBuffer sb = new StringBuffer();
for(int i=input.length()-1; i> -1; i--)
sb.append(input.charAt(i));
String reverse = sb.toString();
String[] tmp1= new String[reverse.length()];
String[] tmp2 = new String[input.length()];
//Populate an array with suffixes of reverse string, such that array[0] contains the shortest suffix
for(int i=reverse.length()-1; i>-1; i--)
tmp1[reverse.length()-i-1] = reverse.substring(i,reverse.length());
//Populate an array with prefixes of input string, such that array[0] contains the shortest prefix
for(int i=0; i<input.length(); i++)
tmp2[i] = input.substring(0,i+1);
//Start from the end of arrays, and find the biggest sub-string in common
for(int i=input.length()-1; i>-1; i--){
if(tmp1[i].equals(tmp2[i])){
return (2*input.length())-tmp1[i].length();
}
}
return -1;
}
Given a list of busy times as "Pairs", I first derive the free time intervals for each person, and the check how these free times overlap. The algorithm is of linear complexity.
public class findFreeTime {
public static List<Pairs> find(List<Pairs> busy1, List<Pairs> busy2){
List<Pairs> output = new ArrayList<>();
List<Pairs> free1 = freeTimes(busy1);
List<Pairs> free2 = freeTimes(busy2);
while(free1.size() != 0 && free2.size() != 0){
Pairs overlap = doOverlap(free1.get(0), free2.get(0));
if(overlap.start == -1 || overlap.end == -1){//checks if the pair is invalid and two pairs don't overlap
if(free1.get(0).start < free2.get(0).start)
free1.remove(0);
else
free2.remove(0);
}
else
output.add(overlap);
}
return output;
}
//Checks if two pairs have an overlap. If they do, return the overlap. Otherwise, returns an invalid pair
private static Pairs doOverlap(Pairs p1, Pairs p2){
int start = -1,end = -1;
if(p1.start >= p2.start){
if(p1.start <= p2.end){
start = p1.start;
if(p1.end <= p2.end)
end = p1.end;
else
end = p2.end;
}
}
else{
if(p2.start <= p1.end){
start = p2.start;
if(p2.end <= p1.end)
end = p2.end;
else
end = p1.end;
}
}
return new Pairs(start,end);
}
//Derive the free times out of busy times
private static List<Pairs> freeTimes(List<Pairs> input){
List<Pairs> output = new ArrayList<>();
for(int i=0; i<input.size(); i++){
if(i != input.size()-1){
Pairs p = new Pairs(input.get(i).end,input.get(i+1).start);
output.add(p);
}
else{
if(input.get(i).end < 30){
Pairs p = new Pairs(input.get(i).end+1,30);
output.add(p);
}
}
}
return output;
}
private static class Pairs{
int start;
int end;
public Pairs(int start, int end){
this.end = end;
this.start = start;
}
}
}
Dynamic Programming solution in java:
public static int find(int N){
int[] tmp = new int[N+1];
tmp[0] = 0;
for(int i=1; i< N+1; i++){
int count = 2;
int min = tmp[i-1]+1;
while(i-Math.pow(count, 2) > -1){
min = Math.min(tmp[(int) (i-Math.pow(count, 2))]+1, min);
count++;
}
tmp[i] = min;
}
return tmp[N];
}
public int findMaxqaz(List<Integer> input){
int size = input.size();
List<Integer> qaz = new ArrayList<>();
Map<Integer,Integer> map = new HashMap<>();
for(int i=0; i<input.size(); i++)
map.put(input.get(i), size-i);
List<Integer> sortedKeys = new ArrayList<>(map.keySet());
Collections.sort(sortedKeys);
for(int i=0; i<sortedKeys.size(); i++)
qaz.add(Math.min(size-i, map.get(sortedKeys.get(i))));
Collections.sort(qaz);
return qaz.get(qaz.size()-1);
}
Repkylecfarrell, Personnel at Bocada
Property custodian with a reputed organization and help in keeping accurate check over the supplies and inventory of materials and ...
Your solution is correct, but always increases the size of result by one, which is a design flaw. For example, if you have a=123 and b=256, c=a+b would be 0379 instead of 379. You can prevent it by just checking if summing two numbers will have a carry-on on the highest order digit or not by few lines of code.
- Reyhan JB September 04, 2015Your solution also does not consider the fact that big numbers are signed or not signed.