Binary Search Algorithm

Hello people…! In this post we will discuss one of the most commonly used search algorithm, the Binary Search. In a search algorithm, we are given an element and a collection or a set of elements. If the given element exists in the given set, we must return where it is located, or otherwise, if it does not exist, our algorithm must be able to say it does not exist.

Binary Search Conditions

The given set must obey the following rules if we want to apply binary search –

  1. All pairs of elements in the given set must be comparable. Mathematically, this is called a totally ordered set.
  2. The given set must be sorted, in ascending or descending order.

Algorithm

Let’s say we are looking for 7 in an array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. Binary search compares the middle element (here 5) and the element to be searched (here 7). So, 5 is less than 7. Binary search says, “Okay so 5 is less than 7, so don’t bother about the elements left of 5 because they are less than 5 anyway. It will never be equal to 7. Continue the same job with the right half instead!”. So, now we will look at the elements right of 5 only.

Now, let’s sat the middle element is 8. This time Binary Search says, “Elements right of 8 are more than 8, they will never be equal to 7, so neglect the elements right of 8, carry on with the elements left of 8.”

So if you analyse this carefully, we are cutting the size of elements we are supposed to look at by half for each step.

To implement this algorithm, we use 3 variables –

  • low – the lowest index of the searching range.
  • high – the highest index of the searching range.
  • mid – which is calculated by the formula below

binary-search-equation-1

 

 

Let us take the previous example array A = {1, 2, 3, 4, 5, 6, 7, 8, 9}. This time let us search for 9, and this time we will find the middle element using the formula above.

binary search

Initially, low = 0 and high = 8, which gives mid = 4. The middle element is not 9, but 5 which is less than 9, so we might find 9 only to the right of 5. So, we will assign low = mid + 1.

binary search

Now, low = 5 and high = 8, which gives mid = 6. Value 7 is less than 9, so we search in the right half of 7. We do this by low = mid + 1. (If we wanted to search in the left half, say for 6 example, we would do high = mid – 1).

binary search

Even now, the middle element is less than the required element, so we must search in the right half. So we do low = mid + 1.

binary search

Now our middle element is equal to what we want, so we return this index! So basically Binary Search goes up to when there’s only one element left. If that remaining element is not the element we want, then we can claim that the given set does not contain it.

Just imagine if we were searching for 10 in the above case, we would go up to the last element and find that even the last element is not equal to 10, so we return a -1 or some value which denotes that the element is not found.

The reason the formula for calculating the middle element isn’t a simple average is to avoid an integer overflow error. If we try to calculate,

binary-search-equation-2

when low and high are close to maximum values of an integer, they can cause an integer overflow. This is why we use the formula mentioned above.

Complexity

We make one comparison per iteration. So what is the worst case? Worst case occurs when the element is not present in the given set. Then we need to iterate until we have one element left. At each iteration, we reduce the range by half, so how many iterations should we perform to reach a single element?

Binary Search complexity

It is log2 N! So the worst case complexity of binary search is O(log2 N). The best case would be if the middle element of the set is itself is the value we want to find, then, the complexity would be O(1).

Code

It is a fairly simple algorithm to code. Please try to write the code by yourself. If you get stuck, you can use my code below as a reference.

CC++JavaPython
    
    
    
    

You can code the binary search using recursion too. But I prefer the iterative version as it does not have the recursion overhead and it will not produce a stack overflow error for large arrays.

Keep practicing! Happy Coding! 🙂

Dynamic Programming – Kadane’s Algorithm

Hello people..! In this post, we will look at a simple dynamic programming based algorithm which is the optimal solution to the Maximum Sum Subarray Problem. Try to focus on how the approach of dynamic programming is applied rather than just trying to understand the main algorithm. Now, let us define the problem.

Maximum Sum Subarray – Given an array A[1, 2, 3, … n]. We need to find that subarray A'[i, i + 1, i + 2, … j] where 1 ≤ i ≤ j ≤ n, where the sum of all the elements in A’ is maximum.

In simpler terms, we need to find that contiguous portion of an array where the sum is maximum.

Brute force approach

Brute force approach would be to look at all the sub-arrays starting with A[i] –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to n
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

This is algorithm is simple but it takes O(N²) time. The problem with this algorithm is that we are not able to save computation by using the solutions to the problems we already solved.

Let us re-write this algorithm slightly differently! Pay attention! Instead of starting from A[i] and going forward looking for maximum, this time, let us start at A[i] and go backward doing the same thing, finding the maximum. Here is the algorithm –

maxSum ← -∞

for i ← 1 to n
        sum ← 0
        for j ← i to 1   // decrement j
                sum += arr[j]

                maxSum ← max(maxSum, sum)

return maxSum

What we are doing is instead of looking at all the sub-arrays starting with A[i], we will look at all the sub-arrays ending with A[i]. This still runs in O(N²) time. So, what’s so special about this? Let is say we have an array A = {-1, 2, 3, -4}. The above algorithm would work on this algorithm something like this –

  • for i = 1 ⇒ max( sum(-1) )
  • for i = 2 ⇒ max ( sum(2), sum(2, -1) )
  • for i = 3 ⇒ max ( sum(3), sum(3, 2), sum(3, 2, -1) )
  • for i = 4 ⇒ max ( sum(-4), sum(-4, 3), sum(-4, 3, 2), sum(-4, 3, 2, -1) )

The solution would be the maximum of all iterations. If you notice, in each iteration, we are finding the maximum sum of all the sub-arrays ending with A[i]. Let us say we store this result in an array maxSum[i].

Kadane’s Algorithm states that,

kadane-algorithm-equation

In simple terms, it states that, the maximum sum sub-array ending with A[i], is either the element A[i] itself, or A[i] combined with the maximum sum sub-array ending with A[i – 1], whichever is the greater one.

Ponder upon this for a while. Using the above intuition we can re-write the above iterations as –

  • for i = 1 ⇒ max ( -1 ) ⇒ maxSum[1] = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum[2] = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum[3] = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum[4] = 1

And as before, the solution would be the maximum of all the elements in maxSum array. For the sake of simplicity, we used the array maxSum[], but we only need the previous iteration’s result to compute the current iteration result. So, we can make it a variable. So our iterations change into –

  • for i = 1 ⇒ maxSum = -1
  • for i = 2 ⇒ max ( 2, 2 + -1 ) ⇒ maxSum = 2
  • for i = 3 ⇒ max ( 3, 3 + 2 ) ⇒ maxSum = 5
  • for i = 4 ⇒ max ( -4, -4 + 5 ) ⇒ maxSum = 1

Why was the first iteration written like that? It is the trivial case. The maximum sum sub-array ending with the first element is the first element itself. And for each iteration, we could keep a global variable, say maxGlobalSum, which keeps track of maximum of all maxSum values.

If you have understood everything up to now, you should be able to code the algorithm very easily. If you didn’t understand, please give a couple more readings and try to code again. Feel free to ask your doubts in the comments!

If you are stuck with the algorithm, you can use my code as a reference –

CJava
    
    

This algorithm runs in O(N) time and uses O(1) space. I hope you have developed an idea of how to think in the dynamic programming way. To get a dynamic programming algorithm, we just have to analyse if where we are computing things which we have already computed and how can we reuse the existing solutions. Keep practising..! Happy Coding! 😀

Java Tutorials – Constructor and Overloading Methods

Hello, people..! In this post, we will explore some more aspects of object-oriented programming, which is overloading methods, but before that, I thought it is the right the time to tell you about what a constructor is.

Constructor

The constructor is a special method which is written in a class. This is called exactly once at the time of instantiating an object of that class. Why do we need a constructor anyway? A constructor is meant to have the code for initializing the instance variables or any such process which we wish to do before we start using the object. A constructor looks just like a method, with a few rules. The rules for writing a constructor are –

  1. It is a method with the same name as the class name.
  2. It does not have any return type. Not even void.

Now, keep those two rules in mind, as I show you what a constructor exactly looks like –

class Classroom {
    int capacity;
    
    // This is a constructor!
    //
    // 1. Same name as class name
    // 2. No return type
    public Classroom() {
        capacity = 35;
    }
}

That is a constructor. It is automatically called by the JVM when an object of that class is created. To demonstrate this, have a look at the code below –

class Classroom {
    int capacity;

    public Classroom() {
        System.out.println("Inside Classroom's Constructor...");
        capacity = 35;
    }
}

public class Test {
    public static void main(String[] args) {
        System.out.println("Inside main()...");
        Classroom obj1 = new Classroom();
        System.out.println("Creating another object...");
        Classroom obj2 = new Classroom();
        System.out.println("Done with main()...");
    }
}

The output of the given code is –

Inside main()...
Inside Classroom's Constructor...
Creating another object...
Inside Classroom's Constructor...
Done with main()...

I hope this makes the flow of execution clear. Feel free to comment if you have any doubts!

Constructor with Parameters

So, we’ve seen that a constructor pretty much resembles a method. But like methods, can it take arguments? Yes! We can mention parameters for a constructor just as we do for a method in java. These values must be passed at the time of creating the object. Have a look at the code below –

class Person {
    String name;
    int age;
    
    // A constructor with parameters
    public Person(String personName, int personAge) {
        name = personName;
        age = personAge;
    }
}

class Test {
    public static void main(String[] args) {
        // Providing the arguments while creating object
        Person p = new Person("Chloë Grace Moretz", 19);
    }
}

Overloading Methods in Java

Now let us look at the OOP feature of overloading methods in java. We will come back to the constructor in a minute! Now, imagine you wanted to create a utility class which has a lot of frequently used functions. Let’s say we wanted to create a utility class which has the method for returning the index of the maximum element in an array. So this is how you would normally do it –

class Utility {
    public int max(int[] arr) {
        if (arr == null || arr.length < 1) {
            return -1;
        }
        
        int index = 0;
        int max = arr[0];
        
        for (int i = 1; i < arr.length; ++i) { if (arr[i] > max) {
                max = arr[i];
            }
        }
        
        return index;
    }
}

This is fine, but it can only accept an array of integers, what if you needed to find the index of the maximum element in an array of doubles or long or short or any other data type? Would you create other method named “max2”, “max3”, “max4” and so on..? No, you would have to remember a lot of names. Here’s where overloading helps you! Overloading allows you to create two or more methods of the same name but different signatures. Now, recall from our discussion on Enums and Methods in Java. We defined method signature as, name of the method + the list of parameters. We want the method names to be the same, so we will only alter the list of parameters. Overloading needs no special syntax, it’s just as simple as writing another method with a few restrictions. Let us look at an example –

class Utility {
    public int max(int[] arr) {
        System.out.println("public int max(int[] arr)");
        
        if (arr == null || arr.length < 1) {
            return -1;
        }
        
        int index = 0;
        int max = arr[0];
        
        for (int i = 1; i < arr.length; ++i) { if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
    
    // Overloaded method max, to
    // accept an array of double
    public int max(double[] arr) {
        System.out.println("public int max(double[] arr)");
        
        if (arr == null || arr.length < 1) {
            return -1;
        }
        
        int index = 0;
        double max = arr[0];
        
        for (int i = 1; i < arr.length; ++i) { if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
    
    // Overloaded method max, to
    // accept an array of long
    public int max(long[] arr) {
        System.out.println("public int max(long[] arr)");
        
        if (arr == null || arr.length < 1) {
            return -1;
        }
        
        int index = 0;
        long max = arr[0];
        
        for (int i = 1; i < arr.length; ++i) { if (arr[i] > max) {
                max = arr[i];
                index = i;
            }
        }
        
        return index;
    }
}

class Test {
    public static void main(String[] args) {
        Utility obj = new Utility();
        
        int[] intArray = {1, 2, 3, 4, 5, 0, -1, -2};
        double[] doubleArray = {1.2, 2.3, 3.4, 4.5, 5.6, 6.7};
        long[] longArray = {1, 2, 3, 4, 5, 6, 124578};
        
        System.out.println(obj.max(intArray));
        System.out.println(obj.max(doubleArray));
        System.out.println(obj.max(longArray));
    }
}

Can you pause for a moment and guess what the output could be? The output of the code above is –

public int max(int[] arr)
4
public int max(double[] arr)
5
public int max(long[] arr)
6

So what happened here is that, based on the number of arguments passed (here 1) and on the basis of the data type of the arguments passed, Java decides for itself which is the best method to call. When we passed an array of doubles, the method which takes an array of doubles is called. If you can notice, we are not reducing the amount of code written, but it makes our job easy as we have to remember only one name, and based on the data type of the argument passed, the corresponding method is called. This is called Overloading methods. Some rules to keep in mind regarding overloading are –

  • We can overload methods only based on different data type of parameter or different number of parameters. Everything else is irrelevant.
  • So, we cannot overload methods based on return type, or access modifiers (public, private, etc.), or specifiers (static), or exception list.

Well, leave exception lists for now, we’ll look at it later. So based on these rules you could run into overloading problems. Given below are some examples of invalid overloads –

/* ===== ===== ===== ===== */
public void foo(int var) { }
public int foo(int var) { }


/* ===== ===== ===== ===== */
public static int foo(int var) { }
public int foo(int var) { }


/* ===== ===== ===== ===== */
public void foo(int var) { }
private void foo(int var) { }

Overloading is heavily used in the Java library. In fact, we’ve been using it right from our first hello world program! How? The println() method we use has a lot of overloaded methods. If you are working in NetBeans or any other IDE, you can see all these methods. This is how it looks in my NetBeans IDE – Overloading - Overloaded Methods of System.out.println()

Overloading Constructors

So we saw what a constructor was and we saw that it resembles a method in many aspects. So as we can overload methods, can we overload constructors too? Yes! How? It’s just like overloading methods, we just alter the number of parameters or change the data type of the parameters. Have a look at the example below to make things clear –

class Time {
    int hours, minutes, seconds;

    public Time(int hrs) {
        hours = hrs;
    }

    // Overloaded Constructor
    public Time(int hrs, int min) {
        hours = hrs;
        minutes = min;
    }
    
    // Overloaded Constructor
    public Time(int hrs, int min, int sec) {
        hours = hrs;
        minutes = min;
        seconds = sec;
    }
}

class Test {
    public static void main(String[] args) {
        Time t1 = new Time(10);
        Time t2 = new Time(10, 20);
        Time t3 = new Time(10, 20, 30);
        
        System.out.println(t1.hours);
        System.out.println(t1.minutes);
        System.out.println(t1.seconds);
        
        System.out.println(t2.hours);
        System.out.println(t2.minutes);
        System.out.println(t2.seconds);
        
        System.out.println(t3.hours);
        System.out.println(t3.minutes);
        System.out.println(t3.seconds);
    }
}

So that’s how we overload constructors on Java. Using overloaded versions of the constructor, we can initialize selected fields of the object while instantiation. The output of the code above is –

10
0
0
10
20
0
10
20
30

We have also used overloaded constructors before. The Scanner class has many overloaded versions of constructors. We can see it all in NetBeans IDE – Overloading - Overloaded Constructors in Scanner class While there are a lot more things to discuss about the constructor we won’t do it in this post as the requires the knowledge of some other concepts. So, if all I explained above made sense to you, then I will definitely have happy tears! 😛

Order of Preference in Overloading

This is a very advanced concept. Beginners can skip this, but do come back again because this is very interesting! Now we know that an integer value is a match to long data type, as well as for Integer class (for those who know it). So, if all these appear in the form of different overloads, which method would be called? What is the order which Java uses to choose an overloaded method if all the methods are actually a match to the argument provided? Well, let’s say there’s a function named “foo” which is provided with 2 integers, then the order which Java uses is –

Exact Match by Data Type
public void foo(int i, int j) {}
A Larger Primitive Data Type
public void foo(long i, long j) {}
Autoboxed Type
public void foo(Integer i, Integer j) {}
Varargs
public void foo(int... args) {}

To better understand this concept take the code below and run it on your PC –

class OverloadingOrder {
    public void foo(int i, int j) {
        System.out.println("public void foo(int i, int j)");
    }
    
    public void foo(long i, long j) {
        System.out.println("public void foo(long i, long j)");
    }
    
    public void foo(Integer i, Integer j) {
        System.out.println("public void foo(Integer i, Integer j)");
    }
    
    public void foo(int... args) {
        System.out.println("public void foo(int... args)");
    }
}

class Test {
    public static void main(String[] args) {
        OverloadingOrder obj = new OverloadingOrder();
        
        obj.foo(1, 1);
    }
}

Now, try commenting out a few versions of the overloads and observe which function is called. Try it for a few minutes and I’m sure you will understand it! You might think Java follows the order which you write it in the class, but that is irrelevant. Now another thing to note here is that Java will only do at most one implicit conversion while finding the right overloaded match. Take a look at the code below –

class OverloadingOrder {
    public void foo(Double f) {
        System.out.println("public void foo(Double f)");
    }
}

class Test {
    public static void main(String[] args) {
        OverloadingOrder obj = new OverloadingOrder();
        
        obj.foo(1f);    // Compilation error
    }
}

This gives a compilation error saying that Java wasn’t able to find a suitable overloaded method. This is because conversion from float to double value is one implicit conversion but that’s the end of it. Java will not perform another implicit conversion from double to Double. Try such examples in your PC. Try the same thing with int and Long, short and Integer, and so on. I’m sure you’ll get the hang of it after a few tries. 🙂 The last concept I want to discuss in overloading is, overloading in the context of variable number of arguments. An array of integers is a match to both the overloaded methods below –

public void count(int... args) { }
public void count(int[] arr) { }

So, which one is called?? It gives a compilation error! Java cannot differentiate between those two. Of course, the way we normally call those methods is different, but still, Java doesn’t take risks as we could pass an array and wreak havoc! 😛 … So that is a nice little thing to remember. I hope my post gave you a fair understanding of what constructors are and what overloading is. If you have any doubts, feel free to comment them! Keep practicing! Happy Coding!! 😀

Encapsulation in Java

Hello, people..! Now we are going to look at the most basic and the first major topic in Object Oriented Programming, Encapsulation. For those who don’t know OOP, it is very important that you spend a lot of time trying to understand these concepts. Because once you learn these concepts, it will be exactly the same in any other OOP language (like C++, C#, etc.), only the syntax changes.

Code without Encapsulation

Let us first understand what happens when we don’t follow encapsulation. Let’s say you created the Person class where all the instance variables were public. The code would look like –

class Person {
    public String name;
    public int age;
}

Now, since it was public, somebody used it in this way in his main() method –

public static void main(String[] args) {
    Person p = new Person();

    p.name = "Vamsi Sangam";
    p.age = -1;
}

Okay, so doing that is legal. Neither the compiler nor the runtime complaints anything about it. But we all know that it’s not sane, right? Seriously, some values can’t be negative, like age, or length, or size etc. It’s like we created this class which everybody is using… Which we are happy about… But they can misuse it, or do stuff not meant for that class. So, we don’t have control.

Encapsulation

So how do get control over things? By implementing encapsulation. So, what’s encapsulation really? It is a set of rules, or a protocol, which we must follow to get more control over our data. Now, what are those rules which we must follow? They are –

  1. Keep instance variables private.
  2. Make public accessor methods.

So, let’s look at it one-by-one. Firstly, we must keep the instance variables private. What does that mean? Well, we just have to write “private” in the place of  “public” before we write the data type of our instance variable. That restricts the scope of the instance variable. Now, the instance variable has scope only inside the class. It cannot be accessed by making an object and referencing it. So, if we implement our rule 1 to Person class, it would look like –

class Person {
    private String name;
    private int age;
}

So, if you tried to use this class from another class’ main() method, and try to access those variables, it will give you a compilation error, saying “age has private access in Person”. The code is –

class Person {
    private String name;
    private int age;
}

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person();
        
        p.age = -1;    // error
    }
}

Great! So it looks like things went from bad to worse! We can’t even use those variables. Well, just wait till we implement the second rule. 😉

The second rules ask us to implement accessor methods. As the name suggests, accessor methods, are meant to access the variables which were marked private. These are also called Getter and Setter methods, or sometimes called as Mutator methods. Oracle thought the name “mutate” sounds bad, so we’ll stick to Getter and Setter methods. So, we will implement Getter and Setter methods for our Person class. As the name suggests the Getter method gets the value of the variable and the Setter method sets the variable to some value. The Person class with Getter and Setter methods would look like –

class Person {
    private String name;
    private int age;
    
    // Getter method for variable name
    public String getName() {
        return name;
    }
    
    // Setter method for variable name
    public void setName(String newName) {
        name = newName;
    }
    
    // Getter method for variable age
    public int getAge() {
        return age;
    }
    
    // Setter method for variable age
    public void setAge(int newAge) {
        age = newAge;
    }
}

As you can see that is the format in which we write the getter and setter methods for a variable. What you write inside the function is your wish, but the access modifier “public”, return type, name, or arguments must be in that format. We’ll talk a little about the naming conventions in a few minutes.
Well, you could ask, what’s changed, you could still do the same cruel stuff we did above to your Person class! 😛 Well, look closely, things have changed! You can do the validation stuff in the setter method of ‘age’ variable. To avoid negative values you could do something like –

// Setter method for variable age
public void setAge(int newAge) {
    if (newAge > 0) {
        age = newAge;
    }
}

So, if the input is a valid one you set the ‘age’ variable to the new value, otherwise you ignore. Not just this, you can do any amount of validation you want. You could keep an upper cap of 125 years or anything like that. So you have complete control. Lastly, you would use the encapsulated class like this –

public static void main(String[] args) {
    Person p = new Person();

    p.setName("Vamsi Sangam");
    p.setAge(-1);   // Ignored, so still 0
    p.setAge(19);
}

You can print the values of the variables using the getter methods if you want to. 🙂

JavaBeans Naming Convention

JavaBeans is a standard set by Oracle. It defines a few rules. We will only concern ourselves with the rules regarding the naming of getter and setter methods, commonly known as JavaBeans Naming Convention. It defines the naming conventions we must follow while naming the getter and setter methods. All classes in the Java library follow this convention strictly. JavaBeans calls an instance variables as a “property”. So the rules are –

Rule Example
Properties are private.
private int age;
private boolean happy;
private int numberOfChildren;
Getter methods begin with is if the property is boolean.
public boolean isHappy() {
    return happy;
}
Setter methods begin with set.
public void setAge(int newAge) {
    age = newAge;
}
The method name must have a prefix of set/get/is, followed by the first letter of the property in uppercase, followed by the rest of the property name
public int getNumberOfChildren() {
    return numberOfChildren;
}

Well, that was the convention rules. The first rule isn’t a naming rule, but it’s a part of JavaBeans so I saw it fit to keep it there.

Encapsulation with Mutable Classes

This is a little advanced topic in Encapsulation. Feel free to skip this part if you are new to OOP. But do check this later because it is an important pitfall! Now, mutable classes are those classes whose data can be changed after the object is created. Example, we saw that String objects are not mutable, whereas the objects of StringBuilder are. We must be careful when encapsulating mutable objects. Check out the class below. Do you think it is perfectly encapsulated?

class Person {
    private StringBuilder name;
    
    public Person(StringBuilder name) {
        this.name = name;
    }
    
    // Getter method for variable name
    public StringBuilder getName() {
        return name;
    }
}

So, let’s say we have this class. We don’t have a setter here, but that’s fine, the class is still considered to be encapsulated (for now :P). So, it pretty much looks like we can’t change the value of the variable ‘name’ after we initialize it with a constructor. Now, check this out –

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person(new StringBuilder("Vamsi Sangam"));

        // variable name will hold Vamsi Sangam
        System.out.println(p.getName());
        
        // Storing the return value
        StringBuilder var = p.getName();
        
        // Changing the object returned
        var.append("! Are you confused?");
        
        // Printing the object inside encapsulated class
        System.out.println(p.getName());
        // Prints "Vamsi Sangam! Are you confused?"
    }
}

We’ve somehow managed to change the object held by the encapsulated field which doesn’t even have a getter method! This happens because, the variable name, is a reference to an object. In the getter method, we are returning the same object which name is pointing to. So if you return the reference to that object, you can actually manipulate it as you want, because it’s a mutable object. Changes made to the object returned by the getter method will reflect in the object held by name because they are exactly the same object.

I hope this made sense. Please go through what I said once more if you didn’t understand it. It’s a fairly simple concept. So what do we do in such a situation? We clone that property and return the clone. Cloning means creating a new object of the same data type as the property which has the same content.

So, a proper getter method for name would be –

class Person {
    private StringBuilder name;
    
    public Person(StringBuilder name) {
        this.name = name;
    }
    
    // Getter method for variable name
    public StringBuilder getName() {
        return new StringBuilder(name);
    }
}

class TestPerson {
    public static void main(String[] args) {
        Person p = new Person(new StringBuilder("Vamsi Sangam"));

        // variable name will hold Vamsi Sangam
        System.out.println(p.getName());
        
        // Storing the return value
        StringBuilder var = p.getName();
        
        // Changing the object returned
        var.append("! Are you confused?");
        
        // Printing the object inside encapsulated class
        System.out.println(p.getName());
        // Prints "Vamsi Sangam"
    }
}

All this nuisance is because the property is of a mutable class. If it were something like a String, we wouldn’t have this problem. Because even if two references point to the same object, we cannot change the content of that object they are pointing to.

So, that was Encapsulation! It is a matter of 2 simple rules. Easy! Isn’t it..?! Keep practicing… Happy Coding..!! 😀

Trie Tree Practise – SPOJ – DICT

Hello people..! In this post we will talk about solving another competitive programming question based on trie tree. I will take up the SPOJ problem – DICT. This is a little harder than the previous trie tree practise problem, PHONELST. Now, read the problem statement carefully a couple of times. Just so that you don’t need to open SPOJ in another tab, I have posted the problem statement below –

Problem Statement
Input Specification
Output Specification
Sample Input
Sample Output

Problem in terms of Trie Tree

Firstly, we will insert the N words into a trie tree. Then, for each K prefix words –

  • We will traverse the trie tree for this word.
  • If it exists, we will lexicographically print the trie tree, with that node as the root. And obviously, we add the prefix to whatever we will print.
  • If the word doesn’t exist at all, that is, while traversing, we would reach a dead-end (no children) node before the prefix word is fully processed, we will simply return from our traversal and print “No match.”.

So, what all do you need to solve this?

  • Trie Tree insertion method.
  • Trie Tree inorder traversal method (lexicographical print)

We can discard any other methods such as delete. We will need another method for searching whether a given word is present in the trie tree or not, in O(L) time, where L is the length of the word. So, take your implementation of trie tree and get it ready for solving the question by making these changes.

searchWord() Method

This is a simple trie tree traversal method, where we traverse the trie tree based on a given word. We look at each character of the word and go to the corresponding edge, in the trie tree. If there is no edge, we return null. If we have reached the end successfully, we return the node where the word ends. Try to code this procedure, you can refer to my code if you are stuck.

C++
struct node * searchWord(struct node * TreeNode, char * word)
{
    while (*word != '\0') {		// while there are alphabets to process
        if (TreeNode->children[*word - CASE] != NULL) {
        	// there is an edge corresponding to the alphabet
            TreeNode = TreeNode->children[*word - CASE];
            ++word;
        } else {
        	// there is no edge corresponding to the alphabet
            break;
        }
    }
 
    if (*word == '\0') {
    	// the word was completely processed
        return TreeNode;
    } else {
    	// word is not there in trie tree
        return NULL;
    }
}

lexicographPrint() Method

This method will have very minor changes from your original method. According to our intuition, we will call this method based on the output of the searchWord method. If it is null, then it is “No match.”. If it is not null, then we begin the lexicographPrint from that node.
This method will carry an extra parameter, which will be the prefix word. Everytime we hit a leaf node, we first print the prefix word and then the remaining word traversed in this method.
Example, in the sample test case, the prefix word was “set”, so, the searchWord would return us, the location of the T node in S → E → T traversal. Then, we begin our lexicographPrint, and when we hit the end of “setter” word, we will print the “set” prefix, and the “ter” word which we gained from the lexicographPrint method.
Try to code these modifications in your code, you can refer to my code if you are stuck.

C++
 
void lexicographPrint(struct Node * trieTree, vector<char> word, char * prefix)
{
    int i;
    bool noChild = true;
 
	if (trieTree->wordEnding && word.size() != 0) {
        vector<char>::iterator itr = word.begin();
		
		printf("%s", prefix);	//	print the prefix
        
		while (itr != word.end()) {
			// print the rest of the word
            printf("%c", *itr);
            ++itr;
        }
        
        printf("\n");
    } 
 
    for (i = 0; i < ALPHABETS; ++i) {
        if (trieTree->children[i] != NULL) {
            noChild = false;
            word.push_back(CASE + i);
            lexicographPrint(trieTree->children[i], word, prefix);
            word.pop_back();
        }
    }
 
    word.pop_back();
}

Putting the pieces together

Now combine your modules and prepare your main function as per the problem statement. You can refer to my code if you are stuck.

    

Word of Caution –

  • The output in the case of a mismatch is “No match.”, not “No match”.
  • The time limits are pretty tight, so your methods should be tidy.

I hope that you were able to solve this problem using a trie tree. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 🙂

Trie Tree Practise – SPOJ – PHONELST

Hello people..! In this post I will show you how to get started with solving Trie Tree based questions in competitive programming. Learning a data structure is different from solving competitive coding questions based on that data structure. In this post, I take up a very simple question so that your confidence is boosted.
We will look at the SPOJ problem – Phone List. It is a very straight forward problem. Just so that you don’t need to go to SPOJ in a new tab, I’m putting the problem statement here.

Problem Statement

Phone List Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let’s say the phone catalogue listed these numbers:

• Emergency 911

• Alice 97 625 999

• Bob 91 12 54 26

In this case, it’s not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob’s phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 <= t <= 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 <= n <= 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output “YES” if the list is consistent, or “NO” otherwise.

The Problem in terms of Trie Tree

We are supposed to check if any word is a prefix of any other or not. Now, there might be a hundred ways to solve this problem, but we will do this using a trie tree so that we can get confident in using the data structure, and so that we can attempt tougher ones based on a trie tree. All throughout my explanation, I will be referring to the implementation in my post on Trie Tree.
What we will do to solve this problem is that, we will insert the words into the trie tree one-by-one, and we will check for the prefix word criteria as we are inserting. Now, there are 2 cases.

Case – 1 – Prefix word is already inserted

This is the sample test case. Consider this test case –

Input
face
facebook

So, what I said we will do is that, we will be inserting the words one-by-one. So, when we insert the word “face”, no problems occur. But while inserting the word “facebook”, we would travel to the nodes F → A → C → E. And at the node E, we would have some indication that this node is a leaf node, that is, some word ends here. In my implementation, this can be indicated by –

if (temp->occurrences.size() == 0) {
	// not a leaf node
} else {
	// a leaf node, thus this is
	// the end of the prefix word
}

If we encounter this situation, we know that the result will be NO.

Case 2 – Prefix word is about to be inserted

This is just the opposite of the previous case, consider the test case –

Input
facebook
face

We won’t have any issues while inserting “facebook”. But when inserting “face”, we traverse F → A → C → E. And in the end of insertion, we see that there is a child node to the node E. Which means that there is a bigger word which ends somewhere deep down the trie tree. Which means that we just inserted the prefix word. We could check this by traversing the children array –

for (i = 0; i < ALPHABETS; ++i) {
	if (temp->children[i] != NULL) {
		// The newly inserted word is
		// prefix to another word
	}
}

In this case too, the answer would be a NO. For every other case, the answer would be a YES.

So, try to code this problem. Take your code of the trie tree, remove the unnecessary things first, like the delete function or print function or any others which we won’t need. As fas as I know, the insert function is all that you will need. And try to make the changes required for the test cases.
Your insert function could return a true or a false, depending on whether the insertion encountered a prefix test case or not. Take time to think about it and try to code it. If you get stuck, you can refer to my code below –

    

A word of caution –

  • Even if you did encounter a prefix word very early, don’t break out of the input, as you will disturb the input for the next test case.

I hope that you were able to solve this problem using a trie tree. It is simple and a prefect problem to start your trie tree streak in competitive coding. Feel free to comment if you have any doubts. If you have any bugs in your code, I’d be glad to help, but don’t comment your entire code in the comment, please leave Ideone or PasteBin links, or if you don’t want to show your code publicly, you can fill up the response form below to mail your code to me. I will respond as soon as I can. Keep practising… Happy Coding…! 😀

Java Tutorials – Classes and Objects

Hello people..! So we finally come to the most famous part of Java, the Object Oriented Programming (OOP). Although I introduce OOP in this post, this post mainly to get you started with the notion of classes and objects. But, before we start our discussion on OOP, let us see why the modern world is so caught up with this programming paradigm. OOP offers you three important things –

  1. More Control – A program can be roughly divided into data (the variables) and code (the functions or the set of instructions). We know that the code performs some operations over the data. If we can somehow encapsulate the data and code such that certain data can be associated with only a certain code and no other code is allowed to touch the data directly, then we can easily find out which code is faulty. This gives us more control over the code… Wait… Not getting it..? 😛 … Let’s take up some sketches to make it clear…!
    Code and Data in OOP

    Code and Data in OOP

    Well, one obvious question is that why should you bother about all this..? You needn’t bother about having more control over your code if you are about to write 50 or 200 lines of code. But software which IT companies build, span up to millions of lines of code..! Yes, millions..! So, you need to have more control. And also because, the code is written by thousands of people. Imagine if you were to monitor 5 people. Would you use CCTV cameras..? No..! But if you were to monitor 1000 people..! Yes..! The same goes here.

  2. Re-usability – The Object Orientation feature Inheritance, allows us to reuse the existing code. This is a boon to companies building massive applications. If you can re-use the code properly, we can save a lot of time.
  3. Remember Less – The Object Orientation feature Polymorphism, enables us to remember less, thus making us more productive.

You will neither understand what they are, nor how they really work at this early stage. But we will learn them all very soon..! In this post, we will talk about the Java construct where all the OOP starts, the class.

The class

Class is a user defined data type. Think of it as a struct in C. Recall struct in C –

  • It was a user defined data type.
  • We could have any number of variables in a struct.

A class is also somewhat like that, only that it is much much more enhanced. Before we go ahead and learn the extra things, let us look at the syntax of a class with the features we are already familiar with.

// Declare using
// 'class' keyword
class Person {
    // These are variables or
    // attributes of the class
    String name;
    String phone;
    String email;
    int age;
}

That is the syntax for creating a class. We generally don’t put an ending semicolon after the class declaration (like as we do with struct in C ), but it is ok if you do.

Now, we can’t have functions in a C struct. But we can have functions (methods) in a class. If so, when are they called? We’ll look at it later. Right now, let’s just focus on the syntax for writing methods in a class –

// Declare using
// 'class' keyword
class Person {
    // Instance Variables
    String name;
    String phone;
    String email;
    int age;

    // The usual syntax -
    // return-type function-name(parameters) { // code }
    void printDetials() {
        // Instance Variables are
        // accessible to every method
        System.out.println("Name - " + name);
        System.out.println("Phone - " + phone);
        System.out.println("Email - " + email);
        System.out.println("Age - " + age);
    }
}

Using that syntax, you can write any number of methods in a class. Now, I have used a new term, Instance Variables. We will discuss later what this actually means. Just know that we can access them from the methods.

Entity

Now we can’t create a class as we like. A class in your code generally represent an entity in the real world (not necessarily living). We created a class person, and we know that a person exists in the real world. Like that, your class must represent something in the real world, or it must represent an entity. So, what do we do in a class…? In a class, we describe what the entity must do..! Every entity has two things –

  • Attributes (Instance Variables) – Just like every Person has a name and age, every entity is supposed to have some attributes or properties.
  • Behavior (Methods) – Every Person would perform some action, say, walk, sneeze, laugh, etc., in code, they are written as methods.

We must specify these. Remember, we are still specifying..! That is, we are still describing what your entity does. Which kinda means that we are still designing the entity, we haven’t yet created an instance of it.

Examples

Let us take up some real life entities and try to represent them as classes so that we can understand, what we should write as attributes and methods. Let us first take a very simple example, a ball.

class Ball
{
    // Attributes
    int innerRadius, outerRadius, weight;

    // Actions
    void bounce()
    {
        // some code
    }
}

There isn’t much in a ball, so this is fine. Now, let’s look at something a little more complex.

class Animal
{
    // Attributes
    int height, weight, color;

    // Actions
    void eat()
    {
        System.out.println("Animal is eating...");
    }

    void sleep()
    {
        System.out.println("Animal is sleeping...");
    }

    void walk()
    {
        System.out.println("Animal is walking...");
    }
}

Now that’s a small animal of the wild..! How about something even more complex?

class SavingsAccount {
    // Attributes
    String accountNumber;
    int balance;
    double interestRate = 10.5;

    // Actions
    void withdraw(int fund)
    {
        if (balance - fund >= 0) {
            balance -= fund;
        }
    }

    void deposit(int fund) {
        if (fund > 0) {
            balance += fund;
        }
    }

    void addInterest() {
        balance += (balance * interestRate) / 100;
    }
}

All these were just to give you a hint on how we write classes. These entities can have a lot more attributes and actions. I have mentioned only a few so that I can keep it simple. Try adding more attributes and actions..! 😉

Objects

So far, what we have seen is a class. Class is as we discussed, is a data type. We don’t store values or data in a data type, we store data in objects!  An object is a live instance or occurrence of a class. Memory is allocated when we create an object. We create an object using the new keyword. When we create an object using the new keyword, a chunk of memory is allocated and a reference to that chunk of memory is returned.

How big is this chunk of memory. Well, let’s just say that it is big enough to accommodate all the attributes of the class. Before we go to the syntax of creating an object, let’s look at a couple of definitions.

Object Reference – It is a variable which holds the address or reference to the object. We access the elements of an object via the Object Reference. We use the de-referencing, or dot operator ‘.’ to access the members of the object. An Object Reference has a data type. It has the same data type as the class whose object we want the object reference to point to.

Object – It is one large chunk of memory dynamically allocated by using the new keyword. It is the live instance of a class. It has memory for variables in it. They are the variables which are specified in the class definition. Object is a reference type. So they must be accessed by a pointer sort of thing, which in Java is an Object Reference.

Now, these definitions will make more sense once we go through some examples. This is how we create an object of Ball class –

// Creating an object reference of type Ball
Ball oref;
        
// Creating an object and assigning
// the reference of the object
oref = new Ball();

Remember, Ball was a class. So it is a data type (user-defined). Visually, it looks something like –

Object and Object Reference

Object and Object Reference

So, the object reference points to the object. In the diagram, the object is having only 3 variables, that is because we had 3 variables in the class definition. If you change that, the object also changes. Class is the blueprint and Object is the live occurrence. Any changes made to the blueprint is reflected in the model.

We can access the members of the object via the object reference –

// We access the attributes by the object reference
System.out.println(oref.innerRadius);
System.out.println(oref.outerRadius);
System.out.println(oref.weight);

// We also access the Actions / Methods
// by the object reference
oref.bounce();

So, if we put all the pieces together –

class Ball
{
    // Attributes
    int innerRadius, outerRadius, weight;

    // Actions
    void bounce()
    {
        System.out.println("Bounce..!");
    }
}

class TestBall
{
    public static void main(String[] args)
    {
        // Creating an object reference of type Ball
        Ball oref;
        
        // Creating an object and assigning
        // the reference of the object
        oref = new Ball();
        
        // We access the attributes by the object reference
        System.out.println(oref.innerRadius);
        System.out.println(oref.outerRadius);
        System.out.println(oref.weight);

        // We also access the Actions / Methods
        // by the object reference
        oref.bounce();
    }
}

The output of that piece of code is –

0
0
0
Bounce..!

So, this was to get you started with classes and objects. We will learn a lot more about classes and objects as we keep learning more and more of Java. Programmers who never dealt with OOP before will find this hard to digest. But trust me, it is worth the pain..! Keep practising… Happy Coding..! 😀

Java Tutorials – Enum and Methods in Java

Hello people..! This is a new post in Java Tutorials – Enum and Methods in Java. In this post I will talk about enum and methods (that is, functions) in Java. The full potential and usage of these constructs will be seen when we start creating classes. But you’ve gotta start somewhere..! So this post is to get you started with these constructs.

enum in Java

“enum” is the short form for “enumeration”… Here, an enum will be an enumeration of constants. In enum, what we do is –

  • Declare an enum. Which involves declaring a set of constants.
  • We create a variable of the enum type, which can hold any one value among the declared constants for that enum… Nothing else…!

Why would anyone use an enum..? … Well, it can look insignificant at most times, but there is a wide scope where we can use them…!

Let’s take the men’s T-shirt sizes for example. We all know that the sizes have fixed letters associated with them. We don’t have to bother ourselves about all of them… Let’s just pick a few –

  • S – Small
  • M – Medium
  • L – Large
  • XL – Extra Large

Now, if you wanted to create a variable to store the T-shirt sizes… Which data types would you choose..? And moreover, how will you ensure that the variable will have exactly anyone of these predefined values..? That’s where an enum comes into the picture.

Let’s look at a simple code which uses an enum

class Enumerations
{
	// Declaring an enum
	// Give the set of constants
	enum TShirtSizes {S, M, L, XL};

	public static void main (String[] args)
	{
		// Creating a variable of the enum
		TShirtSizes myShirt;

		// Assigning a value to the variable
		// Must assign a value among the
		// declared value
		myShirt = TShirtSizes.L;
		// Access the declared value
		// using dot operator 

		System.out.println(myShirt);	// L
	}
}

This is how we use an enum. As you can see, there are 3 steps involved in using an enum in Java –

  1. Declaring – Declare an enumeration using the enum keyword. Provide the set of constants in curly braces. One important thing is that, enum must be declared outside a method. They can be declared even outside a class, but not locally (inside a method)..!
    enum TShirtSizes {S, M, L, XL};
    
  2. Creating a variable – We create the variable using the name of the enum declared. It acts like a data type, similar to a struct.
    TShirtSizes myShirt;
    
  3. Assigning – Assign a value to the variable created. We must always assign a value among the constants declared before. We access these values by using the dot operator on the enum name. Assignment of any other value gives a compilation error.
    myShirt = TShirtSizes.L;
    

Those were about the legal declarations. Let’s look at some illegal declarations. The whole class is given as you could make a mistake at anyone of the steps –

class EnumGoneWrong
{
	enum TShirtSizes = {S, M, L, XL};
	// No '='. This is not an array!

	public static void main (String[] args)
	{
		TShirtSizes myShirt;

		myShirt = TShirtSizes.L;

		System.out.println(myShirt);
	}
}

// Another
class EnumGoneWrong
{
	enum TShirtSizes {S, M, L, XL};

	public static void main (String[] args)
	{
		TShirtSizes myShirt;

		myShirt = TShirtSizes.XXL;
		// XXL wasn't declared..!

		System.out.println(myShirt);
	}
}

// Another
class EnumGoneWrong
{
	enum TShirtSizes {S, M, L, XL};

	public static void main (String[] args)
	{
		TShirtSizes myShirt;

		myShirt = M;
		// It is TShirtSizes.M !

		System.out.println(myShirt);
	}
}

// Another
class EnumGoneWrong
{
	enum TShirtSizes {S, M, L, XL};

	public static void main (String[] args)
	{
		TShirtSizes myShirt;

		myShirt = 'M';
		// It is TShirtSizes.M !

		System.out.println(myShirt);
	}
}

// Another
class EnumGoneWrong
{
	enum TShirtSizes {S, M, L, XL};

	public static void main (String[] args)
	{
		TShirtSizes myShirt;

		myShirt = 1;
		// Cannot take any value
		// other than those declared !

		System.out.println(myShirt);
	}
}

Methods in Java

Functions in Java are actually called “methods”. That’s the terminology we are supposed to use here. In my previous posts, I have used the word “functions” more than “methods” so that you don’t feel too alien. But from now on, we use the term “methods”.

Methods as you know it, are subroutines that can be called from a method, where the control passes to the called method, and comes back to the caller method after execution of the subroutine, with or without a return type.

We will use a lot of methods when we start creating our own classes…. And by “a lot”, I mean really A LOT..! But for now, Let’s just learn how to call a method from the main() method.

class Methods
{
	public static void main (String[] args)
	{
		printMessage("This was printed from a ");
	}

	static void printMessage(String msg)
	{
		System.out.println(msg + "method !");
	}
}

Now the VERY IMPORTANT thing here is that, if you want to call any method from the main() method, it must be marked static, otherwise it is a compilation error..! Not just main() method, any static method can only call another static method..! So the following code gives a compilation error –

class Methods
{
	public static void main (String[] args)
	{
		printMessage("This was printed from a ");
	}

	static void printMessage(String msg)
	{
		printMessageToBob(msg + "method ");
	}

	void printMessageToBob(String msg)
	{
		System.out.println(msg + "Bob !");
	}
}

It is because we are calling a non-static method from a static method. This code gives compilation error which is pretty famous among the beginners –

Main.java:17: error: non-static method printMessageToBob(String) cannot be referenced from a static context
printMessageToBob(msg + "method ");
^
1 error

It is famous among the beginners because they don’t know what static really means. In Java, static means a lot. We will have a detailed discussion later. But you must remember this one rule.

Components in a Method’s Declaration

Methods in Java have six components. They are –

  1. Access Modifier – The access modifier define the scope of the method, that is, from where this method can/cannot be accessed. Access modifiers is a separate topic that we will see later.
  2. Return Type – This is the data type of the return value. It is void if the method does not return anything.
  3. Name – The name of the method.
  4. List of Parameters – Then comes the list of parameters enclosed in parenthesis. The data type of the parameter should be mentioned first.
  5. List of Exceptions – The method must declare unhandled exceptions using throws keyword. We will discuss this later.
  6. Body of the Method – The actual code of the method. Must be enclosed in curly braces.

I would like to introduce another important term –

Method Signature – It is the name of  the method + the list of parameters. It does not include the return type.

Method Signature will be a very frequent term in the upcoming discussions. So, do remember this term well..! As I said before, we will confine ourselves only on calling methods from the main() method. So, you needn’t be bothered about Access Modifiers or List of Exceptions for now.
Some examples of methods, their signatures, and whether they can be called from the main() method or not –

// Method
public static void main(String[] args) {
    // main() method
}

// Signature -
// main(String[] args)

// Method
void print() {
    // Can't be called from main()
}

// Signature -
// Print()

// Method
static String getMessage() {
    // Can be called from main()
    return "Hello";
}

// Signature -
// getMessage()

// Method
static void sort(int[] arr) {
    // Can be called from main()
}

// Signature -
// sort(int[] arr)

// Method
int distance(int x1, int y1, int x2, int y2) {
    // can't be called from main()
    return 0;
}

// Signature -
// distance(int x1, int y1, int x2, int y2)

// Method
public static void main(String args) {
    // Can be called from main()
    // But this is not "the" main()..!
}

// Signature -
// main(String args)

The examples are self-explanatory. But do feel free to comment if you have any doubts..! 🙂

Passing Variables of Primitive Data Types

The primitive data types are always passed by value in Java. There are no pointers in Java. So… You cannot exactly create a swap function in Java..! I know you are a genius, but still, I want to remind you that this function does not swap the elements –

public class SwapSwapSwap {

    public static void main(String[] args) {
        int x = 10;
        int y = 20;
        
        swap(x, y);
        
        System.out.println("x = " + x);     // 10
        System.out.println("y = " + y);     // 20
    }
    
    static void swap(int x, int y) {
        int temp = x;
        x = y;
        y = temp;
    }
    
}

Passing Objects

The objects are passed by their object references, so “in-effect”, they are passed by reference. But passing an object doesn’t exactly mean that we can change them in the method called. That depends on whether the object passed is mutable or not. For example, we know that String objects are immutable, whereas objects of StringBuilder are mutable. So look at the following example –

public class PassingAnObject {

    public static void main(String[] args) {
        String str = "String Object";
        StringBuilder strb 
            = new StringBuilder("String Builder Object");
        
        changeString(str);
        changeStringBuilder(strb);
        
        System.out.println(str);
        // Gives - String Object
        System.out.println(strb);
        // Gives - String Builder Object Changed..!
    }
    
    static void changeString(String str) {
        str = str.concat(" Changed..!");
    }
    
    static void changeStringBuilder(StringBuilder strb) {
        strb.append(" Changed..!");
    }
    
}

Strings are real tricky in this aspect. When we pass a String Object, initially, it does point to the object of the main() method, but once, we change it, we get a whole new object. This is not the case with objects of StringBuilder…! Objects of StringBuilder are mutable, so when we pass the object reference, the actual object can be modified by the called method, because inside the method, it’s just another reference pointing to the same StringBuilder object created in the main() method.
You may not understand this… That’s ok..! 🙂 … But remember this that whether the object can me modified depends on whether the object is immutable or not.

Naming Conventions

  • enums – As discussed, enum is a set of constants. According to the Oracle Code Convention, constants must be named in all caps. Such as –
    enum TShirtSizes {SMALL, MEDIUM, LARGE, EXTRALARGE};
    
  • Methods – Methods in Java follow the Camel Case Convention. Here, the first word is written in small letters and the rest of the words following are capitalized. Such as –
    int binarySearch(int[] arr, int key) {
        // code
    }
    
    String toString(int[] arr) {
        // code
    }
    
    char charAt(int index) {
        // code
    }
    
    int lastIndexOf(String str) {
        // code
    }
    

    I don’t know each and every method in the Java Library, but all the methods I have seen so far strictly follow the naming convention. I think Java library is the best example for everything we study in Java.

More about an enum

This is an advanced discussion… So beginners can feel free to skip this section… 🙂 … There’s a lot more to an enum in Java. enums are like really special (or strange 😛 ) classes. As I told before, enums can be declared outside a class –

enum TShirtSizes {
    S, M, L, XL;
}

public class Enumerations {

    public static void main(String[] args) {
        // code
    }

}

Being able to declare it outside a class doesn’t make it a special kind of class… Then what..? … We can have constructors, methods and variables inside an enum..!
Take our example of the enum TShirtSizes… Well, saying S, M, L, is good… But wouldn’t it be nice if we had data about their actual measurements too..? I mean… What if we could store that size L meant 40 – 42 inches..? Now that would be great, wouldn’t it..? So, now, we bring the variables and constructors of an enum into picture. Go through the following code closely –

enum TShirtSizes {

    // Constant(value associated)
    S(36, 38), M(38, 40), L(40, 42), XL(42, 44);

    // Values to be stored
    final int START, END;
    
    // Constructor
    private TShirtSizes(int START, int END) {
        this.START = START;
        this.END = END;
    }

}

public class Enumerations {

    public static void main(String[] args) {
        TShirtSizes shirt = TShirtSizes.L;
        System.out.println(shirt);  // L
        System.out.println(shirt.START + " - " 
                                       + shirt.END);
        // Prints -> 40 - 42
    }

}

This is an enum with variables and a constructor. We cannot directly invoke the constructor. It is automatically called with the values specified at the time of declaring the constants. It is called when we try to create a variable of the enum type. Have a look at the following program –

enum TShirtSizes {

    // Constant(value associated)
    S(36, 38), M(38, 40), L(40, 42), XL(42, 44);

    // Values to be stored
    final int START, END;
    
    // Constructor
    private TShirtSizes(int START, int END) {
        System.out.println("Enum's constructor");
        this.START = START;
        this.END = END;
    }

}

public class Enumerations {

    public static void main(String[] args) {
        System.out.println("main() begins...");
        TShirtSizes shirt = TShirtSizes.L;
        System.out.println(shirt);  // L
        System.out.println(shirt.START + " - " 
                                       + shirt.END);
        // Prints -> 40 - 42
        
        TShirtSizes shirt2 = TShirtSizes.M;
        System.out.println(shirt2);  // M
        System.out.println(shirt2.START + " - "
                                        + shirt2.END);
        // Prints -> 38 - 40
        System.out.println("End of main()");
    }

}

It gives the output –

main() begins...
Enum's constructor
Enum's constructor
Enum's constructor
Enum's constructor
L
40 - 42
M
38 - 40
End of main()

So the constructor is called as many times as the number of constants in the enum, when we use it for the first time. If we don’t use it at all, then the constructor is never called.
We can also have non-static methods in a enum, which can use this reference to refer to the calling object.
enum has a static method called values() which returns an array of the enum constants. This method can be called from the main method –

public static void print() {
    for (TShirtSizes shirt : TShirtSizes.values()) {
        System.out.print(shirt);
        System.out.print("(" + shirt.START);
        System.out.print(" - " + shirt.END);
        System.out.println(")");
    }
}

So, we looked at enum as a special class. Does this mean that we can extend an enum to other classes..? No..! We cannot extend enum to other classes..!

Summary

  • Syntax for declaring an enum in Java –
    enum TShirtSizes {S, M, L, XL};
    
  • We can’t declare an enum locally, we must declare it outside the method.
  • This is how we create a variable of enum and assign a value to it –
    TShirtSizes myShirt = TShirtSizes.L;
    
  • Functions are actually called “methods” in Java.
  • Only static methods can be called from another static method. The main() method being static, can only call other static methods.
  • Methods in Java have six components –
    1. Access Modifier
    2. Return Type
    3. Name
    4. List of Parameters
    5. List of Exceptions
    6. Body of the Method
  • Method signature is the name of the method + list of parameters. It does not include the return type.
  • Primitive Data Types are always passed by value.
  • Objects are passed through their object references, so, they produce a pass-by-reference effect.
  • What really decides if an object can be modified inside a method is whether the object is mutable or not.
  • enums are actually a special kind of classes in Java.
  • We can have constructors, non-static and static variables and methods in a enum.
  • enum has a static method which returns an array of enum type variables which have all the enum’s declared constants.
  • We cannot extend an enum.

This was what you needed to know about enums and methods in Java. I hope it helped you. If you have anything to ask about this topic, feel free to comment..! Keep practising..! Happy Coding..! 😀

Java Tutorials – Arrays in Java

Hello people..! This is a new post in Java Tutorials – Arrays in Java. In this post I will talk about about using arrays in Java. Arrays in Java are different from arrays in C. Arrays in Java are actually objects. But understanding arrays as being-an-object point-of-view is not something beginners feel comfortable with. So this discussion will introduce new terms and concepts. So, let’s get started…!

Arrays in Java

Creating an array in Java has 3 steps –

  • Declaration – In this step, we specify the data type and the dimensions of the array that we are going to create. But remember, we don’t mention the sizes of dimensions yet. They are left empty.
  • Instantiation – In this step, we create the array, or allocate memory for the array, using the new keyword. It is in this step that we mention the sizes of the array dimensions.
  • Initialization – The array is always initialized to the data type’s default value. But we can make our own initializations.

Now, let’s look at the individual steps in a little more detail.

Declaration

This is how we declare a one-dimensional array in Java –

int[] array;

Well, you should have guesses it because we’ve been declaring arrays right from our first program…! Really..? Yeah..! In the main() method’s declaration..!

public static void main(String[] args) {
    // code
}

The formal parameter of the main() method is a one-dimensional array of Strings. Well, for C programmers, it might look like we are almost done with creating an array… But no..! We have just merely declared it, we have not allocated any memory yet.
There is another syntax by which we can declare arrays –

int array[];

This is looks almost like the C’s array declaration. But here, we don’t specify the size… Not yet..! But this style of declaration is considered to be ugly..! Oracle recommends that you use the previously discussed declaration syntax for declaring arrays.
Here are some other examples of legal declarations –

// One Dimensional Arrays
int[] intArray;             // Good
double[] doubleArray;

// One Dimensional Arrays
byte byteArray[];           // Ugly!
long longArray[];

// Two Dimensional Arrays
int[][] int2DArray;         // Good
double[][] double2DArray;

// Two Dimensional Arrays
byte[] byte2DArray[];       // Ugly
long[] long2DArray[];

And these are some examples of illegal declarations –

int[5] intArray;       // Don't mention size!
double{} doubleArray;  // Square Brackets please!

Instantiation

This is how we “instantiate”, or allocate memory for an array –

int[] array = new int[5];

When the JVM encounters the new keyword, it understands that it must allocate memory for something. And by specifying int[5], we mean that we want an array of ints, of size 5.
So, the JVM creates the memory and assigns the reference of the newly allocated memory to array which a “reference” of type int[]. Bit confusing isn’t it..? We can understand it better if we put the JVM’s job in a step-by-step process, but you’ll have to get used to the terminology –

  1. We create a reference of type int[], or, vaguely, we create a reference to an array of integers. The syntax is –
    int[] array;
    
  2. Then, we allocate the memory, or, create an object of type int[], or, we create an object of an array. In this step, we mention the size of the dimensions –
    int[] array = new int[5];
    int[][] bigArray = new int[5][5];
    
  3. Now, the JVM allocates the required memory an assigns the address of the newly allocated memory to the reference variable, or, object reference, the array variable. The array is initialized to the default value of the data type.

Let’s write a super simple code to practise the things we learnt so far. This program computes and stores the first 100 Fibonacci numbers –

public class SimpleFib {

    public static void main(String[] args) {
        int[] fib;              // Declaration
        fib = new int[100];     // Instantiation

        fib[0] = 1;
        fib[1] = 1;

        for (int i = 2; i < 100; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }

}

Note

Arrays in Java always know their sizes. The size of an array is available to you as the length property. You can use the dot operator ‘.’ on the object reference to access the length property. So, we can re-write the SimpleFib class using this feature –

public class SimpleFib {

    public static void main(String[] args) {
        int[] fib;              // Declaration
        fib = new int[100];     // Instantiation

        fib[0] = 1;
        fib[1] = 1;

        for (int i = 2; i < fib.length; ++i) {
            fib[i] = fib[i - 1] + fib[i - 2];
        }
    }

}

This is a more robust and maintenance free way of writing arrays with loops. This is a good practice and is recommended by many experienced programmers.

Initialization

  1. Using a Loop – Using a for loop to initialize elements of an array is the most common way to get the array going. There’s no need to run a for loop if you are going to assign the default value itself, because JVM does it for you.
  2. All in One..! – We can Declare, Instantiate and Initialize our array in one go. Here’s the syntax –
    int[] arr = {1, 2, 3, 4, 5};
    

    C programmers shouldn’t feel too weird about this syntax. Here, we don’t mention the size, because JVM can see that we are giving 5 values, so it says, “I’m not that dumb..!! 😛 ” … So the JVM does these bunch of things when it encounters such a statement –

    • Creates a variable named arr of type int[], that is, it becomes an array object reference variable.
    • Constructs an array object, or Instantiates, an int array of size 5.
    • Fills the newly constructed array with 1, 2, 3, 4, 5.
    • Assigns this array object to the array object reference variable, arr. A low level note…. It assigns the bit pattern corresponding to the memory allocated to the array. Well, you needn’t be too concerned about it. 😉

Anonymous Array

There is another “All in one..!” syntax to create arrays which is often called as an Anonymous Array. The syntax is –

int[] arr = new int[] {1, 2, 3, 4, 5};

Uh… What is this thing..? It looks like we added an additional “new int[]” to our previous version of “All in one..!” syntax. And we also know that the statement works fine even without that additional decoration.
Then why bother about this syntax at all..? This is handy in creating just-in-time arrays. Such requirement commonly arises when we are supposed to pass ever-changing values to a very frequently used function. Let’s assume you have a function that searches for some names in your phonebook and returns true if all the names were present. It would look like this –

public class AnonymousArray {

    public static void main(String[] args) {
       IsThere(new String[] {"Bill Gates", "Steve Jobs"});
       IsThere(new String[] {"James Gosling", "Ritchie"});
       IsThere(new String[] {"Emma Watson", "Emma Stone"});
    }

    static boolean IsThere(String[] names) {
        // Do some searching on something
        return true;    // if found, else false
    }

}

As you can see, you are frequently searching for names in your phonebook. Sometimes millionaires, or fathers of programming languages, or sometimes gorgeous actresses..! And based on whether the method returns true or false, you would like to take some action.
So, why exactly is Anonymous Arrays handy here..? Imagine you used the regular array syntax for the program –

public class RegularArray {

    public static void main(String[] args) {
        String[] millnrs = {"Bill Gates", "Steve Jobs"};
        String[] fathers = {"James Gosling", "Ritchie"};
        String[] actresses = {"Emma Watson", "Emma Stone"};

        IsThere(millnrs);
        IsThere(fathers);
        IsThere(actresses);
    }

    static boolean IsThere(String[] names) {
        // Do some searching on something
        return true;    // if found, else false
    }

}

Notice anything..? Well, it was just 3 arrays, so you may not notice anything. But imagine if you are creating a hundred such arrays..! They would all be lying in the memory with no purpose at all..! Plus… You’ll simply run out of names for the variables to create..! So, these two are the advantages of Anonymous Arrays in Java –

  • They don’t lie in the memory… Well, there are a special cases where they can. But generally using Anonymous Arrays for just-in-time requirements is a tidy business.
  • You don’t have to remember a lot names..! That is why they are called “anonymous”..!

Multidimensional Arrays in Java

Java treats multidimensional arrays literally as an “Array of Arrays”. You may not know what’s the little surprise behind that statement… So watch closely..!
These are some regular legal declarations for 2D arrays in Java –

int[][] arr2by2 = new int[2][2];
byte[][] arr2by3 = new byte[2][3];
short[][] arr0by2 = new short[0][2];

We all know how those arrays would look in the memory. Now, have a look at this two-dimensional array –

int[][] arr = new int[2][];

arr[0] = new int[2];
arr[1] = new int[3];

Well… You didn’t expect this did you..? 😛 … This is a really different way of creating a 2D array. In the memory, it would look like –
two-dimensional-array-in-java
You see how the array reference thing works..? The data types of the variables are shown by dotted arrows. The elements arr[0] and arr[1] become independent array references which can point to an array of any size. Hence, they point to different array objects which have arrays of different sizes. Important points to take away from the diagram are –

  • Array Objects (the oval shapes on the Heap) are created on the heap.
  • Array Object references of a particular dimension can point to an array object of the same dimension.Hence the following code is invalid –
    int[][] arr = new int[2][];
    
    arr[0] = new int[2][3];
    arr[1] = new int[3][4][5];
    

Methods in Arrays Class

There are a lot of predefined methods in the Arrays class absolutely ready to use..! In most of these methods, we must make sure that the objects are Comparable. A word of caution..! It is the “Arrays” Class, not “Array” Class… Be careful because there is an “Array” Class.

Method Signature Short Description
Arrays.sort(int[] array) Sorts the elements of the array in ascending order using Dual-Pivot Quicksort by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. Has an good performance of O(N log N).
Arrays.sort(int[] array, int fromIndex, int toIndex) Sorts the elements of the array in the range [fromIndex, toIndex) into ascending order. Uses  the same Dual-Pivot Quicksort algorithm.
Arrays.binarySearch(int[] array, int key) Uses Binary Search algorithm to search for a key in the given array. Returns the index of the element if found, otherwise returns the index of the first element greater than the key. The array must be sorted in ascending order.
Arrays.binarySearch(int[] array, int fromIndex, int toIndex, int key) Uses Binary Search algorithm to search for a key in the given array in the range [fromIndex, toIndex). Has the same exact return values and requirements as the above version.
Arrays.copyOf(int[] array, int newLength) Returns a new Array which has the same elements as in the actual parameter array up to where the index is newLength. If newlength > array.length, then the extra elements are set to the default value of the respective data type.
Arrays.copyOfRange(int[] array, int fromIndex, int toIndex) Returns a new Array which has the same elements as in the actual parameter array, where index of the element in the parameter array is in the range [fromIndex, toIndex).
Arrays.equals(int[] array1, int[] array2) Returns true if both the arrays have the same elements in the same order.
Arrays.fill(int[] array, int value) Assigns value to all the elements of array.
Arrays.fill(int[] array, int fromIndex, int toIndex, int value) Assigns value to all the elements of array in the range [fromIndex, toIndex).

All these methods have overloaded versions to support all the primitive data types. To all those who don’t know overloading.. It means that you can use arrays of other data types with these functions… We will discuss overloading very soon..!

Some Pitfalls when using Arrays in Java

  1. Assigning One-Dimensional Arrays – We all know that JVM does a lot of automatic type conversion for us in the case of expressions involving variables of different numeric data types. Just a brief reminder that Java employs widening type conversion. Now, how about assigning a short array object to an int array object..?
    short[] shortArray = new short[10];
    int[] intArray = new int[5];
    
    intArray = shortArray;
    

    Well it seems to be fine.. But this gives a compilation error of “Incompatible Types”. The problem here isn’t that the sizes are different, but the issue is that a reference of type int[] can point to an object of int[], that is, an integer array, not any other.

  2. Assigning Two-Dimensional Arrays – The dimension of array, an array object reference can point to is fixed at the time of declaration and we cannot violate it. So, this code gives a compilation error –
    int[][] arr1 = new int[2][];
    int[][] arr2 = new int[3][2];
    
    arr1[0] = arr2;
    
  3. Array Size – There’s a small tricky thing with the array size. We generally don’t mess up this area, but it never harms to know. These are some legal array declarations –
    int[] arr = new int[0];
    int[][] arr = new int[0][2];
    

    Well, there’s nothing new… Even the GCC compiler wouldn’t bother about these pointless arrays. But, this is a legal array declaration in Java –

    short[] shortArray = new short[-1];
    

    Yes, it is legal… Legal, in the sense that the compiler won’t complaint… But you do get a runtime error saying, “NegativeArraySizeException”. The same thing in C would give a compilation error..!

Summary

  • This is how we declare and allocate memory (instantiate) for an array in Java –
    int[] array = new int[5];
    int[][] bigArray = new int[5][5];
    
  • The array elements are always initialized to the data type’s default value.
  • We can give our own initialization by –
    int[] arr = new int[] {1, 2, 3, 4, 5};
    
  • Arrays in Java always know their sizes. Every array object has a length attribute which is accessed by the dot operator –
    int[] arr = new int[5];
    System.out.println(arr.length);    // 5
    
  • We can create an anonymous array to implement some just-in-time logic by the syntax –
    function(new int[] {1, 2, 3, 4, 5});
    
  • Each element of a multidimensional array is an independant array reference. So, they can hold arrays of different sizes –
    int[][] arr = new int[2][];
    
    arr[0] = new int[2];
    arr[1] = new int[3];
    
  • The Arrays Class provides many useful methods to perform the regular operations on arrays easily and efficiently.
  • Even though Java employs widening type conversion between compatible data types, the following gives a compilation error –
    short[] shortArray = new short[10];
    int[] intArray = new int[5];
    
    intArray = shortArray;
    

Practise

  • Can you guess the output of this program..?
    public class ArraySizes {
    
        public static void main(String[] args) {
            int[][][] array1 = new int[1][3][5];
            int[][][][] array2 = new int[2][1][0][1];
    
            System.out.println(array1.length);
            System.out.println(array1[0].length);
            System.out.println(array1[0][1].length);
    
            System.out.println();
    
            System.out.println(array2.length);
            System.out.println(array2[1].length);
            System.out.println(array2[1][0].length);
    
            System.out.println();
    
            String[][][] str = new String[2][][];
    
            System.out.println(str.length);
            System.out.println(str[1]);
        }
    
    }
    

    Don’t run it…! 😛

This is all you need to know about arrays in Java to start writing programs of fairly good amount of complexity. I hope it helped you. If you have anything to ask about this topic, feel free to comment..! Keep practising..! Happy Coding..! 😀

Java Tutorials – String, StringBuffer and StringBuilder in Java

Hello people…! This is a new post in Java Tutorials – String, StringBuffer and StringBuilder in Java. In this post, I will talk about some basics about Strings in Java. Why basics…? Well, there is a lot in Java when it comes to Strings, which we can’t understand right now due to lack of knowledge. But, on the other hand, these are so basic elements of simple programs, that we can hardly write any useful code without these. So, I will cover only what is required to programs involving good computation, so that you will be able to practice Java writing those programs which you wrote to practise C.

Strings in Java

First of all, to learn Strings in Java… You must forget whatever you learnt about strings in C…! This is because, a String in Java is not exactly treated as an array of characters terminated by a null character..! No..! String in Java is actually an object of the String Class, which is in the java.lang package, or library. But, we can use it fairly as we use strings in C++ (#include <string>). If you know only C, then watch closely..!

String name = "Albus Dumbledore";

This is how we create a String in Java. Here, the variable name, is called an Object Reference. As the name suggests, object reference, it points to an object. The object reference here is of the data type String, which is a class. We will talk a lot about a class later, but for now, think of it as a struct where we can have methods, hence, a user defined data type, here defined by Java for you. Now, the variable name is now pointing to an object of String Class, which has the data “Albus Dumbledore”.

So, when the above line is executed, we don’t get an array of characters, but instead, we get one chunk of memory where the string is stored.

Now, how would we access the variables inside a struct..? We would use the dot operator (struct.variable). Similarly, we use the dot operator, to access the variables and methods of the String Class. Well, let’s proceed with a familiar example of a C struct.

struct Person
{
	char * name;
	char * phone;
	char * email;
	int age;
};

int main()
{
	struct Person harry;

	harry.name = "Harry Potter";
	harry.phone = "9999999999";
	harry.email = "harrypotter@hogwarts.com";
	harry.age = 10;

	return 0;
}

This is how we would create a variable of type struct Person and use its members. In the same fashion, we will use the members of String Class, but this time, it will be functions, not variables (not that we can’t have variables)..!

public class JavaStrings {

    public static void main(String[] args) {
        String name = "Albus Dumbledore";

        // Prints length of String
        System.out.println(name.length());  // 16

        // Prints the last character of String -> e
        System.out.println(name.charAt(name.length() - 1));

        // Returns index of the 1st occurence
        System.out.println(name.indexOf("bus"));    // 2

        // Returns the substring from startIndex - endIndex
        // Here, returns the first word -> Albus
        System.out.println(
                name.substring(0, name.indexOf(' ')));

        // Another Example
        String plan = "Plan you work, and work your plan";

        // false, as it starts with "Plan" not "plan"
        System.out.println(plan.startsWith("plan"));

        // true, as it ends with "plan"
        System.out.println(plan.endsWith("plan"));
    }

}

As you can see, when we use the object reference, name or plan, we can access the various functions provided to us by String Class. All these methods are accessed by the object reference. I’ve used a lot of functions in the program, let’s look at them in a little more detail –

  • length() – This function returns an int, which is the length of the string –
    System.out.println(name.length());
    

    But, which string…? The one name is pointing to..! If the same function were called on another object reference, it would return the length of that string, as in –

    String name = "Albus Dumbledore";
    String plan = "Plan you work, and work your plan";
    
    System.out.println(name.length());  // 16
    System.out.println(plan.length());  // 33
    
  • charAt(int index) – This function, as the name suggests, returns the character the the given index –
    System.out.println(name.charAt(name.length() - 1));
    

    So, the return type is char. Argument must be zero indexed. But what if we give an invalid index. What would happen to the code below..?

    public static void main(String[] args) {
        String name = "Albus Dumbledore";
    
        System.out.println(name.charAt(100));
    }
    

    This would cause a runtime error, or famously called as an Exception..!

    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 100
    	at java.lang.String.charAt(String.java:646)
    	at test.main(test.java:7)
    Java Result: 1
    

    So, the StringIndexOutOfBoundsException is thrown at runtime.

  • indexOf(String str) – This function returns an int, which is the first occurrence, of the string provided as argument –
    System.out.println(name.indexOf("bus")); // 2
    

    If the search fails, -1 is returned. The argument can be a char also, as we searched for first space while printing the first word.

  • substring(int startIndex, int endIndex) – This function returns a substring from the string in the object, from a specified startIndex to an endIndex
    //Returns "Albus"
    System.out.println(name.substring(0, 4));
    

    If either of the arguments are given improperly, the familiar StringIndexOutOfBoundsException is thrown at runtime.

  • startsWith(String prefix) & endsWith(String suffix) – These two functions check if the string in the object have the mentioned prefix or suffix –
    System.out.println(plan.startsWith("plan"));
    System.out.println(plan.endsWith("plan"));
    

    The return type of this function is boolean, so, it returns true if the prefix or suffix is present, otherwise, false.

These were just a few of the many functions that Java provides. We will have a brief note about a few more of others later.

Basic Operations on Strings in Java

  1. Concatenation – We use the addition operator, ‘+’ to concatenate Strings in Java. This is much like the modern programming languages. String Class does provide a method, but this is the most compact way of concatenating strings.
    public class ThatName {
    
        public static void main(String[] args) {
            String name = "Albus ";
    
            name = name + "Percival ";
            name = name + "Wulfric ";
            name += "Brian ";
            name += "Dumbledore!";
    
            System.out.println("The name is - " + name);
        }
    
    }
    

    The other way, is to use the concat() function of the String Class. It returns the concatenated String, which must be assigned back.

    public class IWishTheLegendContinued {
    
        public static void main(String[] args) {
            String name = "Albus ";
    
            name = name.concat("Severus ");
            name = name.concat("Potter");
    
            System.out.println(name +"! You've been named"
                + " after two Headmasters of Hogwarts!");
        }
    
    }
    

    Harry Potter fans…! Please continue the dialogue for me..!! 😀

  2. Equality – Beginners make a common mistake of comparing two strings using “==”. This does not work properly..! We must always use the equals() method of the String class to compare two strings. The data type of the argument is something I’ll reserve for later..! But, remember that this is how we compare Strings –
    public class DeadlyDuo {
    
        public static void main(String[] args) {
            String fred = "Tall n' Brave";
            String george = "Tall ";
    
            george += "n' Brave";
    
            if (fred.equals(george)) {
                System.out.println("Equal");
            }
        }
    
    }
    
  3. Comparision – We use the compareTo() function in the String Class to lexicographically compare two strings –
    public class IssIssIppiWhatever {
    
        public static void main(String[] args) {
            String str1 = "Missouri";
            String str2 = "Mississippi";
    
            if (str1.compareTo(str2) == 0) {
                System.out.println("Equal");
            } else if (str1.compareTo(str2) < 0) {
                System.out.println(str1);
            } else {
                System.out.println(str2);
            }
        }
    
    }
    

    As you can see, it compares two strings and returns an integer –

    • Less than zero – If the argument is lexicographically smaller than the string in object reference.
    • Equal to zero – If both strings are lexicographically equal.
    • Greater than zero – If the argument is lexicographically greater than the string in object reference.

Mutable Strings

Strings in Java are actually immutable in nature. It means that, they cannot be modified or, they are read-only. We cannot change the content inside them. Then how can we create strings where we can actually manipulate them..? We can do so, by creating objects of –

  • StringBuffer Class
  • StringBuilder Class

Till now we have created strings using the String Class. But as they are immutable, we will create strings using the other classes. Let’s use the StringBuffer Class –

public class LikeFatherLikeSon {

   public static void main(String[] args) {
     StringBuffer father, son;

     father = new StringBuffer("James Potter");

     son = father.replace(0, father.indexOf(" "), "Harry");

     System.out.println(son);
   }    

}

As you can see, these strings can be modified. We use the various methods provided in the StringBuffer Class to manipulate them. Some of them are discussed in the next section.

Methods in StringBuffer Class

Method Signature Short Description
StringBuffer append(String str) Appends, adds it to the end, of the argument string.
char charAt(int index) Retrieves the character at the index in the range [0, length – 1]
StringBuffer delete(int startIndex, int endIndex) Deletes the characters from the string in the range [startIndex, endIndex)
StringBuffer deleteCharAt(int index) Deletes the character from the string at the specified index.
int indexOf(String str) If found, returns the index of the first occurrence of the string str, otherwise, returns -1.
StringBuffer insert(int offset, String str) Inserts the string str at an offset, or, inserts it in between characters at index – (offset – 1) and offset
int lastIndexOf(String str, int startIndex) If found, returns the index last occurrence of str from startIndex (optional). Call lastIndexOf(“”) returns the string length.
int length() Returns the length of the string.
StringBuffer replace(int startIndex, int endIndex, String str) Replaces the [startIndex, endIndex) portion of the string with str.
StringBuffer reverse() Returns the string with the character sequence reversed.
void setCharAt(int index, int newChar) Replaces the character at index to newChar
String substring(int startIndex, int endIndex) Returns an object of String Class which is a substring of the original string in the range [startIndex, endIndex). The parameter endIndex is optional.

Difference between StringBuffer and StringBuilder

The same methods which are provided by the StringBuffer Class are also provided by the StringBuilder Class (of course they differ in the return types), but with a small twist. Well, you need to know a little Multi-threading to understand this properly, but it doesn’t harm to learn them now. We will re-visit this topic again, but for now, I wan’t you to be ready if anybody asks the difference.

StringBuffer StringBuilder
All methods in StringBuffer are synchronized. Which means that they are thread-safe. By thread-safe, we mean that no two threads can simultaneously access the method of an object of StringBuffer Class.

StringBuffer Append in Java

StringBuffer Append in Java

Methods are not synchronized. Which means that they are not thread-safe. So, using StringBuilder in a multi-threading environment can cause data corruption due to concurrency.

StringBuilder Append in Java

StringBuilder Append in Java

Being synchronized, they are slow. This is because of the thread safety. Faster than StringBuffer because they don’t carry a burden on synchronization.

But, in a single-threading environment, these two should deliver fairly equal performance. So this choice is left to the programmer. The reference snips are taken from the original java.lang.StringBuffer and java.lang.StringBuilder Class provided by Java, as viewed from NetBeans IDE. I don’t want you to worry about what you don’t understand. All I want you to notice in those snips is the presence and absence of the keyword synchronized. What does it do..? We’ll get to it later.

Behind the Curtains !

This is an advanced discussion about the internals of String, StringBuilder, StringBuffer class. Beginners… Feel free to skip this….!

Well, so far we talked about Strings as an object, a chunk of memory, not as an array of characters. But the thing is that, internally, String is an array of characters. In the String class, we have a member which is an array of characters. And this member is a constant for the String Class. So, its like…. If we put this in C terms, it would look like –

struct String
{
	const char value[10];
};
Array in String Class of Java

Array in String Class of Java

But it is not as simple as it looks, arrays function differently in Java. In fact, if Oracle sees me comparing String Class with that piece of C code, it might say, “If you delete that now, that’ll be the end of it. I will not look for you, I will not pursue you. But if you don’t, I will look for you, I will find you, and I will kill you.” 😛
To get an idea, this is what happening in the String Class –
As you can see –

  • There’s an array of name value.
  • It is declared final, means that it is constant.
  • String Class is final too. So, StringBuffer and StringBuilder are not subclasses of String Class..!
  • The array of characters is private. So, internally String is an array, but we don’t get to see it. This…! This is exactly what Encapsulation is..!! Hiding the implementation…! 😉

So, that’s Java’s little back game, it is operating on an array..! So, when we call length() method, this is what it does –

Length in String Class of Java

Length in String Class of Java

And all the methods operate on this array and return the results if any or throw exceptions accordingly. One last example to make things clear. This is the implementation of the charAt() method –

CharAt of String Class in Java

CharAt of String Class in Java

When it comes to the StringBuffer and StringBuilder Classes, they both inherit from java.lang.AbstractStringBuilder Class..! There, in the abstract class, the character array is defined, which these classes inherit. This is the definition of the AbstractStringBuilder Class –

AbstractStringBuilder Class in Java

AbstractStringBuilder Class in Java

As you can see –

  • The class is defined as abstract.
  • It has a member, value, which is an array of characters.
  • The array is not final.
  • Instead of relying on value.length, it has a variable count, which stores the characters used

Why is using another variable..? Well… These strings have the notion of capacities and actual sizes. One last thing..! StringBuilder and StringBuffer are final classes, just like many other classes in Java Library.

Summary

  • Strings in Java are objects of String Class.
  • Strings created using String Class are immutable. They cannot be modified.
  • We create mutable strings using StringBuffer and StringBuilder classes. The syntax is –
    StringBuffer good = new StringBuffer("Harry Potter");
    StringBuilder evil = new StringBuilder("Tom Riddle");
    
  • Methods in StringBuffer are synchronized, where as methods in StringBuilder are not.
  • StringBuilder gives a better performance than StringBuffer.
  • Internally, the String classes operate on a character array.

This post was to help you with String in Java. I hope it helped you. If you have anything to ask about this topic, feel free to comment..! Keep practising..! Happy Coding..! 😀