Trie Data Structure( or Prefix tree) Java Implementation

Trie Java Implementation

Also know as Prefix Tree.
Below is the  basic Java implementation of Trie Data Structure.We can search the the word in Trie in O(n) complexity.

Below is the implementation of Trie in Java:

import java.util.HashMap;


class Test {

TrieNode root;

    static class TrieNode{
        HashMap<Character, TrieNode> map;
        boolean isWord;
     
        TrieNode(){
        map = new HashMap<Character, TrieNode>();
        }
     
    }
 
 
    /** Initialize your data structure here. */
    public Test() {
    root = new TrieNode();
    }
 
    /** Inserts a word into the trie. */
    public void insert(String word) {
        TrieNode currentNode = root;
        int i=0;
        for(char ch:word.toCharArray()){
        i++;
            if(!currentNode.map.containsKey(ch)){
                currentNode.map.put(ch, new TrieNode());
            }
            currentNode = currentNode.map.get(ch);
            if(i==word.length()) {
            currentNode.isWord = true;
            }
        }
    }
 
    /** Returns if the word is in the trie. */
    public boolean search(String word) {
    TrieNode currentNode = root;
        for(char ch:word.toCharArray()){
            if(!currentNode.map.containsKey(ch)){
                return false;
            }
            currentNode = currentNode.map.get(ch);
        }
        return currentNode.isWord;
    }
 
    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
    TrieNode currentNode = root;
        for(char ch:prefix.toCharArray()){
            if(!currentNode.map.containsKey(ch)){
                return false;
            }
            currentNode = currentNode.map.get(ch);
        }
        return true;
    }
 
    public static void main(String...ar) {
    Test ob = new Test();
    ob.insert("Hello");
    ob.insert("HelGo");
    System.out.println(ob.startsWith("H"));
    System.out.println(ob.search("Hello"));
    System.out.println(ob.startsWith("Hel"));
    System.out.println(ob.search("GG"));
    }
}

Saving File in javascript without making Server call in muiltiple Browsers(IE,Edge,Chrome,Firefox,Opera and Safari)

Saving File in javascript without making Server call

We can make a file and download to user machine without making a server call in javascript. The trick is to make a anchor tag and write a data in a url which is passed to href.But, this trick doesn't work for Internet Explorer and Edge. We can do that in IE and Edge also with the help of making a blob object and with msSaveOrOpenBlob method.

Following is the code which can be used to do the same:

var data="Hello,This is javascript";
var fileName="download.txt";
if (window.navigator && window.navigator.msSaveOrOpenBlob) {
      var blob = new Blob([data], { type: 'text/csv' });
    var done=window.navigator.msSaveOrOpenBlob(blob, fileName);
    }else{
    var element =document.createElement('a');
    element.setAttribute('href', 'data:text/plain;charset=utf-8,' + encodeURIComponent(data));
    element.setAttribute('download', fileName);
 
    element.style.display = 'none';
    document.body.appendChild(element);
 
    element.click();
 
    document.body.removeChild(element);
      }


We can use the same code for downloading the png, csv and other types of files.

There are other methods also but check that it will work on all browser or not.

Spoj TRVCOST - Travelling cost

Spoj TRVCOST - Travelling cost

Problem Statement:-http://www.spoj.com/problems/TRVCOST/

Simple Dijkstra implementation.Be sure to make 500 cells(Vertex) because in inputs only edges i.e. roads are given.

Java Solution for this problem is given below.

Java Solution:-https://github.com/suyashbhalla/old_practice/blob/master/spoj/TRVCOST.java

Spoj MICEMAZE - Mice and Maze Java Solution

Spoj MICEMAZE - Mice and Maze Java Solution

Problem Statement:-http://www.spoj.com/problems/MICEMAZE/

Hint: - Problem can be solved by Dijkstra Algorithm. Reverse the given edges and use the given end cell as source cell(starting cell) and then count the cells that can be reached within given time limit.Java Solution using Dijkstra algorithm link is given below.

Java Solution: -https://github.com/suyashbhalla/old_practice/blob/master/spoj/MICEMAZE.java

Quick Sort Java Implementation

Quick Sort Java Implementation

Quick Sort is a sorting technique to sort the group of elements. It uses the divide and conquer technique to sort the elements.It is pretty much similar to Merge sort.The only difference is that why we divide the array into half always(as in Merge Sort).I prefer you to read the post about Merge Sort if you are not familiar with that technique.

Merge Sort

The highlighted idea in Quick Sort is we will select one Pivot element from the list and re-arrange the array as to get correct position of that element.Thus, we will just arrange the array as like we have smaller elements than Pivot element to the left and the larger elements to the right of the Pivot element.Then we partition the array in such way that we will not include previous Pivot element(as it's reached to its desired location)  and then recursively repeat the process.

The time complexity of Quick sort is O(n^2).

Example:-

We chose Pivot element as the last element.

9  7  5  11  12  2  14  3  10  6

6 is pivot element

5  2  3      6      12  7  14  9  10  11

Now we will perform the same steps for left and right array.

For more detail about Quick sort.Click here https://en.wikipedia.org/wiki/Quicksort

Java Implementation:-

https://github.com/suyashbhalla/other/blob/master/QuickSort.java

Spoj COURAGE - Living with Courage Java Solution

Spoj COURAGE - Living with Courage Java Solution using Segment Tree

Problem Statement:-http://www.spoj.com/problems/COURAGE/

We can easily solve the problem by using the Segment Trees.A very nicely explained and detailed on Segment Tree tutorial link is given below:-

Click on the GITHUB link to see the solution.

Solution:-https://github.com/suyashbhalla/old_practice/blob/master/spoj/COURAGE.java

Spoj CUBNUM - Cube Numbers Java Solution

Spoj CUBNUM - Cube Numbers [Java Solution] using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/CUBNUM/

Easy Problem can be solved by Dynamic Programming.It's an advice to try it yourself first.

Click on the Github link to see the solution.

Solution:-https://github.com/suyashbhalla/old_practice/blob/master/spoj/CUBNUM.java

Spoj Problem ABCDEF-ABCDEF[C++ Solution]

 Spoj Problem ABCDEF-ABCDEF[C++ Solution]

Problem Statement:-http://www.spoj.com/problems/ABCDEF/

Hint:-


We can write it as-
                              a*b+c-de=df            (Multiply each term on both sides with d)
                              a*b+c=de+df
                              a*b+c=d(e+f)

Now we calculate every possible set value with given input on LHS(a*b+c) and on RHS(d(e+f)) in O(n^3) as there are three variables on each side and save the in array(as in solution L and R).Array size is approximately equal to N*N*N.In RHS d cannot be equal to 0.We calucate the answer by comparing L and R whenever they are equal.We count the frequency of values in a separate array(as in below soltion cntL and cntR),whenever LHS calculated value and RHS calculated value are equal we add the all possible sets by multiplying their frequencies.


Note:- Keep in mind d cannot equal to 0.
            qsort of stdlib gives TLE.

Program:-

#include<stdio.h>
#include<algorithm>

using namespace std;

int L[1000000],R[1000000],cntL[1000000],cntR[1000000];

int main(){

int N,i,j,k;
scanf("%d",&N);

int ar[N];

for(i=0;i<N;i++){
scanf("%d",&ar[i]);
}



int sizeL=0,sizeR=0;
for(i=0;i<N;i++){
for(j=0;j<N;j++){
for(k=0;k<N;k++){
L[sizeL++]=(ar[i]*ar[j])+ar[k];
}
}
}


for(i=0;i<N;i++){
if(ar[i]==0){
continue;
}
for(j=0;j<N;j++){
for(k=0;k<N;k++){
R[sizeR++]=ar[i]*(ar[j]+ar[k]);
}
}
}

sort(L,L+sizeL);
sort(R,R+sizeR);

int t=1;
cntL[0]=1;cntR[0]=1;
for(i=1;i<sizeL;i++){
if(L[i]!=L[t-1]){
L[t]=L[i];
cntL[t]=1;
++t;
}else{
++cntL[t-1];
}
}

int t1=1;
for(i=1;i<sizeR;i++){
if(R[i]!=R[t1-1]){
R[t1]=R[i];
cntR[t1]=1;
++t1;
}else{
++cntR[t1-1];
}
}
long long ans=0;


for(i=0,j=0;i<t&&j<t1;){
if(R[j]==L[i]){
ans+=(long long)cntL[i]*cntR[j];
}
if(L[i]<R[j]){
i++;
}else if(L[i]>R[j]){
j++;
}else{
i++;
j++;
}

}

printf("%lld\n",ans);

return 0;
} 

Input:-

2
-1
1

Output:-

4

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem AIBOHP-Aibohphobia[Java Solutio] using Dynamic Programming

   Spoj Problem AIBOHP-Aibohphobia[Java Solution] using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/AIBOHP/

Hint:- Find length of LONGEST COMMON SUBSEQUENCE in orignal string and reverse of string and subtract it from length of orignal string.

Longest Common Subsequence Problem easily solved using Dynamic Programming.

Required Value=length of string - LCS(string,reverse of string)

A nice detailed tutorial to find Longest Common Sub-Sequence is

Java Program:-

 /**
 * @(#)AIBOHP.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/11
 */
import java.io.*;
import java.util.*;

class AIBOHP {

    public static void main(String args[])throws IOException{
   
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    long T=Long.parseLong(br.readLine());
   
    while(T--!=0){
    
    StringBuilder str=new StringBuilder(br.readLine());
    String ostr=str.toString();
    System.out.println(ostr.length()-LCS(ostr,str.reverse().toString()));
   
    }
   
    }
    
    public static int LCS(String x,String y){
   
    int dp[][]=new int[x.length()+1][y.length()+1];
   
    for(int i=0;i<=x.length();i++){
    for(int j=0;j<=y.length();j++){
    if(i==0||j==0){
    dp[i][j]=0;
    continue;
    }
   
    if(x.charAt(i-1)==y.charAt(j-1)){
    dp[i][j]=dp[i-1][j-1]+1;
    }else{
    dp[i][j]=Math.max(dp[i][j-1],dp[i-1][j]);
    }
   
    }
    }
    return dp[x.length()][y.length()];
    }
      
}

Input:-

1
fft

Output:-

1

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem MIXTURES - Mixtures[Java Solution] using Dynamic Programming

     Spoj Problem MIXTURES - Mixtures[Java Solution]                                           using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/MIXTURES/

Hint:- Matrix Chain Multiplication Algorithm.

Helpful Tutorial for Matrix Chain Multiplication Problem using Dynamic Programming:-

With the help of algorithm of  Matrix Chain Multiplication,this problem can be solved similarly except we have to also store new generated color.Keep in mind that we have to minimize the generated smoke.It is an advice to try yourself to solve the problem after studying the concept of Matrix Chain Multiplication using Dynamic Programming.Here,a solution for this problem written in java is given below:-

Java Program:-

/**
 * @(#)MIXTURES.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/4/14
 */

import java.io.*;

class MIXTURES {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    String in;
   
    while((in=br.readLine())!=null){
   
    int N=Integer.parseInt(in);
    String str[]=br.readLine().split(" ");
    int ar[]=new int[N];
   
    for(int i=0;i<N;i++){
    ar[i]=Integer.parseInt(str[i]);
    }
   
    System.out.println(MCM(ar));
   
    }
   
    }
 
    static int MCM(int ar[]){
   
    if(ar.length==2){
    return ar[0]*ar[1];
    }
   
    int dp[][]=new int[ar.length][ar.length];
    int color[][]=new int[ar.length][ar.length];
   
    for(int i=0;i<ar.length;i++){
    color[i][i]=ar[i];
    }
   
    int mul=0;
   
    for(int l=2;l<=ar.length;l++){
   
    for(int i=0;i<=ar.length-l;i++){
   
    int j=i+l-1;
    dp[i][j]=Integer.MAX_VALUE;
    for(int k=i;k<j;k++){
    mul=dp[i][k]+dp[k+1][j]+(color[i][k]*color[k+1][j]);
    if(mul<dp[i][j]){
    dp[i][j]=mul;
    color[i][j]=(color[i][k]+color[k+1][j])%100;
    }
    }
   
    }
   
    }
    return dp[0][ar.length-1];
   
    }
 
 
}

Input:-

2
18 19
3
40 60 20

Output:-

342
2400

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem EDIST - Edit Distance[Java Solution]

   Spoj Problem EDIST - Edit Distance[Java Solution]                                           

Problem Statement:-http://www.spoj.com/problems/EDIST/

Hint:- Dynamic Programming.

Java Program:-

/**
 * @(#)EDIST.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2015/11/2
 */

import java.io.*;


class EDIST {

    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
   
    int T=Integer.parseInt(br.readLine());
   
    while(T--!=0){
   
    String str1=br.readLine();
    String str2=br.readLine();
   
    System.out.println(solve(str1,str2));
   
    }
   
    }  
 
    public static int solve(String s1,String s2){
    int ar[][]=new int[s1.length()+1][s2.length()+1];
    for(int i=0;i<=s1.length();i++){
    ar[i][0]=i;
    }
   
    for(int i=0;i<=s2.length();i++){
    ar[0][i]=i;
    }
   
    for(int i=1;i<=s1.length();i++){
    for(int j=1;j<=s2.length();j++){
    if(s1.charAt(i-1)==s2.charAt(j-1)){
    ar[i][j]=ar[i-1][j-1];
    }else{
    ar[i][j]=Math.min(ar[i-1][j-1],Math.min(ar[i-1][j],ar[i][j-1]))+1;
    }
    }
    }
   
    return ar[s1.length()][s2.length()];
   
    }
   
}

Input:-

1
FOOD
MONEY 

Output:-

4

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj-PIGBANK Piggy Bank Problem[Java Solution]

   Spoj Problem PIGBANK- PIGGY-BANK[Java Solution]                                          using Dynamic Programming

Problem Statement:-http://www.spoj.com/problems/PIGBANK/

With the help of Dynamic Programming concept,this problem can be easily solved.Solution of this problem using Java given below.

Java Program:-

/**
 * @(#)PIGBANK.java
 *
 *
 * @author Suyash Bhalla
 * @version 1.00 2016/3/21
 */

import java.io.*;
import java.util.*;

class PIGBANK {

public static final int INF=1000000000;


    public static void main(String args[])throws IOException{
   
    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    int T=Integer.parseInt(br.readLine());
    while(T--!=0){
    String str[]=br.readLine().split(" ");
    int E=Integer.parseInt(str[0]);
    int F=Integer.parseInt(str[1]);
   
    int N=Integer.parseInt(br.readLine());
   
    int val[]=new int[N];
    int wt[]=new int[N];
   
    int W=(F-E)+1;
    int ar[]=new int[W];
   
    for(int i=0;i<N;i++){
    str=br.readLine().split(" ");
    val[i]=Integer.parseInt(str[0]);
    wt[i]=Integer.parseInt(str[1]);
    Arrays.fill(ar,INF);
   
    }
    ar[0]=0;
   
    for(int i=1;i<=N;i++){
    for(int j=wt[i-1];j<W;j++){
    if(ar[j]>ar[j-wt[i-1]]+val[i-1]){
    ar[j]=ar[j-wt[i-1]]+val[i-1];
    }
    }
    }
   
   
    if(ar[W-1]==INF){
    System.out.println("This is impossible.");
    }else{
    System.out.println("The minimum amount of money in the piggy-bank is "+ar[W-1]+".");
    }
   
   
   
   
   
    }
   
    }
 
 
 
}

Input:-

3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4

Output:-

The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------

Spoj Problem GSS1 - Can you answer these Queries I using Segment Trees

Problem Statement:-http://www.spoj.com/problems/GSS1/

Hint:-Use Segment Tree.

Using the Segment trees,this problem can be solved within the given time limit.we have to maintain four values for prefix,suffix,prefix + suffix, and  maximum of these three

C Program:-

#include<stdio.h>

struct Node{

int sum;

int prefix;

int suffix;

int max;

void init(int value){

sum=value;

prefix=value;

suffix=value;

max=value;

}

void merge(Node l,Node r){

if(l.sum==-99999&&l.prefix==-99999&&l.suffix==-99999&&l.max==-99999){

sum=r.sum;

prefix=r.prefix;

suffix=r.suffix;

max=r.max;

return;

}

if(r.sum==-99999&&r.prefix==-99999&&r.suffix==-99999&&r.max==-99999){

sum=l.sum;

prefix=l.prefix;

suffix=l.suffix;

max=l.max;

return;

}

sum=l.sum+r.sum;

prefix=maxInt(l.prefix,l.sum+r.prefix);

suffix=maxInt(r.suffix,r.sum+l.suffix);

max=maxInt(l.suffix+r.prefix,maxInt(l.max,r.max));

}

int maxInt(int x,int y){

        return x>y?x:y;

        }

};

int getSize(int N){

int s=1;

while(s<N){

s<<=1;

}

s<<=1;

return s-1;

}

void createSegArray(Node segAr[],int ar[],int low,int high,int pos){

if(low==high){

segAr[pos].init(ar[low]);

return;

}

int mid=(low+high)/2;

createSegArray(segAr,ar,low,mid,2*pos+1);

createSegArray(segAr,ar,mid+1,high,2*pos+2);

segAr[pos].merge(segAr[2*pos+1],segAr[2*pos+2]);

}

Node temp={-99999,-99999,-99999,-99999};

Node result={0,0,0,0};

Node executeQuery(Node segAr[],int qL,int qR,int low,int high,int pos){

if(qL<=low&&qR>=high){

return segAr[pos];

}

if(qL>high||qR<low){

return temp;

}

int mid=(low+high)/2;

Node l,r;

l=executeQuery(segAr,qL,qR,low,mid,2*pos+1);

r=executeQuery(segAr,qL,qR,mid+1,high,2*pos+2);

result.merge(l,r);

return result;

}

int main(){

int N;

scanf("%d",&N);

int ar[N];

for(int i=0;i<N;i++){

scanf("%d",&ar[i]);

}

Node segAr[getSize(N)];

createSegArray(segAr,ar,0,N-1,0);

int nQ,L,R;

scanf("%d",&nQ);

while(nQ--!=0){

scanf("%d %d",&L,&R);

printf("%d\n",executeQuery(segAr,L-1,R-1,0,N-1,0).max);

}

return 0;

}

Input:-

3
-1 2 3
1
1 2

Output:-

2

--------------X--------------X--------------X--------------X--------------X--------------X--------------X---------