Java implementation of Producer - Consumer Problem using Blocking Queue

             Producer creates data and make it into a buffer. A consumer who always take the data from the buffer.

Let us consider a textile manufacturer. He/she is the producer. Customer is the consumer.

Problem:

When the producer creates more products or no products.

When a consumer doesn’t take the product.

So the solution is implemented in java as Blocking Queue.

This queue provides the solution for this problem.

It is available in java.util.concurrent package.

Let us create the code.

Java implementation:

// Import the built in package

import java.util.concurrent.*;

//class producer declaration and function ‘run()’ defintion

class PCP_Producer implements Runnable {

    private BlockingQueue<Integer> queue1;

    public PCP_Producer(BlockingQueue<Integer> q) {

        this.queue1 = q;

    }

    @Override

    public void run() {

        int i = 0;

        try {

            while (true) {

                System.out.println("The Produced data is  " + i);

                queue1.put(i++);

                Thread.sleep(500); // let us make some time to simulate production

            }

        } catch (InterruptedException e) {

            Thread.currentThread().interrupt();

        }

    }

}

//Class Consumer declaration and method ‘run()’ definition.

class PCP_Consumer implements Runnable {

    private BlockingQueue<Integer> queue1;

    public PCP_Consumer(BlockingQueue<Integer> q) {

        this.queue1 = q;

    }

    @Override

    public void run() {

        try {

            while (true) {

                Integer item = queue1.take();

                System.out.println("The Consumed data is: " + item);

                Thread.sleep(1000); // make the time to Simulate the consumption

            }

        } catch (InterruptedException e) {

            Thread.currentThread().interrupt();

        }

    }

}

//main class. Object creation and function call.

public class PCP_Example {

    public static void main(String[] args) {

        BlockingQueue<Integer> queue1 = new ArrayBlockingQueue<>(5);

        Thread pcp_producer = new Thread(new PCP_Producer(queue1));

        Thread pcp_consumer = new Thread(new PCP_Consumer(queue1));

        pcp_producer.start();

        pcp_consumer.start();

    }

}

Output:

Compile and run the program to get the output.

C:\raji\blog>javac PCP_Example.java

C:\raji\blog>java PCP_Example

Produced: 1

Consumed: 1

Produced: 2

Consumed: 2

Produced: 3

Produced: 4

Consumed: 3

Produced: 5

Consumed: 4

Consumed: 5

Here, the sample implementation of Producer consumer Problem using Blocking Queue is done. Hope, this code will help you. Keep Coding!!!

Data Structures -An Introduction with Basic Examples

 Let’s consider a social media application. You create an account with your basic details and receive many follow requests, which you accept. Your follower’s list is then organized like a data structure.

Data structures are used to store and manage data in an organized and efficient way.

Everyday Examples: Think of a bookshelf, a wardrobe, or a parking area in a mall—each one organizes different types of items systematically.

Definition:

A data structure is a way of organizing, processing, and retrieving data effectively.

How are data structures classified?

They are broadly categorized into two types:


1. Linear Data Structures

Here, data is stored sequentially and accessed one by one.

  • Array: A basic linear data structure where elements are stored in contiguous memory locations.
  • Linked List: Composed of nodes that are connected using pointers or links.
  • Stack: Follows the Last-In, First-Out (LIFO) principle.
  • Queue: Follows the First-In, First-Out (FIFO) principle—like people standing in a queue.

2. Non-linear Data Structures

The data isn’t stored sequentially; instead, it forms hierarchical or interconnected structures.

  • Tree: Has a root node and child nodes, representing a parent-child relationship.
  • Graph: Consists of nodes (vertices) connected by edges, useful for modeling networks.

Why are data structures important?

They are the backbone of data organization. Proper use of data structures ensures that data can be stored, accessed, and manipulated efficiently.


Real-life Examples of Data Structures:

  • Bank transactions: Utilize stacks and queues to manage operations.
  • Travel apps: Rely on graph structures for route optimization.
  • Social media apps: Often use tree structures to represent follower hierarchies.

Hope ,this introduction will help you to understand Data structures.

Java implementation of MVC Pattern

A Design pattern which separates the data logic, UI (User Interface) and processing. Here, data logic deals with Model. UI is for View. The processing can be done by Controller.

This design pattern is useful for Web Application Architecture.

Model-View-Controller (MVC) separates data logic (Model), UI (View), and processing (Controller).

The technical implementation is given below.

Java implementation:

This program implements four classes namely MVC_Model, MVC_View, MVC_Controller and MVCEg.

‘Class MVC_Model’ :

  • It creates and holds the data.
  • Member function :get_Data()
  • Member variable : m_data.

‘Class M_View’:

  • It displays the data to user.
  • Member function: displayIt( String msg). where ‘msg’ is a member variable as String.

‘Class M_Controller’:

  • This process the data.
  • It initialises the values to above two classes.
  • Member function: ‘updateItView()’.
  • Here, this function gets the data from MVC_Model and use the MVC_View function displayIt().

‘Class MVCEg’:

  • It creates the objects for all classes and make a function call.

Program:

//Class1 for creating data logic

class MVC_Model {

    private String m_data = "MVC Example Sample text!";

    public String get_Data() {

        return m_data;

    }

}

//class 2 is for UI.

class MVC_View {

    public void displayIt(String msg) {

        System.out.println("Displaying the message: " + msg);

    }

}

//Class 3 is for Processing.

class MVC_Controller {

    private MVC_Model model;

    private MVC_View view;

    public MVC_Controller(MVC_Model model, MVC_View view) {

        this.model = model;

        this.view = view;

    }

    public void updateItView() {

        view.displayIt(model.get_Data());

    }

}

//Main Class to create objects and function calls

public class MVCEg {

    public static void main(String[] args) {

        MVC_Model model = new MVC_Model();

        MVC_View view = new MVC_View();

        MVC_Controller controller1 = new MVC_Controller(model, view);

        controller1.updateItView();

    }

}

Output:

Compile and run the program to get the output.

C:\raji\blog>javac MVCEg.java

C:\raji\blog>java MVCEg

Displaying the message: MVC Example Sample text!

Usage of this code: It is useful in Spring MVC, React and Angular Web frameworks.

This is way of creating MVC Design pattern in java. Hope, this code will useful to you.Keep Coding!!!

Java implementation of Strategy Pattern

     This design pattern deals with Dynamic Behavior Selection. Without modifying the code, the pattern swaps the behavior at run time.

Technical implementation:

This implementation starts with creating interface.

  • ‘interface’ PaymentMethod is developed with a member function payIt().payIt() has a member variable ‘amount’.
  • Two classes “CCPayment” and “BankPayment” are derived from interface PaymentMethod.
  • “payIt() method displays the amount paid message to the user.
  • PaymentContext is a class for developing this design pattern.
  • A private member variable’ meth’ is created for PaymentMethod interface.
  • ‘setMethod()’ initialises the variable ‘meth’.
  • ‘processIt()’ calls the function ‘payIt()’ with ‘amount’ value.
  • Finally, a sample class with main () function is written.
  • An object is created for PaymentContext.
  • First,setMethod is initialised with CCPayment object.
  • It calls the payIt() functions with amount value.
  • Again,the setMethod is initialised with BankPayment object.
  • It calls the payIt() function with amount value.

Program:

interface PaymentMethod {

    void payIt(int amount);

}

class CCPayment implements PaymentMethod {

    public void payIt(int amount) {

        System.out.println("The amount: "+amount + "is paid via Credit Card.");

    }

}

class BankPayment implements PaymentMethod {

    public void payIt(int amount) {

        System.out.println("The amount: " + amount + " is paid via Bank account.");

    }

}

class PaymentContext {

    private PaymentMethod meth;

    public void setMethod(PaymentMethod meth) {

        this.meth = meth;

    }

    public void processIt(int amount) {

        meth.payIt(amount);

    }

}

public class sample {

    public static void main(String[] args) {

        PaymentContext pm = new PaymentContext();

        pm.setMethod(new CCPayment());

        pm.processIt(5000);

        pm.setMethod(new BankPayment());

        pm.processIt(1500);

    }

}

Output:

Compile and run the program to get the output.

C:\raji\blog>javac sample.java

C:\raji\blog>java sample

The amount: 5000 is paid via Credit Card.

The amount: 1500 is paid via Bank account.

This design pattern is useful in payment gateways. It also useful in developing AI algorithms.

That’s all. The java program to implement the Strategy Design Pattern is done. Hope, this code sample is useful to you. Keep Coding!!!

Adapter Pattern implementation in java

               It is a structural pattern which organizes the classes and objects. Adapter Pattern is one of its types. This pattern makes the different interfaces to run together.

Java implementation:

              It connects the incompatible interfaces to work together. Let us create two interfaces.

  • One is MPlayer (A media player). It has a play () method.
  • Another interface is AMediaPlayer. It also has playMP4() method.
  • A class (MP3Player) is created for MPlayer interface.
  • ‘play()’ method is used to play Mp3 file.
  • In the same way, another class(MP4Player) is created for AMediaPlayer interface.
  • The ‘playMP4()’ definition is written.
  • Adapter class is created with method. It connects both of the interfaces.
  • A public class ‘MPPlay’ is developed with main() class.
  • Objects are newly created for both classes. ‘play()’ and ‘playMP4()’ functions are called to display the result.

Program:

// interface 1

interface MPlayer {

    void play(String fname);

}

//class1 with method1

class MP3Player implements MPlayer {

    public void play(String fname) {

        System.out.println("Playing MP3 file: " + fname);

    }

}

//interface 2

interface AMediaPlayer {

    void playMP4(String fname);

}

//class 2 with method2

class MP4Player implements AMediaPlayer {

    public void playMP4(String fname) {

        System.out.println("Playing MP4 file: " + fname);

    }

}

//Adapter class definition

class MAdapter implements MPlayer {

    private AMediaPlayer aMediaPlayer;

    MAdapter(String format) {

        if (format.equalsIgnoreCase("mp4")) {

            aMediaPlayer = new MP4Player();

        }

    }

    public void play(String fname) {

        aMediaPlayer.playMP4(fname);

    }

}

//main() function

public class MPPlay {

    public static void main(String[] args) {

        MPlayer player1 = new MP3Player();

        player1.play("Manos Mars - The Tunning.mp3");

        MPlayer player2 = new MAdapter("mp4");

        player2.play("j1.mp4");

    }

}

The program is developed.

Output:

Compile and run the program to get the output.

C:\raji\blog>javac MPPlay.java

C:\raji\blog>java MPPlay

Playing MP3 file: Manos Mars - The Tunning.mp3

Playing MP4 file: j1.mp4

This is the java implementation of Adapter pattern. Hope, this code will helpful to you. Keep Coding!!!

Factory Design Pattern in java

              It is a design pattern which creates objects at run time. It makes the user to develop objects. Even, it does not specify the exact class.

Program implementation:

Here, an interface Fruit is created with findColor() member function.

  • Two more classes are created using this interface. One is for Apple class and another one is guava.
  • A new class “FruitBasket” is developed with a member function getFruit().
  • The main class “FruitEg” is written with main() function.
  • ‘findColor()’ – This function displays the colour of the fruit.
  • ‘getFruit()’ – it gets the type of fruit. Using a if loop, check for fruit type and create the new object.
  • ‘main()’ – this function creates the object for fruit class and call the findColor().

Program:

interface Shape {

    void findCorners();

}

 class Square implements Shape {

    public void findCorners() {

        System.out.println("Square has four Corners");

    }

}

 class Triangle implements Shape {

    public void findCorners() {

        System.out.println("Triangle has three Corners");

    }

}

 class Shapes {

    public static Shape getShape(String type) {

        if (type.equalsIgnoreCase("Square")) return new Square();

        else if (type.equalsIgnoreCase("Triangle")) return new Triangle();

        return null;

    }

}

 public class ShapesEg {

    public static void main(String[] args) {

        Shape myshape = Shapes.getShape("Square");

        myshape.findCorners();

    }

}

Output:

Compile and run the program to get the output.

C:\raji\blog>javac ShapesEg.java

C:\raji\blog>java ShapesEg

Square has four Corners          

This design Pattern is useful for frameworks.

That’s it. The Java Program to implement Factory Design Pattern was written and executed successfully. Hope, this code is useful to you.

Design Patterns Introduction and Singleton Pattern implementation in Java

What is Design pattern?

    It gives you a structured approach to solve a common problem in software development. Basically, it gives you a reusable code which is easy to maintain. It is flexible too.

Let us categorize the design patterns.

  • Creational patterns
  • Structural patterns
  • Behavioral patterns

Each of the pattern has its own features given as follows

Creational Patterns:

              As the name suggests, it deals with object creation. For example, Singleton, Builder and Factory design patterns.

Structural Patterns:

              These design patterns deal with classes.The main purpose is to structure the class and relationships are made.

Eg: Adapter, Decorator and Proxy.

Behavioral Patterns:

              This design pattern is made for communication between objects.

Eg: Command, Observer and Strategy.

Let us create Singleton Design Pattern.

Java implementation of Singleton Pattern:

              This design pattern has only one instance across the entire application. Even the user creates more than one instance.

  • Singleton class is created with one instance in1.
  • ‘getInstance() method checks the instance is created or not. If it is not created, it creates the instance here.
  • ‘showMessage()’ displays the message.
  • In the main() function, two instances created. But both are equal.

Program:

class Singleton {

    private static Singleton in1;

    private Singleton() {} // Private constructor

    public static Singleton getInstance() {

        if (in1 == null) {

            in1 = new Singleton();

        }

        return in1;

    }

    public void showMessage() {

        System.out.println("Singleton instance is accessed here!");

    }

}

public class SDPEg {

    public static void main(String[] args) {

        Singleton ob1 = Singleton.getInstance();

        Singleton ob2 = Singleton.getInstance();

        ob1.showMessage();

        System.out.println(ob1 == ob2);

    }

}

Output:

Compile and run the above program to get the output

C:\raji\blog>javac SDPEg.java

C:\raji\blog>java SDPEg

Singleton instance is accessed here!

True

This design pattern is used in Database connections and logging.

This is the way of creating Singleton design pattern in java. Hope, it will be useful to you. Keep Coding!!!!

The producer- consumer Problem in java

    It is an evergreen synchronization problem in operating system. It has two entries. They are

  • ·       Producer
  • ·       Consumer

Producer is the one, which generates the item and adds it to a shared region. Consumer is the one which retrieves the item from the shared region and processes it.

So, synchronization plays a vital role here.

To handle this problem, the method “BlockingQueue” is used.

Technical implementation:

              This implementation creates two threads Producer and Consumer as Runnable.

  • A private final BlockingQueue as integer. In the constructor, initialise the value.
  • In the run() method,insert the value for queue and make the thread to sleep for some time.
  • Similarly, do the above steps for Consumer thread also.
  • Finally, in the main() function, create objects for queue. Using these objects, start the
  • Threads.

Program:

import java.util.concurrent.BlockingQueue;

import java.util.concurrent.LinkedBlockingQueue;

class Producer implements Runnable {

    private final BlockingQueue<Integer> queue1;

    public Producer(BlockingQueue<Integer> queue1) {

        this.queue1 = queue1;

    }

    @Override

    public void run() {

        for (int i = 1; i <= 5; i++) {

            try {

                System.out.println("Produced: " + i);

                queue1.put(i); // inserts item to the queue

                Thread.sleep(1000); // Delay

            } catch (InterruptedException e) {

                Thread.currentThread().interrupt();

            }

        }

    }

}

class Consumer implements Runnable {

    private final BlockingQueue<Integer> queue1;

    public Consumer(BlockingQueue<Integer> queue1) {

        this.queue1 = queue1;

    }

    @Override

    public void run() {

        while (true) {

            try {

                Integer item = queue1.take(); // Retrieves item

                System.out.println("Consumed: " + item);

                Thread.sleep(1500); // Delay

            } catch (InterruptedException e) {

                Thread.currentThread().interrupt();

            }

        }

    }

}

public class ProducerConsumerEg {

    public static void main(String[] args) {

        BlockingQueue<Integer> queue1 = new LinkedBlockingQueue<>(3);

        Thread producer1 = new Thread(new Producer(queue1));

        Thread consumer1 = new Thread(new Consumer(queue1));

        producer1.start();

        consumer1.start();

    }

}

Output:

C:\raji\blog>javac ProducerConsumerEg.java

C:\raji\blog>java ProducerConsumerEg

Produced: 1

Consumed: 1

Produced: 2

Consumed: 2

Produced: 3

Consumed: 3

Produced: 4

Produced: 5

Consumed: 4

Consumed: 5

This is the way of creating Producer consumer Problem in java. Hope, you are understanding about the concept. Keep Coding!!!

Counting connected components in a graph

               It is a basic problem in graph. A graph contains nodes and edges. Nodes can be a vertices and edges connecting the nodes.

Here, connected component means every node is reached from any other node. The traversal of node may be DFS(Depth First Search) or BFS(Breadth First Search) according to it.

Let us count the counted component in graph.

Program implementation:

  • This program gets the number of nodes and edges as input.
  • It uses DFS(Depth first Search) to traverse the nodes. ‘g_dfs()’ used to traverse the graph.
  • It gets the nodes, adjacent list and a Boolean value ‘g_visited’ to perform the traversal.
  • It sets the ‘g_visited’ value when it reaches the node.
  • ‘countIt()’ -This function gets the number of nodes and edges as input.
  • It checks the ‘g_visited’  value for entire graph. Find the edges visited. Finally, gives you the count.
  • ‘main()’ – this function assigns the input value as number of nodes and edges. It calls the countIt() function to get the counting value.  

Program:

import java.util.*;

public class CCCGEg {

    private static void g_dfs(int g_node, List<List<Integer>> g_adjList, boolean[] g_visited) {

        g_visited[g_node] = true;

        for (int neighbor : g_adjList.get(g_node)) {

            if (!g_visited[neighbor]) {

                g_dfs(neighbor, g_adjList, g_visited);

            }

        }

    }

    public static int countIt(int n, int[][] edges) {

        List<List<Integer>> g_adjList = new ArrayList<>();

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

            g_adjList.add(new ArrayList<>());

        }

        for (int[] edge : edges) {

            g_adjList.get(edge[0]).add(edge[1]);

            g_adjList.get(edge[1]).add(edge[0]);

        }

        boolean[] g_visited = new boolean[n];

        int count = 0;

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

            if (!g_visited[i]) {

                g_dfs(i, g_adjList, g_visited);

                count++;

            }

        }

        return count;

    }

    public static void main(String[] args) {

        int n = 4;

        int[][] edges = {{0, 2},{2, 3}, {3,1}};

        System.out.println("The Count of connected components are: " + countIt(n, edges));

    }

}

Output:

C:\raji\blog>javac CCCGEg.java

C:\raji\blog>java CCCGEg

The Count of connected components are: 1

This is the way of creating the java program to count the connected components in a graph was done. Hope, this code gives you clear understanding to you. Keep coding!!!  

Java Program to find Subsets of a Set

               Set has a collections of elements. Sub set contains the combinations of elements. It can be done by bit manipulation or recursion.

Java implementation:

  • It starts with including the built in packages java.util.ArrayList and java.util.List.
  • A public class is created with main ().
  • A integer array is assigned with elements.
  • A subset is developed as list. Let us call the findSubset() function to get the subsets.
  • ‘findSubset()’ – This function creates the subsets of the given set.
  • Finally, it prints the sub sets.

Technical information:

Class name: SubsetFinderEg

Variables:

set1 as integer array.

subset1 as integer list.

Index as integer

‘all_Subsets, ‘new_Subset’,’more_Subsets’ as array list.

S_item as integer.

Member function: findSubset().

Program:

//include the built-in packages.

import java.util.ArrayList;

import java.util.List;

//class creation with main() class

public class SubsetFinderEg {

    public static void main(String[] args) {

        int[] set1 = {4, 2, 5}; //elements assignement

        List<List<Integer>> subset1 = findSubset(set1, 0);

        System.out.println(subset1);

    }

    public static List<List<Integer>> findSubset(int[] set1, int index) {

        List<List<Integer>> all_Subsets;

        if (index == set1.length) {

            all_Subsets = new ArrayList<>();

            all_Subsets.add(new ArrayList<>()); // insert empty set

        } else {

            all_Subsets = findSubset(set1, index + 1);

            int s_item = set1[index];

            List<List<Integer>> moreSubsets = new ArrayList<>();

            for (List<Integer> subset : all_Subsets) {

                List<Integer> new_Subset = new ArrayList<>(subset);

                new_Subset.add(s_item);

                moreSubsets.add(new_Subset);

            }

            all_Subsets.addAll(moreSubsets);

        }

        return all_Subsets;

    }

}

Output:

Compile and run the program to get the output.

C:\raji\blog>javac SubsetFinderEg.java

C:\raji\blog>java SubsetFinderEg

[[], [5], [2], [5, 2], [4], [5, 4], [2, 4], [5, 2, 4]]

Yes. That’s the output.

Here the set has 3 elements [4,2,5]

The sub sets are [], each element separately [2],[4],[5], combination of two elements [5,2],[5,4],[2,4] and finally all number combinations [5,2,4].

This is the way of creating subsets from a set using java. Hope,this code will useful to you. Keep Coding!!!!

Huffman Encoding implementation in java

 Huffman Encoding is an algorithm which provides compression of data. The encoding deals with the character frequencies to reduce the size of data.

Java implementation:

              This process starts with finding the frequency of each character. Next, it creates the Huffman Tree by the use of a  priority  queue.

Finally, it develops the binary codes for each character.

Program:

import java.util.PriorityQueue;

import java.util.HashMap;

import java.util.Map;

// let us create the class with character with its frequency

class HuffmanNode implements Comparable<HuffmanNode> {

    char h_char;

    int h_freq;

    HuffmanNode h_left, h_right;

    HuffmanNode(char h_char, int h_freq) {

        this.h_char = h_char;

        this.h_freq = h_freq;

    }

 

    @Override

    public int compareTo(HuffmanNode other) {

        return this.h_freq - other.h_freq;

    }

}

 

// class for Huffman Encoding technique

public class HuffmanEncodingEg {

    public static Map<Character, String> huffmanCodes = new HashMap<>();

    // recursive method to generate Huffman code

    public static void generateIt(HuffmanNode root, String code) {

        if (root == null) return;

        if (root.h_left == null && root.h_right == null) {

            huffmanCodes.put(root.h_char, code);

        }

        generateIt(root.h_left, code + "0");

        generateIt(root.h_right, code + "1");

    }

    // Develop the Huffman Tree and code

    public static Map<Character, String> buildHuffmanTree(Map<Character, Integer> freqMap) {

        PriorityQueue<HuffmanNode> pq1 = new PriorityQueue<>();

        for (Map.Entry<Character, Integer> entry : freqMap.entrySet()) {

            pq1.add(new HuffmanNode(entry.getKey(), entry.getValue()));

        }

        while (pq1.size() > 1) {

            HuffmanNode h_left = pq1.poll();

            HuffmanNode h_right = pq1.poll();

            HuffmanNode newNode = new HuffmanNode('-', h_left.h_freq + h_right.h_freq);

            newNode.h_left = h_left;

            newNode.h_right = h_right;

            pq1.add(newNode);

        }

        HuffmanNode root = pq1.poll();

        generateIt(root, "");

        return huffmanCodes;

    }

    public static void main(String[] args) {

        String txt = "It is huffman coding Sample";

        Map<Character, Integer> freqMap1 = new HashMap<>();

        for (char c : txt.toCharArray()) {

            freqMap1.put(c, freqMap1.getOrDefault(c, 0) + 1);

        }

        Map<Character, String> huffmanCodes = buildHuffmanTree(freqMap1);

        System.out.println("The Huffman Codes are:");

        for (Map.Entry<Character, String> entry : huffmanCodes.entrySet()) {

            System.out.println(entry.getKey() + ": " + entry.getValue());

        }

    }

}

Output:

C:\raji\blog>javac HuffmanEncodingEg.java

C:\raji\blog>java HuffmanEncodingEg

The Huffman Codes are:

p: 00

a: 101

S: 111

e: 110

l: 100

m: 01

Hope this code will help you! Keep coding!!!!

Implementing a Trie for word search in Java

What is a Trie?

              It is a data structure looks like a tree. Usually, it stores the data and retrieves it accordingly. It is similar to prefix tree.

Usage: prefix lookup, insert a data and fast search.

Applications: spell checking,dictionary and autocomplete.

Program implementation:

              The implementation starts with including the built-in package java.util.

Classes included in this program:

TrieNodeEg :it creates the node and its elements.

TrieEg : This develops the root node and its value. It includes three member functions.

TrieSample:It is in main() function. it creates the object and calls the member functions to execute to get the output.

Member variables:

Children -it is a hash map object.

isEOF – it is a Boolean value for store the EOF value.

t_root -root elements

t_node – node element

wrd – input to the member functions.

ch -character element.

‘insert()’ – add the elements to the structure.

‘search()’ -it finds an elements.

‘startWith()’ – it checks the data starts with a particular data or not.

Program:

import java.util.*;

class TrieNodeEg {

    Map<Character, TrieNodeEg> children;

    boolean isEOF;

    public TrieNodeEg() {

        children = new HashMap<>();

        isEOF = false;

    }

}

class TrieEg {

    private TrieNodeEg t_root;

    public TrieEg() {

        t_root = new TrieNodeEg();

    }

    public void insert(String wrd) {

        TrieNodeEg t_node = t_root;

        for (char ch : wrd.toCharArray()) {

            t_node.children.putIfAbsent(ch, new TrieNodeEg());

            t_node = t_node.children.get(ch);

        }

        t_node.isEOF = true;

    }

    public boolean search(String wrd) {

        TrieNodeEg t_node = t_root;

        for (char ch : wrd.toCharArray()) {

            if (!t_node.children.containsKey(ch)) {

                return false;

            }

            t_node = t_node.children.get(ch);

        }

        return t_node.isEOF;

    }

    public boolean startsWith(String prefix) {

        TrieNodeEg t_node = t_root;

        for (char ch : prefix.toCharArray()) {

            if (!t_node.children.containsKey(ch)) {

                return false;

            }

            t_node = t_node.children.get(ch);

        }

        return true;

    }

}

public class TrieSample {

    public static void main(String[] args) {

        TrieEg trie1 = new TrieEg();

        trie1.insert("Car");

        trie1.insert("Vehicle");

        trie1.insert("Bus");

        System.out.println(trie1.search("Car"));

        System.out.println(trie1.search("Vehicle"));  

        System.out.println(trie1.search("Van")); 

        System.out.println(trie1.startsWith("Bus"));

    }

}

Output:

C:\raji\blog>javac TrieSample.java

C:\raji\blog>java TrieSample

true

true

false

true

This is the way of creating Word search application using Trie Structure in java. Hope, this code is beneficial to you. Keep coding!!!!

N-Queen Problem in java

              It is a backtracking method to solve the problem. Basically, it is a NxN chessboard which has N queens. It should not attack each other.

Java Implementation:

  • Create a public class with main() function.
  • Add four functions solveNQueensPbm(),backtracking(),isItSafe(),printItBoard().
  • solveNQueensPbm() – create a character array. add the data. Call the backtracking() function.
  • backtracking() – it checks the row with n value and call the printItBoard() function. use for loop to perform backtracking().
  • printItBoard() -It prints the board and queens value.
  • ‘main()’- it creates the value for n and calls the solveNQueensPbm() to get the output.

Program:

import java.util.Arrays;

public class NQueensEg {

    public static void solveNQueensPbm(int n) {

        char[][] board1 = new char[n][n];

        for (char[] q_row : board1) Arrays.fill(q_row, '.');

        backtracking(board1, 0, n);

    }

    private static void backtracking(char[][] board1, int q_row, int n) {

        if (q_row == n) {

            printItBoard(board1);

            return;

        }

        for (int q_col = 0; q_col < n; q_col++) {

            if (isItSafe(board1, q_row, q_col, n)) {

                board1[q_row][q_col] = 'Q';

                backtracking(board1, q_row + 1, n);

                board1[q_row][q_col] = '.';

            }

        }

    }

    private static boolean isItSafe(char[][] board1, int q_row, int q_col, int n) {

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

            if (board1[i][q_col] == 'Q') return false;

        }

        for (int i = q_row, j = q_col; i >= 0 && j >= 0; i--, j--) {

            if (board1[i][j] == 'Q') return false;

        }

        for (int i = q_row, j = q_col; i >= 0 && j < n; i--, j++) {

            if (board1[i][j] == 'Q') return false;

        }

        return true;

    }

    private static void printItBoard(char[][] board1) {

        for (char[] q_row : board1) {

            System.out.println(new String(q_row));

        }

        System.out.println();

    }

    public static void main(String[] args) {

        int n = 4;

        solveNQueensPbm(n);

    }

}

Output:

C:\raji\blog>javac NQueensEg.java

C:\raji\blog>java NQueensEg

.Q..

...Q

Q...

..Q.

 

..Q.

Q...

...Q

.Q..

This output has 4 columns in each row. Q refers ‘queens’. It does not cross each other.

That’s the way, the Java Program to implement N queens Problem was done successfully. Keep coding!!!

How to implement the java Program to generate permutation of string?

 What is permutation?

              It is a specific order of arrangement in alphabets or numbers. Generally, it arranges the set of elements.

In terms of mathematics, it uses factorial concept.

For eg:

 ‘XY’ – this is the input string.

The permutations are { ‘XY,’YX’}

Program implementation:

Class: permutationString

Member functions:

‘generateIt()’

‘main()’

Member variables:

‘str1’ ,’perm1’ , ‘s_remaining’, ‘sample’ -String variables

‘s’ – character variable

Logic:

  • Read the input.
  • Call the generateIt() function. it need to two arguments. One is the input string and permutation string.
  • ‘generateIt()’ function checks the input string is empty or not.
  • If it is not empty, it creates a for loop.
  • Create the permutations using recursion.
  • Finally, print the result.

Program:

public class permutationString {

    //User defined function to generate permutation

    public static void generateIt(String str1, String perm1) {

        if (str1.isEmpty()) {

            System.out.println(perm1);

            return;

        }

       //for loop to create permutaions

        for (int i = 0; i < str1.length(); i++) {

            char s = str1.charAt(i);

            String s_remaining = str1.substring(0, i) + str1.substring(i + 1);

            generateIt(s_remaining, perm1 + s);

        }

    }

    //main() function

    public static void main(String[] args) {

        String sample = "XYZ";

        System.out.println("Permutations of " + sample + ":");

        generateIt(sample, "");

    }

}

Output:

Compile and execute the program to get the output.

C:\raji\blog>javac permutationString.java

C:\raji\blog>java permutationString

Permutations of XYZ:

XYZ

XZY

YXZ

YZX

ZXY

ZYX

That’s all. The Java Program to generate the permutations using String is done. Keep Coding!!!