New Thread implement Runnable or extend Thread

One of the most fundamental design question which is often asked in Java interviews is, if you were to create a new thread, would you extend Thread class or would you choose to implement Runnable and why.

Answer to this question is implement Runnable and the reason provided in most cases is that the class can extend any other class in future, if required. Though the answer is correct but, is that the good enough design consideration to create a new thread this way.

The actual design consideration is you should only extend Thread when you are "extending (enhancing)" the functionality provided by the Thread class and not for providing your business functionality. For instance, if you want to provide a Thread Class which can be Serialized(I don't know why and how you want to do that, this is just a hypothetical situation) and then this class can be used elsewhere as way to spawn serializable threads, then you should actually go ahead and extend thread but, if purpose to create a thread is to execute some business functionality, always go about implementing Runnable.

How To : All Permutations of a String

This is one question you will come across in one or the other java interviews. Though it sounds very difficult when you hear it for the first time, but actually this can be achieved quite easily if you think about it a little in terms of recursion.

Lets take a simple example of a string "ABC" to understand and see how this can be done.

Here, we will see how to approach the problem and try to reach a solution .

Solution:

We start the solution with 2 Strings one given as input and other empty which we call as the output. Then we start creating all the permutations of the string iteratively and recursively.

What need to do is take a character out from the given string, populate it in the output string. All we need to do now is to do this step again with these updated string. Here is the Java code snippet to do the same.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

public void permute (String output, String input){ String temp = null; if(input.length() > 1){ for(int i = 0; i < input.length(); i++){ temp = removeCharacter(input, input.charAt(i)); permute(output+input.charAt(i), temp); } } else { System.out.println(output+input); } } public String removeCharacter(String input, char c){ StringBuilder temp = new StringBuilder(input); int index = input.indexOf(c); temp.replace(index, index+1, ""); return temp.toString(); }

For generating all permutations of a String "ABCD", we need to a call to the method permute like

1	permute("", "ABCD");

Below is the diagram which depicts how each string varies after each iteration and each recursive call. Each level in the tree represents represents a recursive call whereas siblings in the tree represents the iteration.

This code will work only if all the characters in the input string are unique, but will generate some repeated permutations if some or all of the characters are repeated.

Now the question arises, how to handle the scenario where characters are repeated? What you can do is instead of displaying a permutation as and when you get it, you can store it in HashSet. This will eliminate all the duplicates. At the end you can display the entire content of the set. Though this approach works there are memory implication if your input string is really large. To handle those scenarios the algorithm in itself needs to be enhanced to take care of duplicates strings, without using extra memory to the extent of storing all the strings created.