Longest Palindromic Substring

    Brute force

Time complexity: O ( n^3 )
Auxiliary complexity: O ( 1 ).

    Dynamic programming

Time complexity: O ( n^2 )
Auxiliary complexity: O ( n^2)

package geeks.dp;

import java.io.BufferedReader;

import java.io.IOException;

import java.io.InputStreamReader;

public class LongestPalindromeSubstring {

       private static int max = 0;

       public static void main(String[] args) throws IOException {

           BufferedReader buffReader = new BufferedReader(

                                         new InputStreamReader(System.in));

           System.out.println("Input String !!");

           char[] inputChars = buffReader.readLine().toCharArray();

             

           int length = inputChars.length;

             

           int[][] dp = new int[length+1][length+1];

             

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

               for (int j = 1; j <=length; j++) {

                   if(inputChars[i-1]==inputChars[length-j]) {

                        dp[i][j] = dp[i-1][j-1]+1;

                   } else {

                        dp[i][j] = 0;

                   }

                   max = Math.max(dp[i][j], max );

               }

          }

          System.out.println(max);

       }

}

Output:

Input String !!

geeksskeeggeeksskeeg

20

Inversion of control (IoC) and dependency injection

The Inversion of Control (IoC) and Dependency Injection (DI) patterns are all about removing dependencies from your code.

Example: Our application has a text editor component and we want to provide spell checking.

Our standard code would look something like this:

public class TextEditor {
       private SpellChecker checker;
       public TextEditor() {
              this.checker = new SpellChecker();
       }

}

What we've done here is create a dependency between the TextEditor and the SpellChecker.

In an IoC scenario we would instead do something like this:

public class TextEditor {
       private ISpellChecker checker;
       public TextEditor(ISpellChecker checker) {
              this.checker = checker;
       }
}

Now, the client creating the TextEditor class has the control over which SpellChecker implementation to use. We're injecting the TextEditor with the dependency.

It is a process whereby objects define their dependencies, that is, the other objects they work with, only through constructor arguments, arguments to a factory method, or properties that are set on the object instance after it is constructed or returned from a factory method.

The container then injects those dependencies when it creates the bean.

This process is fundamentally the inverse, hence the name Inversion of Control (IoC), of the bean itself controlling the instantiation or location of its dependencies by using direct construction of classes, or a mechanism such as the Service Locator pattern.

IoC containers:

1. BeanFactory

2. ApplicationContext

Dependency injection may happen through 3 ways:

1. Constructor injection.

2. Setter injection.

3. Interface injection

Design Principle vs.Design Pattern

Object Oriented Programming

OOP is a programming paradigm that represents concepts as “objects” that have data fields (attributes that describe the object) and associated methods. Objects (instances of classes) are used to interact with one another to design applications and computer programs.

OO basics principles:

Polymorphism

Abstraction

Encapsulation

Inheritance

Design Principles:

Design principles are core abstract principles which we are supposed to follow while designing software architect. Remember they aren't concrete; rather abstract.

OO principle is a set of guidelines that ensures OOP concept.Based on the OOP concept, this defines ways to design better way, a better design.

Examples:

1. Single Responsibility Principle

2. Open Close Principle

3. Liskov’s Substitution Principle

4. Interface Segregation Principle

5. Dependency Inversion Principle

Design Patterns:

They are solutions to real world problems that pop up time and again, so instead of reinventing the wheel, we follow the design patterns that are well-proven, tested by others, and safe to follow. Now, design patterns are specific, there are terms and conditions only in which they can be applied.

OO design patterns (OODPs) are those which provide a general solution to object oriented design based OO principle.

Design patterns are discovered, not invented.

Examples:

Singleton Pattern

Factory pattern.

Spring Bean

The objects that form the backbone of your application and that are managed by the Spring IoC container are called beans.

Any normal Java POJO class can be a Spring Bean that is instantiated, assembled, and otherwise managed by a Spring IoC container. These beans are created with the configuration metadata that you supply to the container, for example, in the form of XML definitions.

Spring/IoC container

The Spring/IoC container is at the core of the Spring Framework. It is responsible to instantiate, wire them together, configure them, and manage their complete lifecycle from creation till destruction.

The spring container uses dependency injection (DI) to manage the components that make up an application. The IoC container gets informations from the XML file and works accordingly.

Major tasks performed by IoC container:

To instantiate the application class

To configure the object

To assemble the dependencies between the objects

Different type of IoC containers:

1. BeanFactory

interface org.springframework.beans.factory.BeanFactory

The XmlBeanFactory is the implementation class for the BeanFactory interface.

Resource resource = new ClassPathResource("applicationContext.xml");  

BeanFactory factory = new XmlBeanFactory(resource); 

Employee s = (Employee) factory.getBean("e");

The constructor of XmlBeanFactory class receives the Resource object so we need to pass the resource object to create the object of BeanFactory.

2. ApplicationContext

interface org.springframework.context.ApplicationContext

The ClassPathXmlApplicationContext class is the implementation class of ApplicationContext interface.

ApplicationContext context=new ClassPathXmlApplicationContext("applicationContext.xml");
HelloWorld obj = (HelloWorld) context.getBean("helloWorld");

What is database deadlock? How can we avoid them?

Database deadlock

When multiple external resources are trying to access the DB locks and runs into cyclic wait, it may make the DB unresponsive.

Avoid Database deadlock

1. Can make a queue wherein we can verify and order the request to DB (To run the operations in FIFO order).

2. Less use of cursors as they lock the tables for long time (slow down the DML executions).

3. Keeping the transaction smaller (process query relation operation before start the transactions).

What algorithm is used in modern day elevators?

Knuth's Elevator algorithm

The elevator algorithm, a simple algorithm by which a single elevator can decide where to stop, is summarised as follows:

1. Continue travelling in the same direction while there are remaining requests in that same direction.

2. If there are no further requests in that direction, then stop and become idle, or change direction if there are requests in the opposite direction.

The elevator algorithm has found an application in computer operating systems as an algorithm for scheduling hard disk requests.

Modern elevators use more complex heuristic algorithms to decide which request to service next.

http://cdn.kone.com/major_projects.kone.com/Images/elevcon2008-elevator-traffic-simulation-procedure.pdf?v=3

Parallelism vs Concurrency

Parallelism

Parallelism means that an application splits its tasks up into smaller subtasks which can be processed in parallel, for instance on multiple CPUs at the exact same time.

Example:If a person is listening to music while writing an assignment then work done is in parallel way.

Concurrency

A condition that exists when at least two threads are making progress. A more generalized form of parallelism that can include time-slicing as a form of virtual parallelism.

If the computer only has one CPU the application may not make progress on more than one task at exactly the same time, but more than one task is being processed at a time inside the application. It does not completely finish one task before it begins the next.

Example:If a person is watching TV while writing an assignment then work done is in concurrent way.

Pizza Factory design in Java

Design patterns used:

1.     Abstract Factory,

2.     Template method pattern (to define the preparation sequence).

VeggiePizza.java

package com.pizza.factory;

public class VeggiePizza extends Pizza {

     public VeggiePizza() {

           name = "Veggie Pizza";

           dough = "Crust";

           sauce = "Marinara sauce";

           toppings.add("Shredded mozzarella");

           toppings.add("Grated parmesan");

           toppings.add("Diced onion");

           toppings.add("Sliced mushrooms");

           toppings.add("Sliced red pepper");

           toppings.add("Sliced black olives");

     }

     @Override

     public voidprepare() {

           System.out.println("Add Veggie !!");

     }

     @Override

     public voidbake() {

           System.out.println("Bake Veggie Pizza !!");

     }

     @Override

     public voidcut() {

           System.out.println("Cut Veggie Pizza !!");

     }

     @Override

     public voidpack() {

           System.out.println("Pack Veggie Pizza !!");

     }

}

CheesePizza.java

package com.pizza.factory;

public class CheesePizza extends Pizza {

    

     public CheesePizza() {

           name = "Cheese Pizza";

           dough = "Regular Crust";

           sauce = "Marinara Pizza Sauce";

           toppings.add("Fresh Mozzarella");

           toppings.add("Parmesan");

     }

     @Override

     public voidprepare() {

           System.out.println("Add Cheese !!");

          

     }

     @Override

     public voidbake() {

           System.out.println("Bake Cheese Pizza !!");

          

     }

     @Override

     public voidcut() {

           System.out.println("Cut Cheese Pizza !!");

          

     }

     @Override

     public voidpack() {

           System.out.println("Pack Cheese Pizza !!");

     }

}

Pizza.java

package com.pizza.factory;

import java.util.ArrayList;

public abstract class Pizza {

     

      String name;

      String dough;

      String sauce;

      ArrayList<String> toppings = new ArrayList<String>();

     

     

    /**

     * Template method Pattern - Sequence of processes.

     * To define the sequence to prepare Pizza.

     */

    public finalvoidtemplatePizzaPrepare() {

     

      /*Step#1. prepare Pizza integrants */

      prepare();

     

      /*Step#2. bake the Pizza. */

      bake();

     

      /*Step#3. cut the slice of Pizza. */

      cut();

     

      /*Step#4. pack the Pizza. */

      pack();

    }

      public abstract void prepare();

     

      public abstract void bake();

     

      public abstract void cut();

     

      public abstract void pack();

}

SimplePizzaFactory.java

package com.pizza.factory;

public class SimplePizzaFactory {

    

     public static Pizza orderPizza(String type) {

          

           Pizza pizza = null;

          

           if("cheese".equals(type)) {

                pizza = new CheesePizza();

           } else if("veggie".equals(type)) {

                pizza = new VeggiePizza();

           }

          

           pizza.templatePizzaPrepare();

           return pizza;

     }

}

PizzaStore.java

package com.pizza.factory;

public class PizzaStore {

     public static void main(String[] args) {

           Pizza pizza  = SimplePizzaFactory.orderPizza("cheese");

          

           System.out.println("\nPizza ready : "+ pizza.name);

          

           /*pizza  = SimplePizzaFactory.createPizza("veggie");

           System.out.println("Pizza type : "+ pizza);*/

     }

}