WAP to do AutoCorrection of Word Using Trie

/*
ASSUMPTIONS:
All characters are case insensitive
ENHANCEMENTS:
Auto correction of word
Display all words in postorder

SAMPLE DATA: - ALGO, ALL, ALSO, ASSOC, TREE, TRIE

+--> [G] ---+--> [O]
|
+--> [L] ---+--> [L]
| |
+--> [A] ---+ +--> [S] ---+--> [O]
| |
| +--> [S] ---+--> [S] ---+--> [O] ---+--> [C]
[\0] ---+
| +--> [E] ---+--> [E]
| |
+--> [T] ---+--> [R] ---+
|
+--> [I] ---+--> [E]

*/

#include
#include

using namespace std;

class trie
{
private:
struct node
{
char character; // character of the node
bool eow; // indicates a complete word
int prefixes; // indicates how many words have the prefix
node* edge[26]; // references to all possible sons
}*root; // trie root node

void preorder_display(node *); // preorder display
void truncate_node(node *); // Deletes node and sub-nodes
void delete_node(node *); // Deletes node if prefixes is 1

public:
trie(); // constructor
~trie(); // destructor

void insert_word(char *); // to insert a word
void delete_word(char *); // to delete a word
bool search_word(char *); // to search a word

void display(); // display complete trie
};

trie::trie()
{
root = new node();
root->character = '\0';
root->prefixes = 0;
root->eow = false;
for(int i=0;i<26;i++)
{
root->edge[i] = NULL;
}
}

trie::~trie()
{
truncate_node(root);
}

void trie::truncate_node(node* n)
{
for(int i=0;i<26;i++)
{
if(n->edge[i] != NULL)
{
truncate_node(n->edge[i]);
}
}
delete n;
}

void trie::insert_word(char* s)
{
node *t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
node* n = new node();
n->character = *s;
n->eow = false;
n->prefixes = 1;
for(int i=0;i<26;i++)
{
n->edge[i] = NULL;
}
t->edge[c] = n;
t = n;
}
else
{
t = t->edge[c];
t->prefixes++;
}
*s++;
}
t->eow = true;
}

bool trie::search_word(char* s)
{
node *t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
return false;
}
else
{
t = t->edge[c];
}
*s++;
}
if(t->eow == true)
return true;
else
return false;
}

void trie::delete_word(char* s)
{
node* t = root;
while(*s != '\0')
{
int c = toupper(*s) - 'A';
if(t->edge[c] == NULL)
{
return;
}
else if(t->edge[c]->prefixes == 1)
{
truncate_node(t->edge[c]);
t->edge[c] = NULL;
return;
}
else
{
t = t->edge[c];
}
*s++;
}
}

void trie::display()
{
preorder_display(root);
}

void trie::preorder_display(node* t)
{
if(t == NULL)
return;

cout << "iterating :: " << t->character << " :: " << t->eow << " :: " << t->prefixes << endl;

for(int i=0;i<26;i++)
{
if(t->edge[i] != NULL)
preorder_display(t->edge[i]);
}
}



int main()
{
trie mytrie;
char *s[] = {"tree","trie","algo","assoc","all","also","ass"};
for(int i=0;i {
mytrie.insert_word(s[i]);
}

mytrie.display();

if(mytrie.search_word("all") == true) cout << "all exist" << endl;
else cout << "all do not exist" << endl;

mytrie.delete_word("all");

if(mytrie.search_word("all") == true) cout << "all exist" << endl;
else cout << "all do not exist" << endl;

mytrie.display();
}

Find the last person seated around in a circle program/puzzle

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

package brainteasers;

public class FindWinner {
public static void main(String[] args) {
FindWinner finder = new FindWinner();
char winner = finder.findWinner(10,3);
System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
}

private char findWinner(int n, int m){
char[] people = getPeople(n);
boolean[] eliminated = new boolean[n];
//always start from 1st person
int remainingGuys = n;
int current = 0;

while(remainingGuys>1){
int inkiPinki=0;

while( eliminated[current] || ++inkiPinki != m )
current = (current+1) % n;

eliminated[current] = true;
printStatus( eliminated, people );
remainingGuys--;

while(eliminated[(current+1)%n]){
current++;
}

current = (current+1)%n;
}

System.out.println();
return people[current];
}

private void printStatus(boolean[] eliminated, char[] people) {
System.out.println();
for(int i=0;i char output;
if(eliminated[i]){
output = people[i];
}else{
output = (char)(people[i] - 32);
}
System.out.print(output+" ");
}
}

private char[] getPeople(int n) {
char[] people = new char[n];
System.out.println("Participants are...");
for(int i=0;i people[i] = (char)(i+97);
System.out.print((char)(people[i]-32)+" ");
}
System.out.println();
return people;
}
}
/*
Participants are...
A B C D E F G H I J

A B c D E F G H I J
A B c D E f G H I J
A B c D E f G H i J
A b c D E f G H i J
A b c D E f g H i J
a b c D E f g H i J
a b c D E f g h i J
a b c D e f g h i J
a b c D e f g h i j

And the winner is D!!
*/

Find the last person seated around in a circle program/puzzle

“n” people are seated around in a circle. At each step, the “m”th person is eliminated from the circle. The next iteration continues from the person next to the eliminated person. In the end, there will be only one person remaining. Given “n” and “m”, write a program to find out the person who will be remaining at the end.
int FindWinner(int n, int m)

package brainteasers;

public class FindWinner {
public static void main(String[] args) {
FindWinner finder = new FindWinner();
char winner = finder.findWinner(10,3);
System.out.println("\nAnd the winner is "+(char)(winner-32)+"!!");
}

private char findWinner(int n, int m){
char[] people = getPeople(n);
boolean[] eliminated = new boolean[n];
//always start from 1st person
int remainingGuys = n;
int current = 0;

while(remainingGuys>1){
int inkiPinki=0;

while( eliminated[current] || ++inkiPinki != m )
current = (current+1) % n;

eliminated[current] = true;
printStatus( eliminated, people );
remainingGuys--;

while(eliminated[(current+1)%n]){
current++;
}

current = (current+1)%n;
}

System.out.println();
return people[current];
}

private void printStatus(boolean[] eliminated, char[] people) {
System.out.println();
for(int i=0;i char output;
if(eliminated[i]){
output = people[i];
}else{
output = (char)(people[i] - 32);
}
System.out.print(output+" ");
}
}

private char[] getPeople(int n) {
char[] people = new char[n];
System.out.println("Participants are...");
for(int i=0;i people[i] = (char)(i+97);
System.out.print((char)(people[i]-32)+" ");
}
System.out.println();
return people;
}
}
/*
Participants are...
A B C D E F G H I J

A B c D E F G H I J
A B c D E f G H I J
A B c D E f G H i J
A b c D E f G H i J
A b c D E f g H i J
a b c D E f g H i J
a b c D E f g h i J
a b c D e f g h i J
a b c D e f g h i j

And the winner is D!!
*/

Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X.

This problem is quite largely discussed and is very famous for its various ways to attack. This can be constrained in time and in space. The most primitive way of attacking this problem would yield an solution that runs in O(n2) time.
Let me define the problem clearly. Given an array of size n and a number X, you are supposed to find a pair of numbers that sums to X. Only one pair would be enough.
Lets see how we can find the solution for this in O(n) using a HashSet. Yes, HashSet is a costly data structure to use, but lets consider this primitive just due to the linear order it provides.


import java.util.HashSet;
import java.util.Set;

public class FindSumHashSet {
public static void main(String a[]){
FindSumHashSet sumFinder = new FindSumHashSet();
sumFinder.begin();
}

public void begin(){
int[] sampleArray = getRandomArray(20);
int randomSum = sampleArray[15] + sampleArray[10];
System.out.print("ARRAY : ");
for(int i:sampleArray){
System.out.print(i+" ");
}
System.out.println();
findPair(sampleArray,randomSum);
}

public void findPair(int[] sampleArray, int randomSum) {
Set sampleArraySet = new HashSet();
for(int i=0;i sampleArraySet.add(sampleArray[i]);
int valueToFind = randomSum - sampleArray[i];
if(sampleArraySet.contains(valueToFind)){
System.out.println("SUM : "+randomSum);
System.out.println("PAIR : "+valueToFind+","+sampleArray[i]);
break;
}
}
}

private int[] getRandomArray(int size) {
int[] randomArray = new int[size];
for(int i=0;i randomArray[i] = (int)(Math.random()*10);
}
return randomArray;
}
}
//SAMPLE OUTPUTS

//ARRAY : 7 3 6 4 3 4 7 7 5 1 4 6 2 4 1 7 5 8 9 7
//SUM : 11
//PAIR : 7,4

//ARRAY : 0 2 9 6 0 7 6 5 1 7 9 0 7 1 2 4 4 3 9 0
//SUM : 13
//PAIR : 6,7

Given a string, we should be able to print all the possible palindromes. Let me quickly give a brief example. For the following text : abccbab etc

package dsa.stringmanipulation;

/**
* Program to print all palindromes in a string
* @author Bragaadeesh
*/
public class FindAllPalindromes {
public static void main(String[] args){
FindAllPalindromes finder = new FindAllPalindromes();
finder.printAllPalindromes("abcddcbaABCDEDCBA");
}

public void printAllPalindromes(String inputText){
if(inputText==null){
System.out.println("Input cannot be null!");
return;
}
if(inputText.length()<=2){
System.out.println("Minimum three characters should be present");
}
//ODD Occuring Palindromes
int len = inputText.length();
for(int i=1;i for(int j=i-1,k=i+1;j>=0&&k if(inputText.charAt(j) == inputText.charAt(k)){
System.out.println(inputText.subSequence(j,k+1));
}else{
break;
}
}
}
//EVEN Occuring Palindromes
for(int i=1;i for(int j=i,k=i+1;j>=0&&k if(inputText.charAt(j) == inputText.charAt(k)){
System.out.println(inputText.subSequence(j,k+1));
}else{
break;
}
}
}

}
}
/*
Sample Output:
DED
CDEDC
BCDEDCB
ABCDEDCBA
dd
cddc
bcddcb
abcddcba
*/

WAP to Sort Stack In Ascending Order "InPlace"

Sorting can be performed with one more stack. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the new item. Since the items we removed are on the original stack, we’re back where we started. The algorithm is O(N^2) and appears below.

public static Stack sort(Stack s) \
{
Stack r = new Stack();
while(!s.isEmpty())
{
int tmp = s.pop();
while(!r.isEmpty() && r.peek() > tmp)
{
s.push(r.pop());
}
r.push(tmp);
}
return r;
}

WAP to Calculate Square Root of Number Efficiently

It Seems to easy but people don't take care of algo & precision so why most of them don't able to implement these method & its asked in mostly core companies interviews

This Method is Known as Square root approximation - Babylonian method

Explanation
The basic idea is that if x is an overestimate to the square root of a non-negative real number S then S/x, will be an underestimate and so the average of these two numbers may reasonably be expected to provide a better approximation

It proceeds as follows:

1. Begin with an arbitrary positive starting value x0 (the closer to the root, the better).
2. Let xn+1 be the average of xn and S / xn (using the arithmetic mean to approximate the geometric mean).
3. Repeat step 2 until the desired accuracy is achieved.



#include

#include

double sqroot(const double s)
{

double xn = s / 2.0;
double lastX = 0.0;

// Looping this way ensures we perform only as many calculations as necessary.
// Can be replaced with a static for loop if you really want to.
while(xn != lastX) {
lastX = xn;
xn = (xn + s/xn) / 2.0;
}

return xn;

}
int main()
{
printf( " %f ",sqroot(7));
}

Complexity is O(log2(n)) but if the closest 2^k number is found in constant time then complexity is O(log2log2(n))
TC O(logn)
SC O(1)
Run here http://codepad.org/jmmBxoZ4


2nd Method & Well Know Mostly Used Newton Rapson method

The Newton-Raphson method in one variable:

Given a function ƒ(x) and its derivative ƒ '(x), we begin with a first guess x0 for a root of the function. Provided the function is reasonably well-behaved a better approximation x1 is

x(n+1)=x0-f(x0,num)/f'(x0)

#include

#include

float f(float x,int n)
{
return(x*x-n);
}

float df(float x)
{
return 2*x;
}

int main()
{
float x0=3,x1,e=0.0001,num=7;
int i;

printf("\n Newton Raphson's Method : To find Square Root");

x1=(x0)-((f(x0,num))/df(x0));
printf(" %f ", x1);
i=1;
while(fabs(f(x1,num))>e)
{
x0=x1;
x1=(x0)-((f(x0,num))/df(x0));

printf("\n prev root=%f Square root of %f is %.2f",x0,num,x1);

}
}

Source http://en.citizendium.org/wiki/Newton's_method#Computational_complexity

Using Newton's method as described above, the time complexity of calculating a root of a function f(x) with n-digit precision, provided that a good initial approximation is known, is O((\log n) F(n)) where F(n) is the cost of calculating f(x)/f'(x)\, with n-digit precision.

However, depending on your precision requirements, you can do better:

If f(x) can be evaluated with variable precision, the algorithm can be improved. Because of the "self-correcting" nature of Newton's method, meaning that it is unaffected by small perturbations once it has reached the stage of quadratic convergence, it is only necessary to use m-digit precision at a step where the approximation has m-digit accuracy. Hence, the first iteration can be performed with a precision twice as high as the accuracy of x_0, the second iteration with a precision four times as high, and so on. If the precision levels are chosen suitably, only the final iteration requires f(x)/f'(x)\, to be evaluated at full n-digit precision. Provided that F(n) grows superlinearly, which is the case in practice, the cost of finding a root is therefore only O(F(n)), with a constant factor close to unit

TC O(logn)
SC O(1)
Run Here hhttp://codepad.org/mIrXDehk


Too Prove why ist log(n) you can try this simple example based on binary search 

import java.util.*;
public class SQRT
{
public static void main(String args[])
{
float n=7;
float y=sqrt(n);
System.out.println("sqrt is "+y);
}
static float sqrt(float n)
{
float low=0,high=n;
float mid=(low+high)/2;
while(Math.abs(mid*mid-n)>0.0000001)
{

if(mid*mid<n)
low=mid;
else if(mid*mid>n)
high=mid;
mid=(low+high)/2;

}

How to find a number of 10 digits (non repeated digits) which is a perfect square? perfect square examples: 9 (3x3) 16 (4x4) 25(5x)

class perfectSquare
{

/**
* @param args
*/

public static int check(long num)
{
int[] A={0,0,0,0,0,0,0,0,0,0};
int i;

while ( num != 0)
{
i=(int) (num%10);
if (A[i]==0)
{
A[i]=1;
num=num/10;

}
else
return 0;

}
return 1;
}


public static void main(String[] args) {
// TODO Auto-generated method stub

long b=(long) Math.sqrt(1023456789);
long bn= 9876543210L;
long e=(long) Math.sqrt(bn);
int count=0;

for (long j=b;j<=e;j++)
if(check((long)(j*j))!=0)
{
count++;
System.out.println((j*j));
}

System.out.println("count::"+count);


}

}


compilation info

input / output show all hide all
# 1

* upload with new input

You have reached a limit of free submissions this month.
You cannot send submissions this month anymore because of exceeding your monthly limit. Please recharge your account.
*
# 1: hide show edit 2 days 15 hours ago

result: Success time: 0.09s memory: 213440 kB returned value: 0
input: no
output:

1026753849
1042385796
1098524736
1237069584
1248703569
1278563049
1285437609
1382054976
1436789025
1503267984
1532487609
1547320896
1643897025
1827049536
1927385604
1937408256
2076351489
2081549376
2170348569
2386517904
2431870596
2435718609
2571098436
2913408576
3015986724
3074258916
3082914576
3089247561
3094251876
3195867024
3285697041
3412078569
3416987025
3428570916
3528716409
3719048256
3791480625
3827401956
3928657041
3964087521
3975428601
3985270641
4307821956
4308215769
4369871025
4392508176
4580176329
4728350169
4730825961
4832057169
5102673489
5273809641
5739426081
5783146209
5803697124
5982403716
6095237184
6154873209
6457890321
6471398025
6597013284
6714983025
7042398561
7165283904
7285134609
7351862049
7362154809
7408561329
7680594321
7854036129
7935068241
7946831025
7984316025
8014367529
8125940736
8127563409
8135679204
8326197504
8391476025
8503421796
8967143025
9054283716
9351276804
9560732841
9614783025
9761835204
9814072356
count::87

Prime Number Generation Using Sieve of Eratosthenes

public class prime_sieve
{


public static void main(String a[])
{

runEratosthenesSieve(100);

}

public static void runEratosthenesSieve(int upperBound) {

int upperBoundSquareRoot = (int) Math.sqrt(upperBound);

boolean[] isComposite = new boolean[upperBound + 1];

for (int m = 2; m <= upperBoundSquareRoot; m++) {

if (!isComposite[m]) {

System.out.print(m + " ");

for (int k = m * m; k <= upperBound; k += m)

isComposite[k] = true;

}

}

for (int m = upperBoundSquareRoot; m <= upperBound; m++)

if (!isComposite[m])

System.out.print(m + " ");

}


}

AP to implement Horner Rule

#include

double horner(double *coeffs, int s, double x)
{
int i;
double res = 0.0;

for(i=s-1; i >= 0; i--)
{
res = res * x + coeffs[i];
}
return res;
}


int main()
{
double coeffs[] = { -19.0, 7.0, -4.0, 6.0 };

printf("%5.1f\n", horner(coeffs, sizeof(coeffs)/sizeof(double), 3.0));
return 0;
}
W