Archive for December, 2007

Some Facts about String

December 4, 2007 at 6:58 pm · Filed under Strings I/O Formatting and Parsing ·Tagged

Once you have assigned a String a value, that value can never change— it’s immutable
To protect the immutability, String class is marked as final. Nobody can override the behaviours of any of the String methods.

To make Java more memory efficient, the JVM sets aside a special area of memory called the “String constant pool” When the compiler encounters a String literal, it checks the pool to see if an identical String already exists. If a match is found, the reference to the new literal is directed to the existing String, and no new String literal object is created. (The existing String simply has an additional reference.)

What is the output of the code below? How many String objects and how many reference variables were created prior to the println statement?

String s1 = “spring “;
String s2 = s1 + “summer “;
s1.concat(“fall “);
s2.concat(s1);
s1 += “winter “;
System.out.println(s1 + ” ” + s2);

The result of this code fragment is “spring winter spring summer”. There are two reference variables, s1 and s2. There are total of eight String objects created as follows: “spring”, “summer ” (lost), “spring summer”, “fall” (lost), “spring fall” (lost), “spring summer spring” (lost), “winter” (lost), “spring winter” (at this point “spring” is lost). Only two of the eight String objects are not lost in this process.

What is the difference between the below methods of creating a String?

String s=”one”;
String ss=new String(“one”);

First one creates one String object (which is kept in the String constant pool.) and one reference variable.
Second one creates two objects and one reference variable.

Comments (1)

BinarySearch

December 3, 2007 at 5:09 pm · Filed under Search Algorithms ·Tagged

Binary search is a logarithmic algorithm and executes in O(log2n) time.
Specifically, 1 + log2N iterations are needed to return an answer. In most cases it is considerably faster than a linear search. It can be implemented using recursion or iteration, as shown below. In some languages it is more elegantly expressed recursively; however, in some C-based languages tail recursion is not eliminated and the recursive version requires more stack space. http://en.wikipedia.org/wiki/Binary_search_algorithm

package com.search.binary;
import java.util.Arrays;
import com.sort.quick.QuickSort;
public class BinarySearch {
public int search(int[] data, int target) {
int index = -1;
int bottom = 0;
int top = data.length - 1;
while (bottom <= top) {
int middle = (top + bottom) / 2;
if (target < data[middle]) {
top = middle - 1;
} else if (data[middle] == target) {
return middle;
} else {
bottom = middle + 1;
}
}
return index;
}
public static void main(String[] args) {
int[] data = new int[] { 4, 8, 15, 16, 23, 42 };
System.out.println(new BinarySearch().search(data, 16));
}
}

Leave a Comment

« Newer Posts · Older Posts »