What's advanced algorithm?

 Emphasis is placed on fundamental algorithms and advanced methods of algorithmic design, analysis, and implementation. Techniques to be covered include amortization, randomization, fingerprinting, word-level parallelism, bit scaling, dynamic programming, network flow, linear programming, fixed-parameter algorithms, and approximation algorithms. Domains include string algorithms, network optimization, parallel algorithms, computational geometry, online algorithms, external memory, cache, and streaming algorithms, and data structures.

 Sorry, it took so long for me to get this one out! Advanced Algorithms are very complex if you are not aware of the fundamentals of DS-ALGO, The more advanced material takes quite a bit longer to produce.

While it’s not completely necessary to take Big-O Data Structures and Big-O Algorithms first, I would recommend it, even if you’ve learned this stuff before. It doesn’t cost any extra, and the refresher will really help. I won’t rehash all the Big-O complexity stuff here, because I’m assuming you’re already familiar with it. we will focus on implementing some of the more advanced algorithms that you would learn in a CS undergraduate degree and learn how you can recognize when algorithms of this sort will help you in your future career.

What’s included?

There are four modules.

Module 1 – Graph Theory

In this module, we have a brief refresher on graph data structures and implement some basic traversal algorithms like breadth and depth-first search. We also cover different types of graphs, like complete and directed graphs, and how they can be represented in code.

Module 2 – Advanced Searches

In this module, we really round out our experience with graphs. We learn about greedy algorithms, and how they can help us write faster code. We also implement a priority queue so that we can use it as we do a deep dive on Dijkstra’s algorithm. Finally, we finished the module by writing an A* search that can find its way quickly through a muddy map – similar to what you’d need to write as a game developer.

Module 3 – Dynamic Programming

In this module, we shift gears and learn about how memoization and tabulation techniques can be used to optimize various algorithms by trading memory for speed. We re-write the classic Fibonacci function using dynamic programming, as well as the super useful edit-distance algorithm. Edit distance is used in the real world to calculate the similarity in spellings between words, just like how spell-checkers work.

Module 4 – Linear Programming

In the final module, we shift the gears yet again to focus more on the mathematical side of things. Linear programming is a technique used to solve linear systems of equations, specifically optimization problems. We build from scratch a Simplex solver in any programming language that you know and use it to calculate the exact number of cookies and cakes a baker should produce in order to maximize the profit in her shop.

This is all about advanced algorithms.

Behavioral Design Pattern - Interpreter Pattern Java

Behavioral Interpreter Design Pattern 

we're going to look at the interpreter design pattern. The interpreter pattern is a behavior pattern that you used to represent the grammar of a language. A lot of tools use this pattern when parsing various aspects of grammar. 

Let's look at some of the concepts considered when choosing this pattern.

 the concept surrounding why you would choose the interpreter pattern or that it represents grammar. This could be music notation or mathematical equations, or even another language. Compilers will use the interpreter pattern too often. 

 This goes hand in hand with representing the grammar, but we can then use it to interpret a sentence. This enables us to map out a domain-specific language. If you've ever used SQL or an XML parser, this is the exact thing that is. 

This pattern was designed to do define a language that can be interpreted to do things you'll often see an interpreter used when defining an abstract syntax tree. To examples of this in the Java API. The Java Util pattern, the pattern classes used to represent a compiled regular expression, is an incredibly powerful way to search through strings. Another representation is the java class format is an abstract-based class that is used to represent locale-sensitive content such as dates, numbers, and strings. Let's look at some of the design considerations when choosing this pattern.

 

 the design of the interpreter is quite a bit different than most of the other patterns that we've looked at. There is an abstract-based class or an abstract expression that declares an interface for executing an operation. That operation is an interpreted method. Expressions are then broken into terminal expressions, which represent a leaf of a tree or an expression that does not contain other expressions. If it does contain other expressions then it's a nonterminal expression. Nonterminal expressions represent compound expressions and continue. So we called itself a recursive tree until it finally represents a terminal expression or multiple subexpressions. 

The pieces of the UML diagram are the context, abstract expression, terminal expression, non-terminal expression, and a client.

 Example: Pattern

the pattern class used in conjunction with regular expressions is a good example of the interpreter pattern being used in the Java API. We created sentences and establish grammar for that sentence. From there, we're going to interpret the sentence and display what we parsed using the pattern. Let's look at this in life code now.

Code :

package interpreterpattern;

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class InterpreterJavaAPIDemo {

    public static void main(String[] args) {
        String input = "Lions , and tigers , and bears! oh , my";
        Pattern p = Pattern.compile("(Lions , and tigers , and bears! oh , my)");
        Matcher m = p.matcher(input);
        while (m.find()) {
            System.out.println("Found a " + m.group() + ".");
        }
    }
}

Output :
Lions Bears is true

Demo Structure for real-time project implementation:

package interpreterpattern;

public class InterpreterDemo {

    static Expression buildInterpreterTree() {

        Expression terminal1 = new TerminalExpression("Lions");
        Expression terminal2 = new TerminalExpression("Tigers");
        Expression terminal3 = new TerminalExpression("Bears");

        Expression alternation1 = new AndExpression(terminal2, terminal3);
        Expression alternation2 = new OrExpression(terminal1, alternation1);

        return new AndExpression(terminal3, alternation2);
    }

    public static void main(String[] args) {
        //  String context = "Lions";
        // String context = "Tigers";
        //  String context = "Tigers";
        //String context = "Lions Tigers";
        String context = "Lions Bears";
        Expression define = buildInterpreterTree();
        System.out.println(context + " is " + define.interpret(context));
    }
}

package interpreterpattern;

public interface Expression {

    boolean interpret(String context);
}

package interpreterpattern;

public class OrExpression implements Expression {
    private Expression expr1 = null;
    private Expression expr2 = null;
    public OrExpression(Expression expr1, Expression expr2) {
        this.expr1 = expr1;
        this.expr2 = expr2;
    }
    @Override
    public boolean interpret(String context) {
        return expr1.interpret(context) || expr2.interpret(context);
    }
}

package interpreterpattern;

import java.util.StringTokenizer;

public class TerminalExpression implements Expression {

    private String data;

    public TerminalExpression(String data) {
        this.data = data;
    }

    @Override
    public boolean interpret(String str) {
        StringTokenizer st = new StringTokenizer(str);
        while (st.hasMoreTokens()) {
            String test = st.nextToken();
            if (test.equals(data)) {
                return true;
            }
        }
        return false;
    }
}

package interpreterpattern;

public class AndExpression implements Expression {

    private Expression expr1 = null;
    private Expression expr2 = null;

    public AndExpression(Expression expr1, Expression expr2) {
        this.expr1 = expr1;
        this.expr2 = expr2;
    }

    @Override
    public boolean interpret(String context) {
        return expr1.interpret(context) && expr2.interpret(context);
    }
}

Output :

Lions Bears is true

Pitfalls

Now that we've created our own interpreter, let's look at some of the pitfalls of it. If the grammar becomes very complex, it can be difficult to maintain, as you noticed in our rule example that we had you could see very quickly that if I started adding these different answers or combinations, it could become a little bit interesting to try and debug and walkthrough. So complexity can be an issue there. There is at least one class per rule, so every time we create one of our new expressions were creating another class. Complex rules will require multiple classes to define them. That's where the difficulty of maintenance can come into play. The use of other patterns might help with your specific implementation of a complex interpreter, and adding a new variant requires us to change every variant of that class. The interpreter is a little unique compared to some of the other patterns that we have looked at because it is fairly specific to the problem that we're trying to solve to better understand when we should use this or a different pattern. Let's contrast it with the visitor pattern.

Contrast to Other Patterns

To contrast the interpreter pattern. Let's compare it with the visitor. The interpreter and the visitor are very similar in structure, but a different focus on implementation. The interpreter has access to properties because it contains the object. Functions are defined as methods, and since we extend implement the base interface, each interpret function is contained within a method. One drawback is that adding new functionality changes every variant recall the demo that we coated together when we were building the expression tree and the complexity that we could get by calm compounding those expressions together, the visitor is actually very similar to the interpreter, with some slight variations. Instead of having access to the properties we need, we have to implement the observer observable functionality to gain access to those properties similar to the interpreter. Functionality is found in one place, but it is in the visitors and not in the expression objects that were building and just like the interpreter. Adding a new variant requires changing every visitor. The focus is more about whether you're adding more expressions or grammar rules or adding new visitors to interact with, and that is the main focus on choosing one over the other.

Thanks.

 

Trapping Rain Water Problem

There is a very good question about Trapping Rain Water for arrays. Today I will give two solutions for this problem, Naive vs Efficient Solution. Let's understand the problem first.

Trapping Rain Water

So in the above example, you can only store a maximum of 6 units of water.

I/p= arr[] = {2,0,2}

o/p = 2 you can collect 2 Units of water in these bars. 

we are given an array of positive integers 

The elements are represented as Bars and the question is 

how much water you can store in this bar?

2nd Example :

arr[] = {3 , 0 , 1 , 2, 5 }

o/p = 6 

So now we are calculating that how much water we can

calculate suppose first is of height 3 units, 2nd bar

is of the height of 0 unit and so on ......

 if  you sum all the bars height collectively then 

 you will get the answer.

 Code ;

package dsalgo;

public class TrappingRainWaterProblem {
    // for input = arr[] = {3,0,1,2,5}
    public static void main(String[] args) {

        int arr[] = {3, 0, 1, 2, 5}, n = 5;
        System.out.println("Naive Solution:" + getWater(arr, n)); 
        System.out.println("Efficient Solution : " + 
                getWaterEfficientSolution(arr, n)); // efficient Solution
    }

    /*****Naive Solution****/
    public static int getWater(int arr[], int n) {
        int res = 0;

        for (int i = 1; i < n - 1; i++) {
            int lMax = arr[i];

            for (int j = 0; j < i; j++)
                lMax = Math.max(lMax, arr[j]);

            int rMax = arr[i];

            for (int j = i + 1; j < n; j++)
                rMax = Math.max(rMax, arr[j]);

            res = res + (Math.min(lMax, rMax) - arr[i]);
        }
        System.out.println("Naive Time : " + System.nanoTime());
        return res;
    }

    public static int getWaterEfficientSolution(int arr[], int n) {
        int res = 0;

        int lMax[] = new int[n];
        int rMax[] = new int[n];

        lMax[0] = arr[0];
        for (int i = 1; i < n; i++)
            lMax[i] = Math.max(arr[i], lMax[i - 1]);


        rMax[n - 1] = arr[n - 1];
        for (int i = n - 2; i >= 0; i--)
            rMax[i] = Math.max(arr[i], rMax[i + 1]);

        for (int i = 1; i < n - 1; i++)
            res = res + (Math.min(lMax[i], rMax[i]) - arr[i]);

        System.out.println("Efficient Time::" + System.nanoTime());
        return res;
    }

}

 

Output : 

Naive Time : 2745092805500

Naive Solution:6

Efficient Time::2745093880800

Efficient Solution : 6

Just increase the input array then you will see the visible difference in Naive vs. Efficient Solution.

I tried to solve it in a simplest way.

Behavioral Design Pattern - Command Pattern

 Command Design Pattern

So command design pattern is a behavioral pattern that lets you encapsulate. Each request is an object. Of curse, there are more reasons to implement that we will look into those reasons.

Why you would choose the command pattern? 

because it encapsulates. Each request is an object. If you have dealt with or are going to work with a large system, you'll quickly find that the business logic and functions inside that system can be very complex to maintain a debug if they're all just added in one file.

Another key reason for choosing this pattern is that each call back as a request is now object-oriented instead of just another method added insight of that growing class. Maintainability is also increased because the sender is decoupled from the processor. This will enable the system to be more flexible and grow over time, oftentimes, but not the only reason. You will use a command to add undo functionality to your application. The entire request should be contained within the command and then could be rolled back. 

 For Example, Runnable Pattern is a great example of a command Design Pattern. the design of the command is a little different than some of the other patterns and is sometimes argued that it breaks the principles of, oh design because there is an object per command, A command is a verb, and objects usually aren't verbs, but rather the methods inside them. But people have seemed to relax their view on this. The main contract of the command is the command interface, all implementations of actions or commands inside the framework will implement this interface and in its simplest form, just contains an execute method. This method is where all of the action is performed. In the case of an undue feature, the interface will also contain a UN execute or undue method. But this isn't required to adhere to the principles of this pattern. Advanced implementations of this pattern make use of reflection to completely decoupled the client from the receiver or processor using a callback. 

Most examples you see, though, are simpler than this version, and we're going to look at various examples is to see how to best exercise this action and implement it in your day-to-day use.

Code : Example -1 

package command;

public class CommandPattern {

    public static void main(String[] args) {
        Task t1 = new Task(10, 12);  // encapsulates request
        Task t2 = new Task(11, 13);

        Thread thread1 = new Thread(t1);
        Thread thread2 = new Thread(t2);

        thread1.start();//invoker
        thread2.start();
    }
}

class Task implements Runnable {
    int num1;
    int num2;

    public Task(int num1, int num2) {
        this.num1 = num1;
        this.num2 = num2;
    }

    @Override
    public void run() { // executor
        System.out.println(num1 * num2); // receiver
    }
}

Example -2 :

package command;

import java.util.ArrayList;
import java.util.List;

// client
public class CommandPatternExercise {

    public static void main(String args[]) {
        Light bedroomLight = new Light();
        Light kitchenLight = new Light();
        Switch lightSwitch = new Switch();

        Command toggleCommand = new ToggleCommand(bedroomLight);
        lightSwitch.storeAndExecute(toggleCommand);
        // lightSwitch.storeAndExecute(toggleCommand);
        //  lightSwitch.storeAndExecute(toggleCommand);
        //  lightSwitch.storeAndExecute(toggleCommand);
        List<Light> lights = new ArrayList<>();
        lights.add(bedroomLight);
        lights.add(kitchenLight);

        Command alllightsCommand = new AllLightsCommand(lights);
        lightSwitch.storeAndExecute(alllightsCommand);

    }
}

package command;

// receiver
public class Light {

    private boolean isOn = false;

    public boolean isOn() {
        return isOn;
    }

    public void toggle() {
        if (isOn) {
            off();
            isOn = false;
        } else {
            on();
            isOn = true;
        }
    }

    private void on() {
        System.out.println("Light switched on.");
    }

    private void off() {
        System.out.println("Light switched off.");
    }
}

  package command;

//invoker
public class Switch {

    public void storeAndExecute(Command command) {
        command.execute();
    }
}

package command;

public class ToggleCommand implements Command {

    private Light light;

    public ToggleCommand(Light light) {
        this.light = light;
    }

    @Override
    public void execute() {
        light.toggle();
    }

} 

Output :

Light switched on.

Light switched off.

So we can implement this design pattern in our real-time project and can extract lots of benefits from it. I learn this pattern 10 years ago Since I am using it from time to time in my projects.

What are some of the pitfalls of a command? 

It's typically used with other patterns to be more mature. The dependence on other patterns isn't necessarily a bad thing. It just requires more knowledge on the developer's part. I also often see people struggle with the use of multiple commands. Frequently, I see people make the mistake of duplicating logic in another command. A better way to do this is either the use of a composite pattern as we demonstrated or commands. Combined with the chain of responsibility pattern for undo functionality, you may want to look at it using the memento pattern to handle state. If you're tracking objects that need to store history, you may need to also look at the prototype pattern for creating copies of commands to store on a list to get a better idea. When we shouldn't or shouldn't use this pattern.

to contrast the command pattern. Let's compare it with the strategy. The command is structured around an object per command or per request. The class contains essentially, what we're trying to do. It also encapsulates CE in the entire action. The command object on Lee deals with this one exact scenario. Thes strategy, on the other hand, is similar to the command in that it is an object per request, with the focus on this pattern being per strategy different than the command. Though the strategy focuses on the how rather than the what. Instead of encapsulating the action, it encapsulates the algorithm. The structure of these patterns is very similar, though with just some slight variations.

That's it.

Chain Of Responsibility Design Pattern in JAVA

Why you would choose the chain of responsibility pattern?

Because they decouple the sender and receiver objects often times in an application. 
We want to pass a request to a receiving object without knowing who the sender was and vice versa. The sender shouldn't have to know who the receiver was in order for to process that request. When using the chain, the receiver should also contain a reference to the next receiver or the successor. This is an important part when choosing and implementing this pattern.

 It doesn't know the whole hierarchy, but it does know who's next in line. One of the main reasons for choosing this pattern is to promote loose coupling. 

We can modify the chain and add links to the chain without rewriting large portions of logic in the application. It should also be okay that there may not be a handler for a given request, and the application will just continue on examples of this in the job. For example how spring implements their security chain filter in spring security.

I will give two example one JAVA API reference and We will create one for us with real time example.

First lets have a look into the UML Diagram for the same.

UML Diagram:

Lets understand why we should consider this design pattern as you have seen the UML diagram.

the design of the chain Responsibility has a chain of receiver objects. This can be implemented in a number of ways, but some basic form of a list is typically the most common. Each handler is based off of a main interface that defines the contract between each chain link. There is a concrete handler for each receiver or implementation that will interpret a request in building the chain. Each handler has a reference to its successor or the next link in the chain. The pieces of the UML diagram are a handler and a concrete handler and then its successor.

Lets look into the code:

import java.util.logging.ConsoleHandler;
import java.util.logging.Level;
import java.util.logging.Logger;

public class ChainOfresponsibility
{
    private static final Logger logger = Logger.getLogger(ChainOfresponsibility.class.getName());
    public static void main(String[] args)
    {
        logger.setLevel(Level.FINER);
        ConsoleHandler handler = new ConsoleHandler();
        handler.setLevel(Level.FINER);
        logger.addHandler(handler);
        logger.finest("Finest");
        logger.finer("Finer");
        logger.fine("Fine");
    }
}

Output:

Jun 12, 2021 3:30:09 PM ChainOfresponsibility main

FINER: Finer

Jun 12, 2021 3:30:09 PM ChainOfresponsibility main

For Full source code go to my GitHub URL mentioned below:

https://github.com/Abhinaw/DesignPatternInJava/tree/master/src/chainofresponsibility

Here you will get all the required files for complete source code.

Let me explain the example that i took to implement this design pattern.

we have a hierarchy in our company such as CEO -> VP -> Director right?

So Director have some specific limited rights and VP have more rights as compared to Director and obviously, CEO have all the rights he can do anything he wants. here we have chain of responsibility.

More certainly, lets take example that Director can approve a purchase of Rs,1000 only and if it is more than Rs,1000 then it got to VP for approval and if it more than that it should go to CEO for the approval.

public class ChainOfResponsibility {

    public static void main(String[] args) {

        Director director = new Director();

        VP vp = new VP();

        CEO ceo = new CEO();

        director.setSuccessor(vp);

        vp.setSuccessor(ceo);

        Request request = new Request(RequestType.CONFERENCE, 500);

        director.handleRequest(request);

        request = new Request(RequestType.PURCHASE, 1000);

        director.handleRequest(request);

        request = new Request(RequestType.PURCHASE, 2000);

        director.handleRequest(request);

    }

FINE: Fine

Why Kotlin is Domain Specific Language?

There was this question asked to me recently by a developer and as a programmer, I can program this and tell you why kotlin is a domain-specific language? and have many advantages as a domain-specific language.

My Answer:

What Is a Domain Specific Language?

Kotlin is a great programming language with many features. One of the most amazing abilities it has is to allow developers to author DSLs.

 So let's say you have a customer who wants a manufacturing system that can assemble a fort. the customer could easily just want an Android app with many screens, but it could be fort, so let's keep talking about that. you might make some code that looks like this, a series of imperative commands to the computer.

 Create some objects and wire them together to create a fort that has two walls and a tower. This code is normal code we see everywhere throughout our projects. The code is imperative, which I use to describe code that tells the computer exactly what to do.

 

In comparison, So suppose now the customer wants something bigger and new style but fort. The new fort has four towers, four walls, a keep in the middle. Additionally, the fort has some new requirements about how towers can be connected. So you add more imperative code. It constructs the various objects and wires them together to create the final fort object. 

The code still fits fort this requirement at least. The customer is really enjoying his fort and has bigger plans for your fort building system. Now he is requesting a grand fort consisting of many towers, walls, and keeps going. Additionally, he wants to add some new kinds of structures that have additional requirements. 

You can imagine a lot of code is going to be needed just to create this complicated structure. After a lot of typing, you manage to code it and the customer, once again, leaves you alone. However You sit down at your computer to write another 1, 000 lines of configuration code but stop, maybe there is a way to make this configuration code simpler. 

How are you feeling about writing the code using your imperative style? Your initial fort construction code was only about 10 lines. The slightly more complicated fort was a little more, but then you hit this point where larger forts require thousands of lines of configuration, not only that, you can see that in the future business is good and you will be writing many more forts over and over again. 

When you encounter this type of situation, you start to look for some ways to make it easier to construct forts with less code. Now there are several ways you could accomplish this. You could improve the object model. Maybe you have objects that create parts of the fort and create some reasonable components. This is always a good idea because reducing code complexity is important. However, it may not help to make it easier to construct a fort with less code because you are still limited with your imperative programming style and you have not tried to clean up noisy syntax. 

Another option is to use a configuration file. It could be represented as JSON, for example. The JSON can describe the fort and its components, another part of your code reads into JSON and creates the fort object. The file serves as the domain-specific language for your fort object. 

The advantage of this is that you are free to express the problem in any way you like. The downside is you need to implement the parser and other tools to interpret this new syntax. 

DSLs with their own syntax like this are called external DSLs. Often, they are not a good option because external DSLs require the extra work of writing parsers and result in DSLs with no IDE support. 

Now your third option is to create a DSL written in the Kotlin programming language. You can write the DSL to be just regular Kotlin syntax, however, you will not be writing normal Kotlin code. Instead, you're going to focus on using Kotlin's features to improve the syntax and customize it for forts building. 

This way allows you to create a DSL that helps you write more concise fort building code that is more easily understood. These are called internal DSLs and I think they are the sweet spot for utilizing DSLs effectively. 

Let's look at the problem another way.

Demo: Create a List of Towers

It looks like the customer is sending you a gentle reminder, we need to add towers to the DSL. One task you might need to accomplish in a DSL is to add a list of items. Doing so requires creating a special object within a DSL implementation. To get a clean syntax for specifying the towers, the DSL implementation needs a helper class. The Helper class is focused on creating a list of TowerBuilder objects.

Now, let's look into our code how it will look  like rather explaining things 

My Main Class will build any type of forts-based customer configuration and let's look at how easy is to configure this as compared to damn any-any language in the CS field.

Before jump into code just think of a real fort or castle how it can be.

fun main(args : Array<String>) {
    FortBuilder().build()
}

class FortBuilder {
    fun build() {
        var builder = FortBuilder()

        // function sequence
        builder.keep("keep")
        builder.tower("sw") // these are directions south-west
        builder.tower("nw")
        builder.tower("ne")
        builder.tower("se")
        builder.connect("sw", "nw")  // connects with each other
        builder.connect("nw", "ne")
        builder.connect("ne", "se")
        builder.connect("se", "sw")

        // apply
        builder.apply {
            keep("keep")
            tower("sw")
            tower("nw")
            tower("ne")
            tower("se")
            connect("sw", "nw")
            connect("nw", "ne")
            connect("ne", "se")
            connect("se", "sw")
            connect("keep", "nw")
            connect("keep", "nw")
            connect("keep", "se")
            connect("keep", "sw")
        }

        // builders
        builder = FortBuilder()
        builder.keep("keep").tower("sw")
               .tower("nw").tower("ne").tower("se")
        builder.connect("keep", "sw").connect("keep", "ne")
               .connect("keep", "se").connect("keep", "sw")
        builder.connect("sw", "nw").connect("nw", "ne")
               .connect("ne", "se").connect("se", "sw")
        val castle = builder.build()
        println("result: $castle")

        // use varargs for this one
        builder.connectToAll("keep", "sw", "nw", "ne", "se")

        // using map syntax
        builder.connect(mapOf("sw" to "nw", "nw" to "ne",
                              "ne" to "se", "se" to "sw"))
    }
}

class FortBuilder {
    private var towers = mutableListOf<Tower>()
    private var keep: Keep? = null
    private var connections = mutableMapOf<String, String>()

    fun tower(name: String) : FortBuilder {
        val tower = Tower(name)
        towers.add(tower)
        return this
    }

    fun keep(name: String = "keep") : FortBuilder {
        keep = Keep(name)
        return this
    }

    fun connect(from: String, to: String): FortBuilder {
        connections[from] = to
        return this
    }

    fun connectToAll(from: String, vararg to: String): FortBuilder {
        for (toConnect in to) {
            connect(from, toConnect)
        }
        return this
    }

    fun connect(map: Map<String, String>) {
        map.forEach { from, to ->
            connect(from, to)
        }
    }

    fun build(): Castle {
        val symbols = StringSymbolTable<Connectable>()
        towers.forEach { symbols.add(it.name, it) }
        keep?.let {
            symbols.add(it.name, it)
        }

        val allWalls = connections.map { (from, to) ->
            Wall(symbols.lookup(from), symbols.lookup(to)) }
        return Fort(keep, towers, allWalls)
    }
}

data class Fort(var keep: Keep?, var towers: List<Tower>
,var walls: List<Wall>)
data class Keep(override var name: String = "keep"): Connectable
data class Tower(override var name:String): Connectable
data class Wall(var from: Connectable, var to: Connectable)

Done that's it.

how easy it is as a developer if I think of Java here believe me it will be huge lines of code and very complex objects we need to handle. So would request to make them in any other language. you will notice the difference.

here you can connect to any towers to anything and create a bridge, wall, etc.

Suppose client asked you to create any other type of fort the idea is the base configurations will remain the same I mean you need a wall, the tower you need to connect them even you can any other configuration very easily without breaking anything and you do not have to write everything from scratch this is the beauty of the Kotlin and that is why I say it says domain-specific language.

Thanks.

Difference between Single Linked List and Generalized Linked List ?

What is the difference between Single Linked List and Generalized Linked List?

Generalized Linked List

A Generalized Linked List L, is defined as a finite sequence of n>=0 elements, l1, l2, l3, l4, …, ln, such that li are either atom or the list of atoms. 

Thus

L = (l1, l2, l3, l4, …, ln)

where n is a total number of nodes in the list.

To represent a list of items there are certain assumptions about the node structure.

Flag = 1 implies that down pointer exists

Flag = 0 implies that next pointer exists

Data means the atom

Down pointer is the address of node which is down of the current node

Next pointer is the address of node which is attached as the next node

Why Generalized Linked List?

Generalized linked lists are used because the efficiency of polynomial operations using linked lists is good but still, the disadvantage is that the linked list is unable to use multiple variable polynomial equations efficiently. It helps us to represent multi-variable polynomial along with the list of elements. 

Representation of GLL, for example: 

When the first field is 0, it indicates that the second field is variable. If the first field is 1 means the second field is a down pointer, which means some list is starting.

Polynomial Representation using Generalized Linked List

The typical node structure will be:

Here Flag = 0 means variable is present

Flag = 1 means down pointer is present

Flag = 2 means coefficient and exponent is present

Now let's take an example:

This is basically 9x^5 + 7xy^4 + 10xz

Single Linked List :

import java.util.*;

import java.io.*;

import java.lang.*;

class AbhiBlog { 

    static class Node{

        int data;

        Node next;

        Node(int x){

            data=x;

            next=null;

        }

    }

    public static void main(String args[]) 

    { 

        Node head=new Node(10);

    Node temp1=new Node(20);

    Node temp2=new Node(30);

    head.next=temp1;

    temp1.next=temp2;

    System.out.print(head.data+"-->"+temp1.data+"-->"+temp2.data);

    } 

} 

So it is like a One-way chain or singly linked list that can be traversed only in one direction. In other words, we can say that each node contains only the next pointer, therefore we can not traverse the list in the reverse direction.

But we can add two polynomial using a doubly-linked list efficiently.

WhatsApp - Forwarding multiple messages in whatsapp follows which type of data structure

Interesting Interview Question for Senior Developer :  

Well I have multiple opinions on the same such as 

1) Whatsapp and most chat clients on the client-side use SQLite (A tiny embeddable database software) to store the data, and so the chat client does NOT use any data structure on their own and just calls the order-by query on the database, which gives them the list of chats ordered by the time.

This means the database has an index on the date and time of the last chat, and for this, if you look at the SQLite documentation, they use the often-used data structure of b-trees.

2)The data structure used in the queue.

A queue essentially works on the principle of "First In First Out".

A queue is maintained for each user which contains the message to be delivered to the user.

When the user comes online the messages in the queue are delivered and the queue is deleted.

Nothing is stored on the server.

3)WhatsApp uses a customized version of the open standard Extensible Messaging and Presence Protocol (XMPP)

WhatsApp follows a 'store and forwards' mechanism for exchanging messages between two users. When a user sends a message, it first travels to the WhatsApp server where it is stored. Then the server repeatedly requests the receiver acknowledge receipt of the message. As soon as the message is acknowledged, the server drops the message.

Well according to me it would be based on some key facts about networking.

For Delivered: After the message would be received at the client's phone an acknowledgment message sent would be pushed from the client's phone.

For Reading by When the user opens the screen where the message is present, again a notification would be sent this won't require implementing complex data structures but utilizing the features of the protocols being used for transmission. Which have become a part of WhatsApp now.

Whereas sent would indicate message being sent from your phone to the servers at WhatsApp

So for implementing this when in a group chat the message response needs to be stored in a queue that would verify all the above steps for each member in the group and accordingly will set the Status.

Now coming to an important point the original and "native" transport protocol for XMPP is Transmission Control Protocol (TCP), using open-ended XML streams over long-lived TCP connections, and TCP/IP protocol uses a network congestion-avoidance algorithm that includes various aspects of an additive increase/multiplicative decrease (AIMD) scheme, with other schemes such as slow-start to achieve congestion avoidance.

This could be one of the algorithms being implemented for network acknowledgments, they added a lot more features as they have customized XMPP to use on top of their transmission.

I hope I have answered your queries. Thanks.

Upload-Download Any FileType .PDF,MP3,MP4,.DOCX in Database and Without Database in SpringBoot Gradle Build System - Java

 Upload-Download Any FileType .PDF,MP3,MP4,.DOCX in Database and Without Database in SpringBoot :

I have asked to create a file upload-download demo in spring boot on the Gradle build system. So this for my students and beginners who want to understand the API how to develop file upload-download. Even you can view the same in your browser.

Our Spring Boot Application will provide APIs for:

Uploading File to MySQL database

downloading File database with the link

These are APIs to be exported:

Methods Urls Actions

POST /upload upload a File

GET /files get List of Files (name, url, type, size)

GET /files/[fileId] download a File

The uploaded files will be stored in the MySQL Database files table with these fields: id, name, type, and data as BLOB type (Binary Large Object is for storing binary data like file, image, audio, or video).

Let me explain it briefly.

– FileDocument is the data model corresponding to the files table in the database.

– FileDBRepository extends the Spring Data JPA repository which has methods to store and retrieve files.

– FilesStorageService uses FileDBRepository to provide methods for saving new file, get file by id, get list of Files.

– FilesController uses FilesStorageService to export Rest APIs: POST a file, GET all files’ information, download a File.

– FileUploadExceptionAdvice handles exceptions when the controller processes file upload.

– ResponseFile contains information of the file (name, URL, type, size) for HTTP response payload.

– application.YAML contains configuration for Servlet Multipart and MySQL database connection.

– pom.xml for Spring Boot, Spring Data JPA, and MySQL connector dependency.

Full Souce Code Accessible Here on below path:
https://github.com/Abhinaw/demo/tree/master

Below is the test results for reference :

Folder Location where file is getting stored : FileStorage Folder in project

     Folder Location where file is getting stored

Source Code :

import com.greenlearner.fileuploaddownload.dto.FileUploadResponse;
import com.greenlearner.fileuploaddownload.service.FileStorageService;
import org.springframework.core.io.Resource;
import org.springframework.http.HttpHeaders;
import org.springframework.http.MediaType;
import org.springframework.http.ResponseEntity;
import org.springframework.util.StreamUtils;
import org.springframework.web.bind.annotation.*;
import org.springframework.web.multipart.MultipartFile;
import org.springframework.web.servlet.support.ServletUriComponentsBuilder;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.zip.ZipEntry;
import java.util.zip.ZipOutputStream;

@RestController
public class UploadDownloadWithFileSystemController {

    private FileStorageService fileStorageService;

    public UploadDownloadWithFileSystemController(FileStorageService fileStorageService) {
        this.fileStorageService = fileStorageService;
    }

    @PostMapping("single/upload")
    FileUploadResponse singleFileUplaod(@RequestParam("file") MultipartFile file) {

        String fileName = fileStorageService.storeFile(file);

        ///http://localhost:8081/download/abc.jpg
        String url = ServletUriComponentsBuilder.fromCurrentContextPath()
                .path("/download/")
                .path(fileName)
                .toUriString();

        String contentType = file.getContentType();

        FileUploadResponse response = new FileUploadResponse(fileName, contentType, url);

        return response;

    }

    @GetMapping("/download/{fileName}")
    ResponseEntity<Resource> downLoadSingleFile(@PathVariable String fileName, HttpServletRequest request) {

        Resource resource = fileStorageService.downloadFile(fileName);

//        MediaType contentType = MediaType.APPLICATION_PDF;

        String mimeType;

        try {
            mimeType = request.getServletContext().getMimeType(resource.getFile().getAbsolutePath());
        } catch (IOException e) {
            mimeType = MediaType.APPLICATION_OCTET_STREAM_VALUE;
        }
        mimeType = mimeType == null ? MediaType.APPLICATION_OCTET_STREAM_VALUE : mimeType;

        return ResponseEntity.ok()
                .contentType(MediaType.parseMediaType(mimeType))
//                .header(HttpHeaders.CONTENT_DISPOSITION, "attachment;fileName="+resource.getFilename())
                .header(HttpHeaders.CONTENT_DISPOSITION, "inline;fileName=" + resource.getFilename())
                .body(resource);
    }

    @PostMapping("/multiple/upload")
    List<FileUploadResponse> multipleUpload(@RequestParam("files") MultipartFile[] files) {

        if (files.length > 7) {
            throw new RuntimeException("too many files");
        }
        List<FileUploadResponse> uploadResponseList = new ArrayList<>();
        Arrays.asList(files)
                .stream()
                .forEach(file -> {
                    String fileName = fileStorageService.storeFile(file);

                    ///http://localhost:8081/download/abc.jpg
                    String url = ServletUriComponentsBuilder.fromCurrentContextPath()
                            .path("/download/")
                            .path(fileName)
                            .toUriString();

                    String contentType = file.getContentType();

                    FileUploadResponse response = new FileUploadResponse(fileName, contentType, url);
                    uploadResponseList.add(response);
                });

        return uploadResponseList;
    }

    @GetMapping("zipDownload")
    void zipDownload(@RequestParam("fileName") String[] files, HttpServletResponse response) throws IOException {
//zipoutstream - zipentry+zipentry

        try (ZipOutputStream zos = new ZipOutputStream(response.getOutputStream())) {
            Arrays.asList(files)
                    .stream()
                    .forEach(file -> {
                        Resource resource = fileStorageService.downloadFile(file);

                        ZipEntry zipEntry = new ZipEntry(resource.getFilename());

                        try {
                            zipEntry.setSize(resource.contentLength());
                            zos.putNextEntry(zipEntry);

                            StreamUtils.copy(resource.getInputStream(), zos);

                            zos.closeEntry();
                        } catch (IOException e) {
                            System.out.println("some exception while ziping");
                        }
                    });
            zos.finish();

        }

        response.setStatus(200);
        response.addHeader(HttpHeaders.CONTENT_DISPOSITION, "attachment;fileName=zipfile");
    }
}

This is without a database just upload and download files to a particular location.

application.yaml:

server:
  port: 8081

file:
  storage:
    location: fileStorage

spring:
  servlet:
    multipart:
      enabled: true
      location: temp123
      file-size-threshold: 5MB
      max-file-size: 20MB
      max-request-size: 20MB

  datasource:
    url: jdbc:mysql://localhost:3306/db?useSSL=false
    username: root
    password:
    driver-class-name: com.mysql.cj.jdbc.Driver

Gradle dependency:

dependencies {
   //my sql connector
   compile 'mysql:mysql-connector-java:8.0.17'
   implementation 'org.springframework.boot:spring-boot-starter-thymeleaf'
   implementation 'org.springframework.boot:spring-boot-starter-data-jpa'
   implementation 'org.springframework.boot:spring-boot-starter-web'
   testImplementation('org.springframework.boot:spring-boot-starter-test') {
      exclude group: 'org.junit.vintage', module: 'junit-vintage-engine'
   }
}

Thanks.