CodePredator
BAN USERHere is the method that I thought :
Maintain a sorted array of long//lat of all places, sorted first by longitude and second by latitude.
If we have to find all places from point (a,b) with in a radius of r.
1) find all the places within the longitude range a+r and a-r and latitude range b+r and b-r (Use Binary search on sorted array to find this range of places).
2) Now for these points use the expression (x-a)^2+(y-b)^2 -r^2 to decide whether they lie inside or outside the given radius.
a) if (x-a)^2+(y-b)^2 -r^2 > 0 it lies outside the given radius
b) if (x-a)^2+(y-b)^2 -r^2 < 0 it lies inside the given radius
1. We can take the file in 300 MB blocks approx (make sure the blocks end at word endings) and reverse the order of blocks in the file.
2. Then go to each block and reverse words in it.
@job_hungry : the question clearly says they are sorted arrays, that means the objects in it are comparable. If they are not comparable the best method I can think of is putting it into a Hash Set.
- CodePredator April 16, 2013Use newton-raphson method. to find the root upto the required precision.
xn+1 = xn- f(xn)/f'(xn)
Build A suffix tree. Find the deepest non-leaf node in the tree ( deepest here means max no of chars from root to that node). The chars in this path from root to this node will give the longest common substring.
- CodePredator February 12, 2013Oh....Ok...Got it !!!Kandane's Algorithm requires it
- CodePredator February 07, 2013This algorithm does not work because you are not checking whether entire left-sub tree is lesser than the 'node->value' and entire right subtree is greater than the 'node->value'.
- CodePredator December 21, 2012I have taken care of repetitions.
I have put comments for those lines. Is there a problem in that line?
Just do it the way we manually do it :
Sort the string and swap elements of the string in lexicographic order, while doing this keep count of the number strings that come before the current string in lexicographic order.
Also take care of duplicates while counting and swapping.
Eg:
For string 'dbace' :
1. sort : abcde
2. count permutation starting with a : 24
3. count permutation starting with b : 24
4. count permutation starting with c : 24
5. count permutation starting with 2nd letter as a : 6
int findCount(string str, int start, int end)
{
int length = end-start+1;
int count = factorial(length);
int i=start;
while(i< end)
{
int rep=1;
bool flag = true;
while(str[i] == str[i+1]) //counting number of repitions
{
flag = false;
rep++;
i++;
}
if(flag)
i++;
count = count/ factorial(rep); //dividing by repitions!
}
return count;
}
int permRank(string str)
{
if(str == "")
return 0;
int count =0;
string sorted(str);
sort(sorted.begin(),sorted.end());
for(int i=0;i<sorted.length()-1;i++)
{
int rem;
int j=i+1;
while(sorted[i] != str[i])
{
rem = findCount(sorted,i+1,sorted.length()-1);
count += rem;
cout<<sorted<<"--->"<<rem<<endl;
while(sorted[i] == sorted[j]) // don't swap if there is a duplicate
j++;
swap(sorted,i,j);
j++;
}
}
return count;
}
Yes...this method produces duplicates because
if(i>pos && input[i]==input[i-1]) continue;
this check will only work if you maintain the sorted order throughout all the recursive calls.
I think this will work :
public static void permute(char[] input, int pos, ArrayList<String> result){
if(pos==input.length){
result.add( new String(input));
return;
}
int i;
for(i=pos;i<input.length;i++){
int j;
for(int i=pos;i< str.length();i++)
{
j=pos;
if(i!=pos)
{
for(;j<i;j++)
{
if(str[j] == str[i]) //check if str[i] occurs in str[pos......i-1]
break;
}
}
if(j<i)
continue;
char tmp = input[pos];
input[pos] = input[i];
input[i] = tmp;
Permutation.permute(input, pos+1, result);
tmp = input[pos];
input[pos] = input[i];
input[i] = tmp;
}
}
Wow!!!I didnt get it first time I saw it!!!
- CodePredator November 06, 2012But the space needed in this method is also bounded by O(h). Storing in array would need O(n).
- CodePredator November 05, 2012We can do it in O(h) complexity by using the following method:
1. Search for the element 'n' in the BST, as you search add the elements in the path to a stack
2. If element is found and the element has a right subtree, the leftmost element in the right subtree will be the next biggest element.
3. If element is not found or the element is found but does not have right subtree, then pop elements from the stack until you find an element that is greater than 'n'. This will be the next biggest element.
Funda : by maintaining a stack we can traverse back and easily find the inorder successor with in O(h) time.
/* Begin with sum as 0 and max as root->info*/
int maxPathSum(Node root, int sum, int max)
{
if(root == NULL)
return max;
int newSum;
int newMax;
if(sum<0)
newSum = root->info;
else
newSum = root->info + sum;
int lMax,rMax;
if(newSum > max)
newMax = newSum;
else
newMax = max;
int lMax = maxPathSum(root->left, newSum, newMax);
int rMax = maxPathSum(root->right,newSum, newMax);
if(lMax > rmax)
return lMax;
else
return rMax;
}
1. Sort the strings in the file, based on their length.
- CodePredator May 01, 20132. Build a common suffix tree for all these words, in the above sorted order.
3. If a word can be inserted to the suffix tree without adding any direct child to the root node,
then it means that it is a combination of two words that have been already added to the suffix tree.
For eg: if we have inserted 'there' and 'after' to the suffix tree, then for adding 'thereafter' to the suffix tree we don't need to add a direct child to the root node of the suffix tree. So it is a combination of two other words.
Complexity : O(nlogn) considering that building suffix tree would take O(n) time.