Multithreaded Quick Sort

Quick sort is a classic example where we can use multiple threads, since execution proceeds on separate paths on separate segments. You can read about classic Quick Sort here.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately

Now check the last step, The two segments can be sorted and processes by 2 separate Threads easily as they don't depend on each other. In turn they can spawn more segments and more threads. For this we can use ThreadPool.

Multi-threaded Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately via Two Threads

INPUT

2

6

7

5

3

1

8

4

PROCESSING

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

THREAD 1 2 1 3	THREAD 2 5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Need for Immutable String in Java

While understanding String Immutability there were some answered questions as to why the designers of Java made String Immutable. We checked that String is immutable but Why so?

Well, it's difficult to go inside the brain of designers of java but based on the usage as of today we can speculate as to what would have been going on in their brain while making java immutable.

1. Easy storage and housekeeping

Strings are used a lot inside a program. A lot of Strings are repeated. For example in a College Database application, same names (Strings) are repeated again and again. Hence it makes better sense to keep a single copy of all strings at a single place (String Pool). Instead of creating new objects again and again. Garbage Collection and Storage of these high volume data becomes easy.

2. Hashcode does not change

Since Strings are immutable, their hascode won't change like other objects. Thus Strings do not calculate hashcode every time we call hashcode function, Hascode us kept cached. Since Strings are used a keys in HashMaps and other such Structures, we save a lot of time but not calculating hashcode every time we need to retrieve an Object.

3. Network Security

All passwords we enter online are strings. Bank details are passed as Strings. If they are mutable, anyone could change them over the network, which would wreak havoc. Same goes with classnames while loading a Class. 

4. Prevents Concurrency Issues

Since Strings are immutable, hence no need to synchronize. Hence no concurrency issues while using Strings.

String immutable in Java: What does it really mean?

This is one of the favourite questions at the fresher level that interviewer asks. Most of the candidates tend to gloss over this. If interviewer tends to go into this deep, most of the candidates tend to falter. At least that if what I have observed having interviewed hundreds of candidates in the past.

We will try and make this article single point of reference for Strings in Java. Hopefully we cover something that might be helpful to you. Read here, for knowing Why It was made Immutable.

Let's try and go in depth on String immutability.

Let's start by Source Code of String.java. I always say that source code is the best resource to learn a language.

How String is Immutable?
This question is self answered by the above code snippet. Member variable data type is final. Hence String Object once created becomes immutable in Java.

How come then we are able to assign same variable, a different value?
Now we are talking. Valid question. Let's check it via code,




So the question stands. What does immutability means?

Well, it can be explained by what happens internally. Variable immutable refers to a memory space which is allocated to "javaonjava. This memory allocation is what we call immutable. Same variable can point to different memory spaces.

String literals are stored separately in a String Pool. Once a String is Created, say "javaonjava". Whenever a new variable needs "javaonjava" String, a new String is not created. The old one is referenced. This is what we mean by immutability. So String Object is not immutable, String itself is immutable.

Compare it with any User defined object. When that object is updated, content is re-written on the same memory space. Hope things are getting clear now.

How to check String is immutable in Java

1. == (equals operator), is the best check.
As we read above StringPool contains single copy of a given String. So if this operator returns true on two string variables, it means they are pointing to same memory and content inside the StringPool






Thus we see, they both point to the same content.

2. No operations modify String





Thus we see neither concat, nor substring modifies the String. They simply create a new String, which is returned as we see below.





In the last example, what happens to "javaonjava" String. Well it remains in the StringPool but unreferenced. If not reused for considerable time, it could be Garbage Collected.

See the diagram below for better understanding

What is a Thread?

Thread relates to running of a program. A Thread is a single chain of execution within a program.

This above start to end path within a program is called a Thread. These steps can do a number of operations. For example if we are adding two numbers input by the user. This thread execution will comprise of the below steps:

1. Asking user for the input 1

2. Asking user for the input 2

3. Adding the two inputs

4. Printing the final sum.

A single program can have multiple executions in parallel. As in multiple threads. For example finding the sum of 10 input numbers.

Two separate threads can take 5 inputs separately and add them up. At the end, the two results can be added together to get the final sum. It's not that work speed increases magically. It's just a illusion, a trick by a magician.

Salient Features of a Thread

1. Thread is like a sub-process. Multiple thread paths can exist within a single process.

2. All threads share the same resources (memory, variables) within a process. This can result into conflict, hence needs to be handles carefully.

3. Apart from shared resources, each thread has its own stack space where it stores variables local to it.

4. One can argue that we can create multiple processes, then why is the need for multiple threads. You can read about it here. Multiple threads v/s Multiple processes.

Quick Sort

QuickSort works on the concept of dividing and proceeding.

An array is divided into two segments, One containing all small elements, other containing all higher elements (from a pivot element). The two segments are in-turn QuickSorted to get the sorted output.

Quick Sort Steps

1. Select an element as pivot (preferable the last element).

2. Shift the pivot such that all elements before it are smaller and after it after bigger (Pivot reaches correct position)

3. Sort the two segments (Before Pivot and After Pivot) separately.

INPUT

2

6

7

5

3

1

8

4

PROCESSING (4 is the pivot)

2

6

7

5

3

1

8

4

2

8

7

5

3

1

4

6

2

1

7

5

3

4

8

6

2

1

3

5

4

7

8

6

2

1

3

4

5

7

8

6

Pivot (4) is in place now. Time to QuickSort separate segments

2 1 3	5 7 8 6
1 2 3	5 7 6 8 5 6 7 8

FINAL RESULT

1

2

3

4

5

6

7

8

Coming Soon: Quick Sort Java Code

Top Java Strings Interview Questions

The favourite of the interview questions when it comes to Java. In my entire career I don't recall how many String questions have I asked and how many have I answered. It's like an ocean. The more you soak, the deeper you get.

This importance comes from the fact that Java designers too gave special significance to Strings. Strings are stored separately and plays and important roles in all programs. 

1. Where is String stored in Java?

String are considered special data type in Java. They stored StringPool which is a separate storage space on Java Heap.

2. What do we mean by "Spring is Immutable"?

All member variable data type is final. Hence String Object once created becomes immutable in Java. 

String literals are stored separately in a String Pool. Once a String is Created, say "javaonjava". Whenever a new variable needs "javaonjava" String, a new String is not created. The old one is referenced. This is what we mean by immutability. So String Object is not immutable, String itself is immutable.

Compare it with any User defined object. When that object is updated, content is re-written on the same memory space.

3. Is String a primitive Data Type?

No, String is not a primitive data type. String is a user defined data type. java.lang.String. 

Just like all other objects, Strings extend java.lang.Object. 

As we see in the String class, private final char value[]; stores the data of the String Object.

4. Is String in Java the same as in C?

No, In C, String is just a character array, terminated by null.

In Java String is a Class Object with multiple methods, like equals() to compare Strings, concat() to add two Strings, split() to split a String etc.

5. What does toString() method does?

toString() is an Object level method (java.lang.Object). It returns the String representation of any Object.

6. We see that String class is defined as final. Why?

The answer is the same, to make it immutable. As to Why, there are multiple reasons as to Why Java Designers made String final.

7. Can String be converted to int?

Yes. We have a special function parseInt() in Integer class for this purpose. Check the below code,

8. Can String be used with Switch/Case?

A serious drawback of Switch-Case was it just worked with expressions that evaluated to int (int, short, byte, char, Enum). Not anymore. With Java 7 it can take Strings too. Isn’t is awesome?

String fruit = "apple";

switch (fruit) {

case "orange":

9. How to compare two Strings?

There are multiple ways to compare Strings. But the one that we should follow is equals(). equals() checks if the data is equal. "==" just checks if String Objects are same or not.

10. What is String Pool in Java?

String Pool is a separate storage area on Heap Memory where String Objects are stored. Once a String is Created, say "javaonjava". Whenever a new variable needs "javaonjava" String, a new String is not created. The old one is referenced from String Pool

11. Why is char array preferred over String when it comes to saving password?

Strings as we now know are immutable. They are stored in String Pool and can't be erased till Garbage Collection kicks in. Hence application is susceptible to password leaks. Whereas in char[], each index can be set to null, when we want to erase the password.

12. What is intern() method used for?

In earlier versions of java, String created by new(), was not created in String Pool. intern() method, used to move it to String Pool.

13. Is String Thread safe?

Should be simple to answer by now. Since String is immutable, it cannot be modified. What is immutable is Thread Safe.

14. Differentiate between String/StringBuffer/StringBuilder.

String	immutable	thread safe
StringBuffer	mutable	thread safe
StringBuilder	mutable	not thread safe

Overloading main() in Java

A common fresher interview goes like, Can we overloading main() in Java?

It's a very tricky question on the face of it. But if we just recollect basics, it won't be too hard to answer.

Answer is Yes, we can very much do.

By default we use String args[] as the method argument for main(). We can have multiple mains with different arguments types.

Error Cases
1. main(String args[]) is missing