Cryptography

There are two type of cryptography

1. Symmetric

2. Asymmetric (Public key encryption)

Symmetric

Two major algorthims are

1. Data Encryption Standard (DES)

2. Advanced Encryption Standard (AES)

Main Components of Symmetric Cryptography

1. Plaintext (P): The original message 
2. Encryption algorithm (EA):  Performs a complex combination of substitutions/transpositions
3. Secret Key (K): Controls substitutions/transpositions of plaintext
4. Ciphertext (C): The scrambled message C = EA(P,K)
5. Decryption algorithm (DA): Retrieves the original message P = DA(C, K)

Two general ways of attacking symmetric algorithms:

1. Cryptanalysis

• Relies on some knowledge of the algorithm, P, or even sample P-C pairs
  
• Uses algorithms characteristics (weaknesses) to deduce P or K
  

2. Brute-force

• Uses every possible K on C until P is obtained
  
• On average, half of all possible keys must be tried before success

Asymetric  (Public key encryption and Digital Signature)

First proposed by Diffie and Hellman in the late 70s

Based on mathematical operations and not on simple bit operations

It is asymmetric, i.e., there is a public key (Kpub) and a private key (Kpri)

Entities advertise their Kpub in yellow pages but keep their Kpri secret

P = Plaintext and C = Ciphertext

The encryption and decryption algorithms E are identical

The public and private keys are different but related; either of the two can be used for encryption, with the other used for decryption.

It is computationally infeasible to determine the decryption key given only the encryption key and the knowledge of the encryption algorithm

Main mathematical properties:

1. C = E (P, Kpub) and P = E (C, Kpri)

2. C = E (P, Kpri) and P = E (C, Kpub)

Data Communications and Networking http://www.sju.edu/~bforoura/courses/lectures/stallings2004/chap16.html

RSA was first developed by MIT scientists Rivest, Shamir and Adleman in 1977

It is the industry standard for public-key encryption

A block cipher where P and C are integers between 0 and n-1 for some n

The basic idea:

C = Pe mod n

P = Cd mod n = (Pe)d = Ped mod n

Sender and receiver know n and e but only the receiver knows d

The keys are:

Kpub = {e, n}

Kpri = {d, n}

General requirements:

It's possible to find e, d and n such that Ped = P mod n for P <>

It's easy to calculate Pe and Cd for P <>

It's computationally infeasible to determine d given e and n

Servlet, JSP

1. What are methods of Servlet and Why the servlet has init() method?Servlet is Basic interface that contains these methods

1. init(ServletConfig)
2. service(ServletRequest, ServletResponse)
3. destroy()
4. getServletConfig()
5. getServletInfo()

Then implemented abstract classes are GenericServlet and HttpServlet.

Now constructor can not be define in interface, but init can have as skeleton in interface,

so any servlet using the interface knows that what need to be override to initialize a servlet.

Q. which pattern is this? Templating pattern

2. What is necessary to override init() method of Servlet?

There are no necessary conditions to override this particular method. In case you are overridding init(ServletConfig config), then make sure to call super.init(config).

3. Context Object pattern

A context object encapsulates web server specific HTTP information in more general and portable

form. It is used when:

1. you have components and services that need access to the system information.You want to decouple application components and services from the protocol specifics of system information.
2. you want to expose only relevant APIs within a context.
3. Use a context object to encapsulate state in a protocol-independent way to be shared throughout your application.

4. Life cycle of servlet and jsp

Servlet : init(), service(), destroy()

JSP: translation, and above all

5. Difference between in static and dynamic include

1. The syntax for static include is and the syntax for dynamic include is
   
2. Static include is an inline inclusion. i.e., the contents of the file will be included at translation phase. It’s something like a copy and paste. In case of dynamic include the response of the file will be included to the original response at runtime. The file will be processed separately and only the response will become the part of the original files’ response.
3. Static include cannot have a dynamic filename. This is because the servlet container needs the files for inclusion, at translation phase itself. 
4. Static include cannot accept a parameter dynamic can.
5. Static includes are faster than dynamic includes.
6. In case if the resource lost occurs, container will throw 500(Internal Server Error) for static, though 404(Page Not Found Error) for dynamic include

6. Difference between forward and sendRedirect

1. When you invoke a forward request, the request is sent to another resource on the server, without the client being informed. This process occurs completely within the web container. When a sendRedirtect method is invoked, it causes the web container to return to the browser indicating that a new URL should be requested. 
2. In case of sendRedirect browser issues a completely new request any object that are stored as request attributes before the redirect occurs will be lost. 
3. Redirect is slower than forward
4. forward is method of RequestDespatcher and sendRedirect is of request 

7. Inversion Of Control (IoC) and Dependency Injection (DI) are concepts generally associated with the Spring Framework.  The easiest way to think of Inversion Of Control is what Rod Johnson (founder of the Spring framework) calls the Hollywood Principal, "don't call us we'll call you:.  IoC uses interfaces to acquire and release resources a prime example being JDBC connections.  This also part of the reason Spring works so well with Object/Relational Mapping (ORM) tools such as Hibernate, iBatis, and TopLink.

DI is a more specific version of IoC.  DI pushes application dependencies at runtime.  DI comes in several flavors in Spring:

    1.  Setter Injection - uses Java Bean setters (and getters) to get dependencies

    2.  Contructor Injection - dependencies come from constructor arguments

    3.  Method Injection - where the container is used to implement dependencies

8. Explain Struts navigation flow

---

When we deploy our application in the server, at first the container reads the information from web.xml file.Here ActionServlet object will be created and init() of ActionServlet will be called.Here ActionServlet is the backbone to the whole application.
When client send a rewuest using .jsp extension , getters() and reset() of FormBean will be called. When client fill the form and press on submit button, then setters() and validate() will be called.
If the data is not valid ,then the form redirects to another page which is specified in struts-config.xml file. If the data is valid , then only Action class object will be created.
In Action class , have execute() which have return type of ActionForward. We can specify the business logic in Model and provide that object in execute(). After completion of business logic execution , then it forwards to another page ( either success or failure) , whichis specified in struts-config.xml file.
Action classes of struts uses Command pattern and overall as a web flow, it uses MVC pattern.

Data structure and algorithms

1. How to reverse a string?

swap the charecters from initial to end and converge till middle point

2. How to reverse a sentence?

Put the words in linked list, and swap the nodes, this way words will also be reversed.

Other thing is,

swap the every charecter of sentence, on each space, swap the word again, sentence will be reversed but words wont

3. How to find the Median/middle of a List.

Traverse with two pointers, single and double, when double points to end, single will be at middle.

4. How to find cycle in the List.

Traverse with two pointers, single and double, at any point of time, double will reverse back and will point to single, means there is cycle, otherwise, stop till single reaches to the end, means no cycle.

5. Given a graph, find the cycle

6. Reversing a linkedlist: 

Again swap the first elment to last and converge to the middle.

7. Swaping two variables

1. using temp

2. Using arithmetic

  void swap(int &i, int &j) {

       i=i+j;        j=i-j;        i=i-j;    }

 3. XOR method

 void swap(int &i, int &j){

      i = i ^ j;       j = j ^ i;       i = i ^ j; 

 } 

8. Finding the merging point of two list

List1 length=L1

List2 length=L2

Start traversing from longer list, traverse till (L1-L2), Now start comparing the values of L1 and L2, after this point merge point is 

equidistant from each List, If equality found means merge point exist otherwise not. 

Mergring point index in Longer list=(L1-L2) + no of nodes required to reach merge point

Merging point index in small list= no of nodes required to reach merge point

9. How to find fibonacci of a number in o(logn) time.

Using these two formula, it can be achieved

F(2n-1) = F(n-1)2 + F(n)2
F(2n) = ( 2 F(n-1) + F(n) ) F(n)

check this link for detail

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibFormula.html#exact

10. How to find nth max element in an Array.

By the approach of quicksort, choosing pivot at ith posivition make sure that ith max element is the pivot. We need to iterate only n times max to find out.  Other approach could be, after partitioning if n > i, then move ahead with quicksort in right  otherwise in left, and slowly we can converge to the nth index where pivot element will be only one, and of course that will the nth max element.

....??? not complete

Design Patterns

1. Singleton

Possibly the simplest design pattern is the singleton, which is a way to provide one and only one object of a particular type. 

Sample code

==========================================
final class Singleton {

  private static Singleton s = new Singleton(47);

  private int i;

  private Singleton(int x) { i = x; }

  public static Singleton getReference() {

    return s;

  }

  public int getValue() { return i; }

  public void setValue(int x) { i = x; }

}
==========================================

Points:
1. Must make all constructors private 2. create at least one constructor to prevent the compiler from synthesizing a default constructor
3. We should protect the class by cloning also, so the final is been used.

Double Checked Locking in Sigleton Pattern

public static Singleton CreateInstance() {    

if(instance == null) 

//first check   {       

// Use a mutex locking mechanism  that suits your system       

LockCriticalSection();        

if (instance == null) 

//second check       {         

instance = new Singleton();       

}       

UnLockCriticalSection();    

}    

return instance;

}

2. Strategy Pattern: Choosing the algorithm at run time

3. Template Pattern: Define the skeleton of an algorithm in an operation, deferring some steps to subclasses. Template Method lets subclasses redefine certain steps of an algorithm without changing the algorithm's structure. Example, all servlets, JSPs, Thread

Some questions
==========================================
1. Structurally, the difference between Proxy and State is simple: a Proxy has only one implementation, while State has more than one. The application of the patterns is considered (in Design Patterns) to be distinct: Proxy is used to control access to its implementation, while State allows you to change the implementation dynamically.

2. Difference between AbstractFactory and Factory
Abstract Factory:- provide an interface to create a family of related or  dependant classes without specifying their concrete classes. Abstract factory pattern is typically used for giving implementation to specification (eg., jdbc, servlet specifications etc...).

Factory Method :-  another creational pattern, Defines an interface for creating An Object, but let sub class decide which class to instantiate.