Interview Question: String Permutation

There are lot of question we encounter during an interview but there are few question which repeats in many interviews. But due to our lousy nature, every time we end up begging mercy to change the question. My friend has gone through such painful experience many time. But this time he can not resist himself to find the solution of the question. Though he could not find the solution and ask me to relieve his burden. So I thought of enlighten world with my half cooked knowledge.

Question: Find all the permutation of a string?
Condition A: Find if all characters of the string are unique?

Answer: How should be start writing the code? If you look at the permutation mechanism it has a certain pattern. Lets examine it with different possible combination of string ABC

   1: --- Start with A ---

   2: ABC

   3: ACB

   4: --- Start with B ---

   5: BAC

   6: BCA

   7: --- Start with C ---

   8: CAB

   9: CBA

Ok, it is still less clear can we look for a bigger example. Lets look for ABCD

   1: --- Starting with A---

   2: A BCD

   3: A BDC

   4: A CBD

   5: A CDB

   6: A DBC

   7: A DCB

   8:  

   9: --- Starting with B ---

  10: B ACD

  11: B ADC

  12: B CAD

  13: B CDA

  14: B DAC

  15: B DCA

  16:  

  17: --- Starting with C ---

  18: CABD

  19: CADB

  20: CBAD

  21: CBDA

  22: CDAB

  23: CDBA

  24:  

  25: ----Starting with D---

  26: DABC

  27: DACB

  28: DBAC

  29: DBCA

  30: DCAB

  31: DCBA

Now from above 2 code snippets it is clear puzzle for n can be broken into n-1 elements. If there are 4 elements then add 4th element to permutations of rest 3… Yes, you got the solution. It is a recursive process. Where we need to touch the bottom of the ocean and then return to water surface.

Code:

1: import java.util.ArrayList;

   2: import java.util.LinkedList;

   3: import java.util.List;

   4:  

   5: public class StringPermutations {

   6:  

   7:     List<String> strs = new LinkedList<String>();

   8:         

   9:     void printString(String str){

  10:         char[] charArray = str.toCharArray();

  11:         List<Character> charList = new ArrayList<Character>();

  12:         for(char ch: charArray){

  13:             charList.add(ch);

  14:         }

  15:         printCharacterArray(charList, new StringBuffer());

  16:         System.out.println(strs);

  17:     }

  18:  

  19:     private void printCharacterArray(List<Character> charList, StringBuffer temp) {

  20:         

  21:         StringBuffer savePoint = new StringBuffer(temp);

  22:         for(int index = 0; index <  charList.size(); index++){            

  23:             temp = new StringBuffer(savePoint);

  24:             temp.append(charList.get(index));

  25:             List<Character> tempChars = new ArrayList<Character>(charList);

  26:             tempChars.remove(index);

  27:             printCharacterArray(tempChars, temp);

  28:         }

  29:         if(charList.size() == 0){

  30:             strs.add(temp.toString());

  31:         }

  32:         temp = new StringBuffer();

  33:     }    

  34: }

Explanation:
In the above listing I have strs variable which keeps all the list.
printString method converts string into list of character and calls recursive function.
printCharacterScreen is a recursive method which iterate through the each element of the list and calls the same method again with list – element. The recursion breaks when there are no elements in the list then it adds the str to the list.
To run this code, copy the above code and save it to StringPermutations.java file. Add the following code of snippet.

1: public static void main(String[] args){

   2:     StringPermutations sp = new StringPermutations();

   3:     sp.printString("ABCD");

   4: }

Compile and run the class. It will print all combination of the ABCD string.

Condition B: if string has non-unique characters?
No issues, use java’s collection API well. Use Set instead of list to save all the string.

Disclaimer: The algo written here may not be performant. If you have some other algorithm which takes solves issue in lesser time complexity please let me know.

Object Oriented Programming Part 2

In earlier post we have already discovered Object oriented programming, orientation, its fundamentals and features. Here we will take up next remaining questions.

These are the questions whose answer are we seeking here in these blogs…

ü  What is Object Oriented Programming?

ü  What are the fundamental concepts/Features of OOP?

ü  What is Object Based Programming?

ü  What is Procedural programming?

ü  What are the features of Procedural programming?

ü  Compare basic features of the OOP and PP?

First 2 questions have already been answered in the first blog. Here I will start with the third question.

What is Object Based Programming?

Object based programming is associated with objects, objects which consist fields and methods similar to OOP. In object based programming few features(Abstraction, Polymorphism, Encapsulations, Inheritance) of OOP are included. It is not wrong to say, OBP is a subset of OOP where subset has all the features except few.

As I am not concentrating more on this paradigm so I am not going to invest much of your time here.

What is Procedural programming?

In Procedural programming instead of data; structure of the program is the determining feature. Here programmer concentrate on structure of the program instead the behaviour and state of the object.

Edsger Dijkstra's structured programming, where the logic of a program is a structure composed of similar sub-structures in a limited number of ways. This reduces understanding a program to understanding each structure on its own, and in relation to that containing it, a useful separation of concerns.

At low level. structure programming composed of simple, hierarchical program flow structures. These are Sequence(Ordered sequence of statements), selection (Decision making conditions) and repetition(repetitive statements).

In current scenario Fortron, Basic are using structured programming. Branch of structures programming used by Procedural programming which is implemented in C.

Procedural programming is a branch of structural programming where procedure are created on the basis of structures. Procedures are routines, subroutines, functions and their sequence.

What are the features of Procedural programming?

As stated above the poles of the procedural programming are methods, modules, functional calls, variables whereas procedural programming does not have features like abstraction, encapsulation, inheritance and polymorphism.

Methods: These can be understand as the basic feature. We create the structure of the program, divide it into sequence, selection, repetition and accordingly divide one routine to different subroutines and achieve the desired functionality.

Modules: n number of subroutines creates a module where all subroutines are scope specific.

functional calls: As oops uses messages pass between object here it is achieved by functional calls.

Variables: As PP does not belong to object, so each routine has its own variables associated with function’s scope.

Compare basic features of the OOP and PP?

Till now it is understood that Procedure based programming is much closer to deal with structure on the other side OOP only deals with objects, and blueprint of the objects.

Pros and Cons of PP: Procedure based programs tends to run quickly and use system resources efficiently. Whereas the drawback is that it does not fir gracefully with certain type of problems, such as in this paradigm programmer is forced to use structure approach to reach to the conclusion.

Pros and Cons of OOP: OOP is very similar to the perception of world, so it is less difficult to visualize things there. Code reuse is another big advantage of OOPS which is one among the hard hitting drawbacks of PP. OOP is runtime inefficient. It needs more memory and resource to run the program.

If we summarize the whole story, it is evident that none of the paradigm is inferior or superior. It is just our requirements which makes one preferred to us. To finalize the paradigm there are few factors which should be taken into account. First we should look for the data structure of the problem and accordingly should decide the paradigm. Benchmarking is another aspect which effects mostly testing efforts a lot. These 2 factors could highlight the preferences of selecting the programming structure.

I will take a break now. Again I am open to discussions, please post me your queries in comments.

Disclaimer: All the material here is the result of research and understanding of other material. If there is some content which is either incorrect or inappropriate to the context of the article I am always open for discussion.

Marker Interface

This post is not in the continuation of the last post. But this week I was searching about the marker interfaces. So I thought of documenting my learning about Marker Interfaces.

As it is known, Java interface defines contract between real world and objects, which implies when a class in implementing a java interface it has to implement all the methods defined in the interface.

What is a marker interface?

Marker interface is an interface which does not have any field and method associated with it.

/** 

* This interface is a marker interface. 

* For JVM it is just another interface without any method and field.

*/

public interface MarkerInterface {

}

Here as in the example above there is an interface which do not define any method and field. But this interface will compile without any issues.
/**

* MarkedClass is implementing MarkerInterface, 

* which means class MarkedClass is associated with MarkerInterface.

* This class will compile without any issues.

* */

public class MarkedClass implements MarkerInterface{

}

As mentioned in the example MarkedClass has been tagged as a MarkerInterface.
To compile this example you can copy the interface’s code to MarkerInterface.java file and copy class’s code to MarkedClass.java file.

What is the actual use of marker interfaces? Why will I prefer marker interface instead of an interface which has some methods?

Purpose of marker interfaces is to create a special type of Object, in such a way to restrict the classes that can be cast to it without placing ANY restrictions on the exported methods that must be provided. In another way these are used to provide metadata information to the classes.

To explain it further we can use an example…
There are quite a few IT organizations which primarily concentrate on product whereas there services are limited to their products and beside these organizations there are organizations which concentrate on services of the others products. These are classified as Product Organization and service organization.
A product company may sell their products either to Customer directly or to Service Company.  On the basis of the type of customer a product company wants to provide different set of contracts with the company. In general a product company has millions of customers and few service companies associated with it. So to distinguish between these two types of organization we mark Service companies with the marker interface.

This organization interface defines the contract.

/**

* This interface will have common utility methods that will be used across all the 

* customer as well as service organizations.  

*/ 

public interface Organization {

      String[] getProduct();     

      void setProduct(String[] products);

      //Many other such methods.      

}

This ServiceOrganization interface is a marker interface which will state the organization as a service organization.

/**
This interface is to mark an Organization as a Service Organization.

**/

public interface ServiceOrganization extends Organization{

}

Here you can see customer is implementing Organization, i.e. it is stating this Customer is not a special customer to me.
/**

* Customer is implementing Normal organization.

*/

public class Customer implements Organization {

@Override

public String[] getProduct() {

return null;

}

@Override

public void setProduct(String[] products) {

}

}

Now ServiceOrganization interface has been implemented by the Service customer class which will distinguish service customer from normal customer.
/**

* Service Customer has been tagged as service Organization but it does not need 

* to implement something other than method which will be defined by a

* common customer. 

*/

public class ServiceCustomer implements ServiceOrganization {

@Override

public String[] getProduct() {

return null;

}

@Override

public void setProduct(String[] products) {

}

}

As both types of customers have been separated with the use of marking, now it is not difficult to judge the customers.
Does Java have by default marker interface? If Yes, what all marker interfaces are there and what are their uses?
Yes, Java has few marker interfaces. Those are as follows:

java.util.RandomAccess

java.io.Serializable

java.rmi.Remote

java.util.EventListner

java.lang.Clonable

java.io.Serializable
When a class is implementing this interface this internally suggests to JVM that object of this class may be serialized for persistence purposes.
Source code for the interface is as mentioned below.
public interface Serializable {
}

So it is clear, writeObject and readObject methods are not part of the interface, but rather part of the serialization process, and help determine how to serialize an object.
java.lang.Clonable
Clonable interface is necessary to use clone method associated with each object. If clone is used without implementing clonable interface the code will throw a runtime exception.
java.util.EventListner
This interface also does not have any specific method but it is necessary for a class to implement the interface to achieve the functionality of listening the events.
java.util.RandomAccess
Implementing this interface suggests data accessing in the list is fast. So it is just marking list as fast random access. 
java.rmi.Remote
The remote interface serves to identify interfaces whose methods may be invoked from a non-local virtual machine. Any object that is a remote object must directly or indirectly implement this interface. Only those methods specified in a "remote interface", an interface that extends java.rmi.Remote are available remotely.
Here again marker interface has made sure if something has to access remotely then it should be marked with remote interface.
List of marker interfaces is long but the interfaces mentioned above are the widely known interfaces.

Like me You must be wondering, this all is fine but still there is one important question.
How does JVM deal with specific functionality of each marker interfaces?
I could not find something very specific to this question. But as most of the experts suggests Java does not do anything specific to identify the marker interface. instanceOf operator is used to identify whether the functionality is supported for the object or not.

If you look at the code of ObjectOutputStream.java, it is quite clear when serialization is supported by java.
//Piece of code of method - writeObject0(Object obj, boolean unshared){

.............

} else if (cl.isArray()) {

writeArray(obj, desc, unshared);

} else if (obj instanceof Serializable) {

writeOrdinaryObject(obj, desc, unshared);

} else {

throw new NotSerializableException(cl.getName());

}

.................

Now it is clear what are marker interfaces and at what instances do we use them. Java 5 release sun has introduced annotations, a way which will replace marker interface in future designs. Annotations are more descriptive and powerful mechanism to tag a class. I will talk about annotations in coming blogs..
Disclaimer: All the material here is the result of research and understanding of other material. If there is some content which is either incorrect or inappropriate to the context of the article I am always open for discussion.