vsounda1@binghamton.edu
BAN USERI have O(N*M) solution,
Where N is the number of pairs in the Set
and M is length of the given Range
in the given example N = 8 ; M = (13-3);
This is better than O(N log N) in the cases where N is scaled exorbitantly and M is a normal range like (3,13).
Its worse when the range is like (2,1000000).
Approach:
Make an array of integers spanning the given range. (here [3,4,...13]).
For each pair in the given set,
For each int in the array
if (Pair covers the integer && Pair is bigger than the existingPair that covers)
Mark as covered by Pair
Now the array of covered pairs is the answer.
The Code:
public class Ranger {
private static void doAction(int[] key,pair<Integer,Integer>[] ans,pair<Integer,Integer>[] set)
{
int i;
for(pair<Integer,Integer> s : set)
{
for(i=0;i<key.length;i++)
{
if(covers(key[i],s))
{
if((s.second-s.first)>=(ans[i].second-ans[i].first))
{
ans[i]=s;
}
}
}
}
}
private static boolean covers(int k, pair<Integer,Integer> p)
{
boolean a = false;
if(k>(p.first-1) && k<(p.second+1))
{
a = true;
}
return a;
}
public static void main(String args[])
{
String set = "(1,4);(30,40);(20,91);(8,10);(6,7);(3,9);(9,12);(11,14)";
pair<Integer,Integer> range = new pair(3,13);
pair<Integer,Integer>[] setArray;
String[] sArray = set.split(";");
setArray = new pair[sArray.length];
String[] vals;
int i =0;
for(String s : sArray)
{
s = s.substring(1, s.length()-1);
vals = s.split(",");
setArray[i]= new pair(Integer.parseInt(vals[0]),Integer.parseInt(vals[1]));
i++;
}
int[] hashArray = new int[range.second-range.first];
pair[] answer = new pair[range.second-range.first];
Arrays.fill(answer, new pair(0,0));
int f = range.first;
int j;
for(j=0;j<hashArray.length;j++,f++)
{
hashArray[j]=f;
}
doAction(hashArray,answer,setArray);
System.out.println(answer[0].first+","+answer[0].second);
for(j=1;j<answer.length;j++)
{
if(answer[j].first!=answer[j-1].first && answer[j].second!=answer[j-1].first)
System.out.println(answer[j].first+","+answer[j].second);
}
}
}
So How does the algorithm decide where to stop reversing the list before checking for palindrome?
If it is exactly halfway through then the solution wouldn't work if the palindrome is not the entire list.
Considering "madam", in a list as "amadamosel".
here "ama","ada","madam" are the palindromes, only Madam is the answer.
a series of mod operations would do the trick
public class numLetters {
public static void main(String args[])
{
System.out.println( new StringBuilder(findLetters(1)).reverse().toString() );
}
public static String findLetters(int N)
{
String val = "null";
if(N>0)
{
int x = N % 26;
int y = (N-x)/26;
if(y>0)
{
val = getLetter(x)+findLetters(y);
}
else
{
return getLetter(x);
}
}
else
{
return " ";
}
return val;
}
public static String getLetter(int n)
{
String val = "";
switch(n)
{
case 0: val="z"; break;
case 1: val="a"; break;
case 2: val="b"; break;
case 3: val="c"; break;
case 4: val="d"; break;
case 5: val="e"; break;
case 6: val="f"; break;
case 7: val="g"; break;
case 8: val="h"; break;
case 9: val="i"; break;
case 10: val="j"; break;
case 11: val="k"; break;
case 12: val="l"; break;
case 13: val="m"; break;
case 14: val="n"; break;
case 15: val="o"; break;
case 16: val="p"; break;
case 17: val="q"; break;
case 18: val="r"; break;
case 19: val="s"; break;
case 20: val="t"; break;
case 21: val="u"; break;
case 22: val="v"; break;
case 23: val="w"; break;
case 24: val="x"; break;
case 25: val="y"; break;
default : val=" "; break;
}
return val;
}
}
public class sumCons
{
static int doesSum(int a, int N)
{
int sum = a;
while(sum<N && a>0)
{
sum = sum+(a-1);
a--;
}
if(sum==N)
{
return a;
}
else
{
return -1;
}}
public static void main(String args[])
{
int X = args[0];
int b;
int a = X/2;
while(a>1)
{
b = doesSum(a,X);
if(b!=-1)
{
System.out.println("("+b+","+a+")");
}
a--;
}
}
}
External Sorting is the standard way to do this.
First We start by fetch pages of the 50GB array into the memory.
For 200MB RAM, lets consider the page size for the machine to be say 10MB.
# We will fetch the first 10 Pages of the array (100MB of RAM is used)
# perform quick sort on each page
# No we have 10 pages of sorted Integers
# Merge Sort the 10 pages into new page of 100MB (all 200MB used)
# write back to the array the first 10 pages of data
# repeat for the next 10 pages. (50GB/100MB times)
** Now we have an array of 50GB where every 100MB is individually sorted. i.e 512 blocks of sorted integers
# Lets consider 512 as 4 parts of 128 blocks
# fetch first 1MB of 128 blocks of the first part
# Merge sort and keep writing into disk (at a new place)
# Use Double Cache (when 1MB of a block is done, discard it and get the next 1MB)
# Do same to the other three parts.
# Do the another double cached merge sort over these new 4 parts and overwrite on the old array.
This is one way of doing it, any comments on improving this approach is welcomed.
This can be improved,
- vsounda1@binghamton.edu January 06, 2016where N will only the Sets that can potentially cover the range