Correlated SubQuery -- Find Nth maximum value in SQL Server

Use Pubs
Go

Create table Employee
(
Eid int,
Name varchar(10),
Salary money
)
Go

Insert into Employee values (1,'harry',3500)
Insert into Employee values (2,'jack',2500)
Insert into Employee values (3,'john',2500)
Insert into Employee values (4,'xavier',5500)
Insert into Employee values (5,'steven',7500)
Insert into Employee values (6,'susana',2400)
Go
A simple query that can find the employee with the maximum salary, would be:

Select * from Employee where salary = (Select max(Salary) from Employee)
How does this query work?

The SQL Engine evaluates the inner most query and then moves to the next level (outer query). So, in the above example inner query i.e. Select max(Salary) from Employee is evaluated first. This query will return a value of 7500 (based on the sample data shown as above). This value is substituted in the outer query and it is evaluated as:

Select * from Employee where salary = (7500)
Returns:

Eid Name Salary
5 steven 7500
If the same syntax is applied to find out the 2nd or 3rd or 4th level of salary, the query would become bit complex to understand. See the example below:

Select * from Employee where salary =
(Select max(Salary) from Employee where salary
< (Select max(Salary) from Employee where Salary < (Select max(Salary) from Employee where Salary <…………………………………………… N The above query would go on and on, depending on the level of salary that is to be determined. As mentioned earlier, the SQL Engine evaluates the inner most query first and moves the next outer level. One wouldn’t want to write such a big query just to find out this simple information. The same result can be achieved with a simple syntax and easily understandable logic, by using a CORRELATED SUBQUERY.
 As a "Rule of Thumb" keep these points in mind, when you use a correlated sub-query :
1) Correlated sub-query is a performance overhead to the database server and so, you have to use it only if it is required
2) Avoid using Correlated subquery on large tables, as the inner query is evaluated for each row of the outer query Having said that, let’s look at the query that captures the Nth maximum value: Select * From Employee E1 Where (N-1) = (Select Count(Distinct(E2.Salary)) From Employee E2 Where E2.Salary > E1.Salary)
(Where N is the level of Salary to be determined)

In the above example, the inner query uses a value of the outer query in its filter condition meaning; the inner query cannot be evaluated before evaluating the outer query. So each row in the outer query is evaluated first and the inner query is run for that row. Let’s look into the background process of this query, by substituting a value for N i.e. 4,(Idea is to find the 4th maximum salary):

Select * From Employee E1 Where
(4-1) = (Select Count(Distinct(E2.Salary)) From Employee E2 Where
E2.Salary > E1.Salary)
Since the outer query’s value is referred in the inner query, the operation is done row-by-row. Based on the sample data as shown above, the process starts with the following record:

Employee E1
----------------------------------
Eid Name Salary
1 harry 3500
The salary of this record is substituted in the inner query and evaluated as:

Select Count(Distinct(E2.Salary)) From Employee E2
Where E2.Salary > 3500
Above query returns 2 (as there are only 2 salaries greater than 3500). This value is substituted in the outer query and will be evaluated as:

Select * From Employee E1 Where (4-1) = (2)
The "where" condition evaluates to FALSE and so, this record is NOT fetched in the result.

Next the SQL Engine processes the 2nd record which is:

Employee E1
----------------------------------
Eid Name Salary
2 jack 2500
Now the inner query is evaluated as:

Select Count(Distinct(E2.Salary)) From Employee E2
Where E2.Salary > 2500
This query returns a value of 3 (as there are 3 salaries greater than 2500). The value is substituted in the outer query and evaluated as:

Select * From Employee E1 Where (4-1) = (3)
The "where" condition evaluates to TRUE and so, this record IS fetched in the result. This operation continues for all the remaining records. Finally the result shows these 2 records:

Eid Name Salary
2 jack 2500
3 john 2500
The above query works in the same manner in Oracle and Sybase as well. Applying the same logic, to find out the first maximum salary the query would be:

Select * From Employee E1 Where
(1-1) = (Select Count(Distinct(E2.Salary)) From Employee E2 Where
E2.Salary > E1.Salary)
If you are able to understand this functionality, you can workout various other queries in the same manner. The bottom line is, the query should be efficient and NOT resource hungry.

http://www.sqlteam.com/article/find-nth-maximum-value-in-sql-server

Important SQL Queries

Deleting only dupes from a table

DELETE FROM mytable
WHERE EXISTS
( SELECT name1, age1, MIN(id) as cf_prog
FROM mytable TAB02
WHERE ( mytable.name1 = TAB02.name1 ) AND
( mytable.age1 = TAB02.age1 )
GROUP BY name1, age1
HAVING ( count(*) > 1 ) AND
( mytable.id <> cf_prog ) )

Selecting Dupes from a table

select cargo_id, dest_id
from routing t1
where
( select count(*)
from routing t2
where t2.dest_id = t1.dest_id ) > 1


Finding the Nth maximum from a table

select *
from yourTable X
where n-1 =
(select count(*)
from yourTable
where salary > X.salary)
order by salary desc

Selecting the top n rows from a table


select *
from employee X
where n >
(select count(*)
from employee
where dept = X.dept
and salary > X.salary)
order by dept, salary desc

Where vs Having

SQL Standard says that WHERE restricts the result set before returning rows and HAVING restricts the result set after bringing all the rows. So WHERE is faster. On SQL Standard compliant DBMSs in this regard, only use HAVING where you cannot put the condition on a WHERE (like computed columns in some RDBMSs.)
HAVING clauses should be used to apply conditions on group functions, otherwise they can be mvoed into the WHERE condition.

http://stackoverflow.com/questions/328636/which-sql-statement-is-faster-having-vs-where

SQL - Cursors

SQL Server is very good at handling sets of data. For example, you can use a single UPDATE statement to update many rows of data. There are times when you want to loop through a series of rows a perform processing for each row. In this case you can use a cursor.

Please note that cursors are the SLOWEST way to access data inside SQL Server. The should only be used when you truly need to access one row at a time. The only reason I can think of for that is to call a stored procedure on each row. In the Cursor Performance article I discovered that cursors are over thirty times slower than set based alternatives.
The basic syntax of a cursor is:

DECLARE @AuthorID char(11)

DECLARE c1 CURSOR READ_ONLY
FOR
SELECT au_id
FROM authors

OPEN c1

FETCH NEXT FROM c1
INTO @AuthorID

WHILE @@FETCH_STATUS = 0
BEGIN

PRINT @AuthorID

FETCH NEXT FROM c1
INTO @AuthorID

END

CLOSE c1
DEALLOCATE c1
The DECLARE CURSOR statement defines the SELECT statement that forms the basis of the cursor. You can do just about anything here that you can do in a SELECT statement. The OPEN statement statement executes the SELECT statement and populates the result set. The FETCH statement returns a row from the result set into the variable. You can select multiple columns and return them into multiple variables. The variable @@FETCH_STATUS is used to determine if there are any more rows. It will contain 0 as long as there are more rows. We use a WHILE loop to move through each row of the result set.

The READ_ONLY clause is important in the code sample above. That dramatically improves the performance of the cursor.

In this example, I just print the contents of the variable. You can execute any type of statement you wish here. In a recent script I wrote I used a cursor to move through the rows in a table and call a stored procedure for each row passing it the primary key. Given that cursors are not very fast and calling a stored procedure for each row in a table is also very slow, my script was a resource hog. However, the stored procedure I was calling was written by the software vendor and was a very easy solution to my problem. In this case, I might have something like this:

EXEC spUpdateAuthor (@AuthorID)
instead of my Print statement. The CLOSE statement releases the row set and the DEALLOCATE statement releases the resources associated with a cursor.

If you are going to update the rows as you go through them, you can use the UPDATE clause when you declare a cursor. You'll also have to remove the READ_ONLY clause from above.

DECLARE c1 CURSOR FOR
SELECT au_id, au_lname
FROM authors
FOR UPDATE OF au_lname
You can code your UPDATE statement to update the current row in the cursor like this

UPDATE authors
SET au_lname = UPPER(Smith)
WHERE CURRENT OF c1

http://www.sqlteam.com/article/cursors-an-overview

SQL interview Questions

Q: 1. What are two methods of retrieving SQL?
A: SELECT statement, cursors

Master list of Java interview questions - 115 questions

What is the difference between procedural and object-oriented programs?
 a) In procedural program, programming logic follows certain procedures and the instructions are executed one after another. In OOP program, unit of program is object, which is nothing but combination of data and code. b) In procedural program, data is exposed to the whole program whereas in OOPs program, it is accessible with in the object and which in turn assures the security of the code.

What are Encapsulation, Inheritance and Polymorphism?
 Encapsulation is the mechanism that binds together code and data it manipulates and keeps both safe from outside interference and misuse.
Inheritance is the process by which one object acquires the properties of another object.
Polymorphism is the feature that allows one interface to be used for general class actions.

What is the difference between Assignment and Initialization?
Assignment can be done as many times as desired whereas initialization can be done only once.

What is OOPs?
 Object oriented programming organizes a program around its data, i. e. , objects and a set of well defined interfaces to that data. An object-oriented program can be characterized as data controlling access to code.

What are Class, Constructor and Primitive data types?
Class is a template for multiple objects with similar features and it is a blue print for objects. It defines a type of object according to the data the object can hold and the operations the object can perform. Constructor is a special kind of method that determines how an object is initialized when created. Primitive data types are 8 types and they are: byte, short, int, long, float, double, boolean, char.

What is an Object and how do you allocate memory to it?
Object is an instance of a class and it is a software unit that combines a structured set of data with a set of operations for inspecting and manipulating that data. When an object is created using new operator, memory is allocated to it.

What is the difference between constructor and method?
 Constructor will be automatically invoked when an object is created whereas method has to be called explicitly.

What are methods and how are they defined?
Methods are functions that operate on instances of classes in which they are defined. Objects can communicate with each other using methods and can call methods in other classes. Method definition has four parts. They are name of the method, type of object or primitive type the method returns, a list of parameters and the body of the method. A method’s signature is a combination of the first three parts mentioned above.
What is the use of bin and lib in JDK?- Bin contains all tools such as javac, appletviewer, awt tool, etc., whereas lib contains API and all packages.

What is casting?
Casting is used to convert the value of one type to another.

How many ways can an argument be passed to a subroutine and explain them?-
An argument can be passed in two ways. They are passing by value and passing by reference. Passing by value: This method copies the value of an argument into the formal parameter of the subroutine. Passing by reference: In this method, a reference to an argument (not the value of the argument) is passed to the parameter.

What is the difference between an argument and a parameter?- While defining method, variables passed in the method are called parameters. While using those methods, values passed to those variables are called arguments.

What are different types of access modifiers?- public: Any thing declared as public can be accessed from anywhere. private: Any thing declared as private can’t be seen outside of its class. protected: Any thing declared as protected can be accessed by classes in the same package and subclasses in the other packages. default modifier : Can be accessed only to classes in the same package.

What is final, finalize() and finally?- final : final keyword can be used for class, method and variables. A final class cannot be subclassed and it prevents other programmers from subclassing a secure class to invoke insecure methods. A final method can’t be overridden. A final variable can’t change from its initialized value. finalize() : finalize() method is used just before an object is destroyed and can be called just prior to garbage collection. finally : finally, a key word used in exception handling, creates a block of code that will be executed after a try/catch block has completed and before the code following the try/catch block. The finally block will execute whether or not an exception is thrown. For example, if a method opens a file upon exit, then you will not want the code that closes the file to be bypassed by the exception-handling mechanism. This finally keyword is designed to address this contingency.

What is UNICODE?- Unicode is used for internal representation of characters and strings and it uses 16 bits to represent each other.

What is Garbage Collection and how to call it explicitly?-
When an object is no longer referred to by any variable, java automatically reclaims memory used by that object. This is known as garbage collection. System. gc() method may be used to call it explicitly.

What is finalize() method?- finalize () method is used just before an object is destroyed and can be called just prior to garbage collection.

What are Transient and Volatile Modifiers?
 Transient: The transient modifier applies to variables only and it is not stored as part of its object’s Persistent state. Transient variables are not serialized.
Volatile: Volatile modifier applies to variables only and it tells the compiler that the variable modified by volatile can be changed unexpectedly by other parts of the program.

What is method overloading and method overriding?- Method overloading: When a method in a class having the same method name with different arguments is said to be method overloading. Method overriding : When a method in a class having the same method name with same arguments is said to be method overriding.

What is difference between overloading and overriding?
a) In overloading, there is a relationship between methods available in the same class whereas in overriding, there is relationship between a superclass method and subclass method. b) Overloading does not block inheritance from the superclass whereas overriding blocks inheritance from the superclass. c) In overloading, separate methods share the same name whereas in overriding, subclass method replaces the superclass. d) Overloading must have different method signatures whereas overriding must have same signature.


http://www.techinterviews.com/master-list-of-java-interview-questions

Queue Interface

Queue Interface
A Queue is designed to hold a list of "to-dos," or things to be processed in some way. Although other orders are possible, queues are typically thought of as FIFO (first-in, first-out). Queues support all of the standard Collection methods and they also add methods to add and subtract elements and review queue elements.

PriorityQueue This class is new with Java 5. Since the LinkedList class has been enhanced to implement the Queue interface, basic queues can be handled with a LinkedList. The purpose of a PriorityQueue is to create a "priority-in, priority out" queue as opposed to a typical FIFO queue. A PriorityQueue's elements are ordered either by natural ordering (in which case the elements that are sorted first will be accessed first) or according to a Comparator. In either case, the elements' ordering represents their relative priority.

Map Interface

Map Interface
A Map cares about unique identifiers. You map a unique key (the ID) to a specific value, where both the key and the value are, of course, objects. You're probably quite familiar with Maps since many languages support data structures that use a key/value or name/value pair. The Map implementations let you do things like search for a value based on the key, ask for a collection of just the values, or ask for a collection of just the keys. Like Sets, Maps rely on the equals() method to determine whether two keys are the same or different.

HashMap The HashMap gives you an unsorted, unordered Map. When you need a Map and you don't care about the order (when you iterate through it), then HashMap is the way to go; the other maps add a little more overhead. Where the keys land in the Map is based on the key's hashcode, so, like HashSet, the more efficient your hashcode() implementation, the better access performance you'll get. HashMap allows one null key and multiple null values in a collection.


Hashtable Like Vector, Hashtable has existed from prehistoric Java times. For fun, don't forget to note the naming inconsistency: HashMap vs. Hashtable. Where's the capitalization of t?
Anyway, just as Vector is a synchronized counterpart to the sleeker, more modern ArrayList, Hashtable is the synchronized counterpart to HashMap. Remember that you don't synchronize a class, so when we say that Vector and Hashtable are synchronized, we just mean that the key methods of the class are synchronized. Another difference, though, is that while HashMap lets you have null values as well as one null key, a Hashtable doesn't let you have anything that's null.

LinkedHashMap Like its Set counterpart, LinkedHashSet, the LinkedHash-Map collection maintains insertion order (or, optionally, access order). Although it will be somewhat slower than HashMap for adding and removing elements, you can expect faster iteration with a LinkedHashMap.

TreeMap You can probably guess by now that a TreeMap is a sorted Map. And you already know that by default, this means "sorted by the natural order of the elements." Like TreeSet, TreeMap lets you define a custom sort order (via a Comparable or Comparator) when you construct a TreeMap, that specifies how the elements should be compared to one another when they're being ordered.

Collection - Set

Set Interface
A Set cares about uniqueness—it doesn't allow duplicates. Your good friend the equals() method determines whether two objects are identical (in which case only one can be in the set). The three Set implementations are described in the following sections.

HashSet : A HashSet is an unsorted, unordered Set. It uses the hashcode of the object being inserted, so the more efficient your hashCode() implementation the better access performance you'll get. Use this class when you want a collection with no duplicates and you don't care about order when you iterate through it.

LinkedHashSet : A LinkedHashSet is an ordered version of HashSet that maintains a doubly-linked List across all elements. Use this class instead of HashSet when you care about the iteration order. When you iterate through a HashSet the order is unpredictable, while a LinkedHashSet lets you iterate through the elements in the order in which they were inserted.

Important : 
When using HashSet or LinkedHashSet, the objects you add to them must override hashCode(). If they don't override hashcode(), the default object. hashcode() method will allow multiple objects that you might consider "meaningfully equal" to be added to your "no duplicates allowed" set.


TreeSet: The TreeSet is one of two sorted collections (the other being TreeMap). It uses a Red-Black tree structure, and guarantees that the elements will be in ascending order, according to natural order. Optionally, you can construct a TreeSet with a constructor that lets you give the collection your own rules for what the order should be (rather than relying on the ordering defined by the elements' class) by using a Comparable or Comparator.

About Collections (List)

List Interface
A List cares about the index. The one thing that List has that non-lists don't have is a set of methods related to the index. Those key methods include things like get(int index), indexOf(Object o), add(int index, Object obj), and so on. All three List implementations are ordered by index position—a position that you determine either by setting an object at a specific index or by adding it without specifying position, in which case the object is added to the end. The three List implementations are described in the following sections.

ArrayList Think of this as a growable array. It gives you fast iteration and fast random access. To state the obvious: it is an ordered collection (by index), but not sorted. You might want to know that as of version 1.4, ArrayList now implements the new RandomAccess interface—a marker interface (meaning it has no methods) that says, "this list supports fast (generally constant time) random access." Choose this over a LinkedList when you need fast iteration but aren't as likely to be doing a lot of insertion and deletion.

Vector Vector is a holdover from the earliest days of Java; Vector and Hashtable were the two original collections, the rest were added with Java 2 versions 1.2 and 1.4. A Vector is basically the same as an ArrayList, but Vector methods are synchronized for thread safety. You'll normally want to use ArrayList instead of Vector because the synchronized methods add a performance hit you might not need. And if you do need thread safety, there are utility methods in class Collections that can help. Vector is the only class other than ArrayList to implement RandomAccess.

LinkedList A LinkedList is ordered by index position, like ArrayList, except that the elements are doubly-linked to one another. This linkage gives you new methods (beyond what you get from the List interface) for adding and removing from the beginning or end, which makes it an easy choice for implementing a stack or queue. Keep in mind that a LinkedList may iterate more slowly than an ArrayList, but it's a good choice when you need fast insertion and deletion. As of Java 5, the LinkedList class has been enhanced to implement the java.util.Queue interface. As such, it now supports the common queue methods: peek(), poll(), and offer().

Union, Intersection, Difference Operations on Sets(Collection)

Bulk operations are particularly well suited to Sets; when applied, they perform standard set-algebraic operations. Suppose s1 and s2 are sets. Here's what bulk operations do:
s1.containsAll(s2) — returns true if s2 is a subset of s1. (s2 is a subset of s1 if set s1 contains all of the elements in s2.)
s1.addAll(s2) — transforms s1 into the union of s1 and s2. (The union of two sets is the set containing all of the elements contained in either set.)
s1.retainAll(s2) — transforms s1 into the intersection of s1 and s2. (The intersection of two sets is the set containing only the elements common to both sets.)
s1.removeAll(s2) — transforms s1 into the (asymmetric) set difference of s1 and s2. (For example, the set difference of s1 minus s2 is the set containing all of the elements found in s1 but not in s2.)
To calculate the union, intersection, or set difference of two sets nondestructively (without modifying either set), the caller must copy one set before calling the appropriate bulk operation. The following are the resulting idioms.
Set union = new HashSet(s1);
union.addAll(s2);

Set intersection = new HashSet(s1);
intersection.retainAll(s2);

Set difference = new HashSet(s1);
difference.removeAll(s2);

The implementation type of the result Set in the preceding idioms is HashSet, which is, as already mentioned, the best all-around Set implementation in the Java platform. However, any general-purpose Set implementation could be substituted.
Let's revisit the FindDups program. Suppose you want to know which words in the argument list occur only once and which occur more than once, but you do not want any duplicates printed out repeatedly. This effect can be achieved by generating two sets — one containing every word in the argument list and the other containing only the duplicates. The words that occur only once are the set difference of these two sets, which we know how to compute. Here's how the resulting program looks.


import java.util.*;

public class FindDups2 {
public static void main(String[] args) {
Set uniques = new HashSet();
Set dups = new HashSet();

for (String a : args)
if (!uniques.add(a))
dups.add(a);

// Destructive set-difference
uniques.removeAll(dups);

System.out.println("Unique words: " + uniques);
System.out.println("Duplicate words: " + dups);
}
}

When run with the same argument list used earlier (i came i saw i left), the program yields the following output.
Unique words: [left, saw, came]
Duplicate words: [i]

A less common set-algebraic operation is the symmetric set difference — the set of elements contained in either of two specified sets but not in both. The following code calculates the symmetric set difference of two sets nondestructively.
Set symmetricDiff = new HashSet(s1);
symmetricDiff.addAll(s2);
Set tmp = new HashSet(s1);
tmp.retainAll(s2));
symmetricDiff.removeAll(tmp);

http://java.sun.com/docs/books/tutorial/collections/interfaces/set.html

Class Loading fundamentals

The first thing that happens when you run Java on Beetle is that you try to access Beetle.main( ) (a static method), so the loader goes out and finds the compiled code for the Beetle class (this happens to be in a file called Beetle.class). In the process of loading it, the loader notices that it has a base class (that’s what the extends keyword says), which it then loads. This will happen whether or not you’re going to make an object of that base class. (Try commenting out the object creation to prove it to yourself.)
If the base class has a base class, that second base class would then be loaded, and so on. Next, the static initialization in the root base class (in this case, Insect) is performed, and then the next derived class, and so on. This is important because the derived-class static initialization might depend on the base class member being initialized properly.
At this point, the necessary classes have all been loaded so the object can be created. First, all the primitives in this object are set to their default values and the object references are set to null—this happens in one fell swoop by setting the memory in the object to binary zero. Then the base-class constructor will be called. In this case the call is automatic, but you can also specify the base-class constructor call (as the first operation in the Beetle( ) constructor) by using super. The base class construction goes through the same process in the same order as the derived-class constructor. After the base-class constructor completes, the instance variables are initialized in textual order. Finally, the rest of the body of the constructor is executed.

Advantages of Iterator over forEach

1. Iterator is a design pattern and is a light-weight container.
2. Iterator doesnt need to know what the collection is (i.e. a List or sth else )
3. Using iterator ,we can remove the current element. The for-each loop hides the iterator, so you cannot call remove. Therefore, the for-each loop is not usable for filtering.
4. Similarly, forEach is not usable for loops where you need to replace elements in a list or array as you traverse it, but Iterator can be used.
5 .Finally, forEach is not usable for loops that must iterate over multiple collections in parallel.

http://java.sun.com/j2se/1.5.0/docs/guide/language/foreach.html

If a Runtime Exception is thrown in the finalize method

finalize
protected void finalize()
throws Throwable Called by the garbage collector on an object when garbage collection determines that there are no more references to the object. A subclass overrides the finalize method to dispose of system resources or to perform other cleanup.
The general contract of finalize is that it is invoked if and when the JavaTM virtual machine has determined that there is no longer any means by which this object can be accessed by any thread that has not yet died, except as a result of an action taken by the finalization of some other object or class which is ready to be finalized. The finalize method may take any action, including making this object available again to other threads; the usual purpose of finalize, however, is to perform cleanup actions before the object is irrevocably discarded. For example, the finalize method for an object that represents an input/output connection might perform explicit I/O transactions to break the connection before the object is permanently discarded.

The finalize method of class Object performs no special action; it simply returns normally. Subclasses of Object may override this definition.

The Java programming language does not guarantee which thread will invoke the finalize method for any given object. It is guaranteed, however, that the thread that invokes finalize will not be holding any user-visible synchronization locks when finalize is invoked. If an uncaught exception is thrown by the finalize method, the exception is ignored and finalization of that object terminates.

After the finalize method has been invoked for an object, no further action is taken until the Java virtual machine has again determined that there is no longer any means by which this object can be accessed by any thread that has not yet died, including possible actions by other objects or classes which are ready to be finalized, at which point the object may be discarded.

The finalize method is never invoked more than once by a Java virtual machine for any given object.

Any exception thrown by the finalize method causes the finalization of this object to be halted, but is otherwise ignored.


Throws:
Throwable - the Exception raised by this method


http://java.sun.com/j2se/1.5.0/docs/api/java/lang/Object.html

Throwable class hierarchy

http://www.cs.colorado.edu/~main/javasupp/throwable.html

Exception inside finally block

An issue for which there's no really neat solution is that code in the finally block could itself throw an exception. In this case, the exception in the finally block would be thrown from the exception instead of any exception occurring inside the try block. Since code in the finally block is intended to be "cleanup" code, we could decide to treat exceptions occurring there as secondary, and to put an explicit catch:

public int readNumber(File f) throws IOException, NumberFormatException {
BufferedReader br = new BufferedReader(new
InputStreamReader(new FileInputStream(f), "ASCII"));
try {
return Integer.parseInt(br.readLine());
} finally {
try { br.close(); } catch (IOException e) {
// possibly log e
}
}
}


We might often choose to at least log the exception. In the case of an exception occurring while closing an input stream1, this is one of the few cases where it's fairly legitimate to just ignore the exception, or else take the risk that it will override the main exception. (If you log the exception to somewhere, then you would have a chance of catching cases where your logic was wrong and an exception during closure turned out to be significant for some reason.) For something as unlikely as an exception while closing an input stream, "taking the risk" is generally my preferred solution, favouring more succinct code.

More care needs to be taken during closure of an output stream, since in this case pending data may actually be written before closure and an "important" error is more likely. For different reasons, we may actually arrive at the same code pattern: since data is potentially being written, we probably would allow an exception on closure to be propagated by the method. The 'overriding' exception in the finally clause is still likely to indicate the underlying cause of the initial exception.

Some other things to note about finally blocks:

The same 'overriding' problem that we mentioned with exceptions occurs when returning a value from a finally block: this would override any return value that the code in the try block wanted to return. In practice, returning a value from a finally clause is rare and not recommended.
Actually exiting the program (either by calling System.exit() or by causing a fatal error that causes the process to abort: sometimes referred to informally as a "hotspot" or "Dr Watson" in Windows) will prevent your finally block from being executed!
There's nothing to stop us nesting try/catch/finally blocks (for example, putting a try/finally block inside a try/catch block, or vice versa), and it's not such an uncommon thing to do.

Blank Final Variables

A variable can be declared final. A final variable may only be assigned to once. It is a compile time error if a final variable is assigned to unless it is definitely unassigned (§16) immediately prior to the assignment.
A blank final is a final variable whose declaration lacks an initializer.

Once a final variable has been assigned, it always contains the same value. If a final variable holds a reference to an object, then the state of the object may be changed by operations on the object, but the variable will always refer to the same object. This applies also to arrays, because arrays are objects; if a final variable holds a reference to an array, then the components of the array may be changed by operations on the array, but the variable will always refer to the same array.

Declaring a variable final can serve as useful documentation that its value will not change and can help avoid programming errors.

In the example:

class Point {
int x, y;
int useCount;
Point(int x, int y) { this.x = x; this.y = y; }
final static Point origin = new Point(0, 0);
}

the class Point declares a final class variable origin. The origin variable holds a reference to an object that is an instance of class Point whose coordinates are (0, 0). The value of the variable Point.origin can never change, so it always refers to the same Point object, the one created by its initializer. However, an operation on this Point object might change its state-for example, modifying its useCount or even, misleadingly, its x or y coordinate.

Creating Generic Methods

Imagine you want to create a method that takes an instance of any type, instantiates an ArrayList of that type, and adds the instance to the ArrayList. The class itself doesn't need to be generic; basically we just want a utility method that we can pass a type to and that can use that type to construct a type safe collection. Using a generic method, we can declare the method without a specific type and then get the type information based on the type of the object passed to the method. For example:

import java.uti1.*;
public class CreateAnArrayList {
public < t > void makeArrayList(T t) { // take an object of an
// unknown type and use a
// "T" to represent the type
List< t > list = new ArrayList(); // now we can create the
// list using "T"
list.add(t);
}
}

In the preceding code, if you invoke the makeArrayList() method with a Dog instance, the method will behave as though it looked like this all along:

public void makeArrayList(Dog t) {
List list = new ArrayList();
list.add(t);
}


And of course if you invoke the method with an Integer, then the T is replaced by Integer (not in the bytecode, remember—we're describing how it appears to behave, not how it actually gets it done).

The strangest thing about generic methods is that you must declare the type variable BEFORE the return type of the method:

public void makeArrayList(T t)

The before void simply defines what T is before you use it as a type in the argument. You MUST declare the type like that unless the type is specified for the class. In CreateAnArrayList, the class is not generic, so there's no type parameter placeholder we can use.

You're also free to put boundaries on the type you declare, for example if you want to restrict the makeArrayList() method to only Number or its subtypes (Integer, Float, and so on) you would say

public void makeArrayList(T t)

More on Generics

look at the following statements and figure out which will compile:


1) List list = new ArrayList<dog>();
2) List aList = new ArrayList<dog>();
3) List foo = new ArrayList();
4) List cList = new ArrayList<integer>();
5) List bList = new ArrayList<animal>();
6) List dList = new ArrayList<dog>();

The correct answers (the statements that compile) are 1, 2, and 5. The three that won't compile are

Statement: List foo = new ArrayList();

Problem: you cannot use wildcard notation in the object creation. So the new ArrayList() will not compile.

Statement: List cList = new ArrayList();

Problem: You cannot assign an Integer list to a reference that takes only a Dog (including any subtypes of Dog, of course).

Statement: List dList = new ArrayList();

Problem: You cannot assign a Dog to . The Dog is too "low" in the class hierarchy. Only or < Object > would have been legal.

Generics Reloaded

Generic collections give you the same benefits of type safety that you've always had with arrays, but there are some crucial differences that can bite you if you aren't prepared. Most of these have to do with polymorphism.

You've already seen that polymorphism applies to the "base" type of the collection:

List myList = new ArrayList();

In other words, we were able to assign an ArrayList to a List reference, because List is a supertype of ArrayList. Nothing special there—this polymorphic assignment works the way it always works in Java, regardless of the generic typing.

But what about this?

class Parent { }
class Child extends Parent { }
List myList = new ArrayList();

Think about it for a minute.
Keep thinking…

No, it doesn't work. There's a very simple rule here—the type of the variable declaration must match the type you pass to the actual object type. If you declare List foo then whatever you assign to the foo reference MUST be of the generic type . Not a subtype of . Not a supertype of .Just .

These are wrong:

List< Object > myList = new ArrayList(); // NO!
List numbers = new ArrayList(); // NO!
// remember that Integer is a subtype of Number

But these are fine:

List myList = new ArrayList(); // yes
List myList = new ArrayList(); // yes

Difference : Overloading and Overriding

Argument(s)
Overloaded Method : Must change.
Must not change.

Return type
Overloaded Method :Can change.
Overridden Method :Can't change except for covariant returns.

Exceptions
Overloaded Method :Can change.
Overridden Method :Can reduce or climinate. Must not throw new or broader checked exceptions.

Access
Overloaded Method :Can change.
Overridden Method :Must not make more restrictive (can be less restrictive).

Invocation
Overloaded Method :Reference type determines which overloaded version (based on declared argument types) is selected. Happens at compile time. The actual method that's invoked is still a virtual method invocation that happens at runtime, but the compiler will already know the signature of the method to be invoked. So at runtime, the argument match will already have been nailed down, just not the class in which the method lives.
Overridden Method :Object type (in other words, the type of the actual instance on the heap) determines which method is selected. Happens at runtime.

Polymorphism in Overloaded and Overridden Methods

How does polymorphism work with overloaded methods? From what we just looked at, it doesn't appear that polymorphism matters when a method is overloaded. If you pass an Animal reference, the overloaded method that takes an Animal will be invoked, even if the actual object passed is a Horse. Once the Horse masquerading as Animal gets in to the method, however, the Horse object is still a Horse despite being passed into a method expecting an Animal. So it's true that polymorphism doesn't determine which overloaded version is called; polymorphism does come into play when the decision is about which overridden version of a method is called. But sometimes, a method is both overloaded and overridden. Imagine the Animal and Horse classes look like this:

public class Animal {
public void eat () {
System.out.println("Generic Animal Eating Generically"};
}
}
public class Horse extends Animal {
public void eat() {
System.out.println("Horse eating hay ");
}
public void eat(String s) {
System, out .println ("Horse eating " + s) ;
}
}

Notice that the Horse class has both overloaded and overridden the eat() method. Table 2-2 shows which version of the three eat() methods will run depending on how they are invoked.

Table 2-2: Examples of Illegal Overrides Method Invocation Code
Result

Animal a = new Animal(); a.eat();
Generic Animal Eating Generically

Horse h = new Horse(); h.eat();
Horse eating hay

Animal ah = new Horse (); ah.eat();
Horse eating hay

Polymorphism works—the actual object type (Horse), not the reference type (Animal), is used to determine which eat() is called.

Horse he = new Horse(); he.eat("Apples") ;
Horse eating Apples

The overloaded eat(String s) method is invoked.

Animal a2 = new Animal(); a2.eat ("treats");
Compier error! Compiler sees that Animal class doesn't have an eat() method that takes a String.

Animal ah2 = new Horse(); ah2.eat("Carrots");
Compiler error! Compiler still looks only at the reference, and sees that Animal doesn't have an eat() method that takes a String. Compiler doesn't care that the actual object might be a Horse at runtime.




Exam Watch
Don't be fooled by a method that's overloaded but not overridden by a subclass. It's perfectly legal to do the following:

public class Foo {
void doStufff() { }
}
class Bar extends Foo {
void doStuff(String s) { }
}

The Bar class has two dostuff () methods: the no-arg version it inherits from Foo (and does not override), and the overloaded dostuff (string s) defined in the Bar class. Code with a reference to a Foo can invoke only the no-arg version, but code with a reference to a Bar can invoke either of the overloaded versions.

All about Overloading

The rules are simple:

Overloaded methods MUST change the argument list.

Overloaded methods CAN change the return type.

Overloaded methods CAN change the access modifier.

Overloaded methods CAN declare new or broader checked exceptions.

A method can be overloaded in the same class or in a subclass. In other words, if class A defines a dostuff(int i) method, the subclass B could define a dostuff (String s) method without overriding the superclass version that takes an int. So two methods with the same name but in different classes can still be considered overloaded, if the subclass inherits one version of the method and then declares another overloaded version in its class definition.

Very Important concept about overriding

If a method is overridden but you use a polymorphic (supertype) reference to refer to the subtype object with the overriding method, the compiler assumes you're calling the supertype version of the method. If the supertype version declares a checked exception, but the overriding subtype method does not, the compiler still thinks you are calling a method that declares an exception (more in Chapter 5). Let's take a look at an example:

class Animal {
public void eat() throws Exception {
// throws an Exception
}
}
class Dog2 extends Animal {
public void eat() { // no Exceptions }
public static void main(String [] arga) {
Animal a = new Dog2();
Dog2 d = new Dog2();
d.eat(); // ok
a.eat(); // compiler error -
// unreported exception
}
}

This code will not compile because of the Exception declared on the Animal eat() method. This happens even though, at runtime, the eat() method used would be the Dog version, which does not declare the exception.

All about overriding

The rules for overriding a method are as follows:

The argument list must exactly match that of the overridden method. If they don't match, you can end up with an overloaded method you didn't intend.

The return type must be the same as, or a subtype of, the return type declared in the original overridden method in the superclass. (More on this in a few pages when we discuss covariant returns.)

The access level can't be more restrictive than the overridden method's.

The access level CAN be less restrictive than that of the overridden method.

Instance methods can be overridden only if they are inherited by the subclass. A subclass within the same package as the instance's superclass can override any superclass method that is not marked private or final. A subclass in a different package can override only those non-final methods marked public or protected (since protected methods are inherited by the subclass).

The overriding method CAN throw any unchecked (runtime) exception, regardless of whether the overridden method declares the exception. (More in Chapter 5.)

The overriding method must NOT throw checked exceptions that are new or broader than those declared by the overridden method. For example, a method that declares a FileNotFoundException cannot be overridden by a method that declares a SQLException, Exception, or any other non-runtime exception unless it's a subclass of FileNotFoundException.

The overriding method can throw narrower or fewer exceptions. Just because an overridden method "takes risks" doesn't mean that the overriding subclass' exception takes the same risks. Bottom line: an overriding method doesn't have to declare any exceptions that it will never throw, regardless of what the overridden method declares.

You cannot override a method marked final.

You cannot override a method marked static. We'll look at an example in a few pages when we discuss static methods in more detail.

If a method can't be inherited, you cannot override it. Remember that overriding implies that you're reimplementing a method you inherited! For example, the following code is not legal, and even if you added an eat() method to Horse, it wouldn't be an override of Animal's eat() method.

public class TestAnimals {
public static void main (String [] args) {
Horse h = new Horse();
h.eat(); // Not legal because Horse didn't inherit eat()
}
}
class Animal {
private void eat() {
System.out.println("Generic Animal Eating Generically");
}
}
class Horse extends Animal { }

Overriding and Exceptions

The overriding method CAN throw any unchecked (runtime) exception, regardless of whether the overridden method declares the exception.

The overriding method must NOT throw checked exceptions that are new or broader than those declared by the overridden method. For example, a method that declares a FileNotFoundException cannot be overridden by a method that declares a SQLException, Exception, or any other non-runtime exception unless it's a subclass of FileNotFoundException.

The overriding method can throw narrower or fewer exceptions. Just because an overridden method "takes risks" doesn't mean that the overriding subclass' exception takes the same risks. Bottom line: an overriding method doesn't have to declare any exceptions that it will never throw, regardless of what the overridden method declares.

using NaN

Not A Number

"NaN" stands for "not a number". "Nan" is produced if a floating point operation has some input parameters that cause the operation to produce some undefined result. For example, 0.0 divided by 0.0 is arithmetically undefined. Taking the square root of a negative number is also undefined.

0.0 / 0.0 -> NaN
Math.sqrt(-2.0) -> NaN
Operations involving NaN

Double.NaN + Double.NaN -> NaN
Float.NaN + 2.0 -> NaN
Float.NaN * 3.0 -> NaN
(0.0 / 0.0) * Float.POSITIVE_INFINITY -> NaN
Math.abs(0.0 / 0.0) -> NaN
(int) (Double.NaN) -> 0
All boolean operations involving "NaN" results in a false value.

Double.NaN > 1.0 -> false
Double.NaN < 1.0 -> false
Double.NaN == 1.0 -> false
Float.NaN < -3.0 -> false
Float.NaN > Float.POSITIVE_INFINITY -> false
Float.NaN < Float.POSITIVE_INFINITY -> false
(0.0 / 0.0) == (0.0 / 0.0) -> false

Double d1 = Double.NaN;
Double d2 = Double.NaN;


System.out.println(d1 == d2);
System.out.println(d1 == Double.NaN);
System.out.println(Double.NaN == Double.NaN);


Ans : false
false
false

Summary : All boolean operations involving "NaN" results in a false value.

Nice Ques (Asked in Nucleus Software Written Test)

if(new Boolean("true") == new Boolean("true")){
System.out.println("True");
}else{
System.out.println("False");
}

Ans : False

Static Override (Asked in Nucleus Software written Test)

A static method can not override a non static method.
Also, a non static method can not override a static method.
We'll get compile time error in both cases.

Adobe interview Ques (4th Jan 10)

public class GreatQues {

public static void main(String[] args) {

int a = 10;
int b =20;

System.out.println("Sum of the numbers : " + a + b);
//System.out.println("Diff of the numbers : " + a - b); // (Line 1) Compile time error
System.out.println("Product of the numbers : " + a * b);
System.out.println("Division of the numbers : " + a / b);

short x = 127;
short y = 140;
//short z = x + y; // Compile time error (Line 2)
System.out.println(127 + 140);


}

}

Output :

Sum of the numbers : 1020
Product of the numbers : 200
Division of the numbers : 0
267


Explanation :

When we write sysout ( String + some integer), the compiler treats that interger as a String only and just appends the value to the String.
- operator is not overloaded in String, therefore, the Line 1 gives compile time error saying : - operator is undefined for arguments of type String and int.

Line 2 gives compile time error because any mathematical operation on two shorts / ints / bytes always gives int as result.

Mind Blowing Puzzle

Puzzle : There are 50 1-cent coins on the table. Initially all coins are tails up. Close your eyes, and I will turn over 10 random coins. The task is to divide all the coins into two groups blindly, so that the groups have an equal number of heads up.

Solution : We r sure that there r 10 heads in the group ..
So separate 10 random coins to form a group.. and remaining 40 will be in another group.. So if there are x heads in 10grp there will b 10-x heads in 40grp..
ie, the no of tails in 10grp is equal to the no of heads in 40grp..
So if u flip all the coins in 10grp all the tails will become heads and finally now both groups have same number of heads..

http://geniusbeauty.com/mental-beauty/brain-game-how-to-become-a-psychic/

Basic UNIX commands

ls -> List all files
ls-l -> Lists files in long format; e.g. the exact size of the file, who owns the file and who has the right to look at it, and when it was last modified.
ls-a -> Lists all files including those whose name starts with a .(dot)

How to connect two databases

If the two databases are on the same server you can reference either one in the other by using the fully qualified object name: [database].[owner].[object]

Java Implementation of Circular Queue

public class CircularQueue {

int[] cirQueue;

int front;

int rear;

// int size;
public CircularQueue(int size) {
cirQueue = new int[size];
front = rear = -1;
}

public static void main(String[] args) {
CircularQueue myQueue = new CircularQueue(5);
myQueue.insert(1);
myQueue.insert(2);
myQueue.insert(3);
myQueue.insert(4);
myQueue.insert(5);
myQueue.delete();
myQueue.insert(6);
myQueue.display();

}

public void delete() {
if (front == rear ) {
System.out.println("Can not delete from empty Queue");
return;
}else{
if(front==cirQueue.length)
front=0;
else
front++;
}
}

public void insert(int value) {
if ((rear + 1 == front) || (front == 0 && rear == cirQueue.length - 1)) {
System.out.println("Cant add ... Queue is full ");
return;
} else {
if (rear == cirQueue.length - 1) {
rear = 0;
}else{
rear++;
}
cirQueue[rear] = value;
}
if(front==-1)
front=0;
}

public void display(){
if(front > rear){
for(int i = front; i < cirQueue.length ; i++){
System.out.println(cirQueue[i]);
}
for(int i = 0 ; i < rear ; i++){
System.out.println(cirQueue[i]);
}
}else{
for(int i = front ; i < rear ; i++){
System.out.println(cirQueue[i]);
}
}
}
}

My Hanoi Prog

public class TowerOfHanoi {

static int moves = 0;
public static void main(String[] args) {
char fromPole = 'A';
char toPole = 'B';
char withPole = 'C';
hanoi(3, fromPole, toPole, withPole);
}
public static void hanoi(int height , char fromPole , char toPole , char withPole){
if(height >= 1){
hanoi(height - 1, fromPole, withPole ,toPole);
move(fromPole , toPole);
hanoi(height - 1,withPole,toPole , fromPole );
}
}
public static void move(char fromPole , char toPole){
moves++;
System.out.println("****Next Move****");
System.out.print(fromPole+ "-->");
System.out.println(toPole);
}
}


Output is :
****Next Move****
A-->B
****Next Move****
A-->C
****Next Move****
B-->C
****Next Move****
A-->B
****Next Move****
C-->A
****Next Move****
C-->B
****Next Move****
A-->B

Java Program for Tower of Hanoi problem (Very Simple and Easy solution)

This program implements the ``classical'' recursive algorithm that solves the Towers of Hanoi problem. The recursive algorithm is based on the observation that moving a tower of height h from pole A to pole B is equivalent to moving a tower of height h-1 to pole C, them moving the last disk from pole A to pole B, and finally moving the the tower from pole C to B. So the problem of moving a tower of height h, has been reduced to the one of moving a tower of height h-1.
The following Java application uses only one class variable, moves, which holds the number of moves so far. The variable is used only for formating purposes.

<*>=

import java.io.*;

public class hanoiA
{
static int moves=0; //number of moves so far




}

This code is written to a file (or else not used).
Method getInt is used to read an integer from the user terminal. The method is based on the new API therefore the whole program cannot be executed with an old JDK. Its functionality is very simple: it reads an input line which is supposed to contain only one integer. If the line contains what should contain it transforms the line into a valid integer and return it, otherwise it returns the number 1 and print an error message.

=
static int getInt()
{
String line;
BufferedReader in =
new BufferedReader(new InputStreamReader(System.in));
try
{
line = in.readLine();
int i = Integer.valueOf(line).intValue();
return i;
}
catch (Exception e)
{
System.err.println("***Error: Input is not a number.\n" +
"Input assumed to be the number 1");
return 1;
}
}

Used above.
Method hanoi is the kernel of the program---it ``performs'' the moves. It accepts four arguments: the height of the current tower, the fromPole, the toPole and the withPole. Initially the tower has height, say n. Then we must move a tower of height n-1 from fromPole to withPole, move the biggest disk from fromPole to toPole and finally move the tower of height n-1 to pole toPole from withPole. The first step is implemented as a call to the method itself (procedures are called methods in Java), the second to a call to method moveDisk, and finally the third step to a call to the itself. Particularly, the withPole is the pole we move the tower of height n-1.

Each recursive method must have a termination condition, i.e., a condition that signals the termination of the method, or else it will never terminate! In our case this condition is reached when the height of the tower is zero.

=
static void hanoi(int height,
char fromPole,
char toPole,
char withPole)
{
if (height >= 1)
{
hanoi(height-1, fromPole, withPole, toPole);
moveDisk(fromPole, toPole);
hanoi(height-1, withPole, toPole, fromPole);
}
}

Used above.
Method moveDisk simply print on the terminal each move. A ``move'' is defined by the orientation pole and the destination pole, each represented by a character. The method prints a string of the form ``FT'' where ``F'' denotes the orientation pole and ``T'' the destination pole. Moreover, it tries to make the output readable. So, it prints only twenty moves per line, by detecting multiples of the number 20.

=
static void moveDisk(char fromPole, char toPole)
{
moves++;
System.out.print(fromPole);
System.out.print(toPole);
System.out.print(((moves % 20)==0) ? '\n' : ' ');
}

Used above.
Method main is there where the whole action is. The first thing is to define the poles as characters and to the height of the tower as an integer. Next, it reads the height of the tower (in case we type some rubbish or a negative number, the height is assumed equal to 1). Finally, it prints out the solution. The last aspect of this program is that it print its execution time in milliseconds.

=
public static void main(String[] args)
{
long time1, time2; //for benchmarking
int TowerHeight;
char FromPole='A', ToPole='B', WithPole='C';

System.out.println("Enter Tower height...");
System.out.print("?");
TowerHeight = getInt();
time1 = System.currentTimeMillis();
hanoi(TowerHeight, FromPole, ToPole, WithPole);
time2 = System.currentTimeMillis();
System.out.println();
System.out.print(time2-time1); //print execution time in msec
System.out.println(" msec execution time");
}

What is Virtual Memory

Virtual memory is a common part of most operating systems on desktop computers. It has become so common because it provides a big benefit for users at a very low cost.

Most computers today have something like 64 or 128 megabytes of RAM (random-access memory) available for use by the CPU (central processing unit). Often, that amount of RAM is not enough to run all of the programs that most users expect to run at once. For example, if you load the Windows operating system, an e-mail program, a Web browser and word processor into RAM simultaneously, 64 megabytes is not enough to hold it all. If there were no such thing as virtual memory, your computer would have to say, "Sorry, you cannot load any more applications. Please close an application to load a new one." With virtual memory, the computer can look for areas of RAM that have not been used recently and copy them onto the hard disk. This frees up space in RAM to load the new application. Because it does this automatically, you don't even know it is happening, and it makes your computer feel like is has unlimited RAM space even though it has only 32 megabytes installed. Because hard-disk space is so much cheaper than RAM chips, virtual memory also provides a nice economic benefit.

The area of the hard disk that stores the RAM image is called a page file. It holds pages of RAM on the hard disk, and the operating system moves data back and forth between the page file and RAM. (On a Windows machine, page files have a .SWP extension.)

Of course, the read/write speed of a hard drive is much slower than RAM, and the technology of a hard drive is not geared toward accessing small pieces of data at a time. If your system has to rely too heavily on virtual memory, you will notice a significant performance drop. The key is to have enough RAM to handle everything you tend to work on simultaneously. Then, the only time you "feel" the slowness of virtual memory is in the slight pause that occurs when you change tasks. When you have enough RAM for your needs, virtual memory works beautifully. When you don't, the operating system has to constantly swap information back and forth between RAM and the hard disk. This is called thrashing, and it can make your computer feel incredibly slow.

Fibonacci series -> w/o using recursion

// Print out the first N Fibonacci numbers in the order:
// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765
public static final void printFib(final int N) {

int f0 = 0;
int f1 = 1;

for (int i = 0; i < N; ++i) {
System.out.println(f0);

final int temp = f1;
f1 += f0;
f0 = temp;
}
}

Given a positive number, write a prog to find next multiple of 8

public class NextMultipleOfEight {

public static void main(String[] args) {
int x = 22;
System.out.println((x/8+1) << 3);
}

}

Prog to find if a machine is Little Endian or Big Endian

import java.nio.ByteOrder;

public class FindEndianness {

public static void main(String[] args) {
ByteOrder b = ByteOrder.nativeOrder();
if(b.equals(ByteOrder.BIG_ENDIAN)){
System.out.println("Big Endian");
}else if(b.equals(ByteOrder.LITTLE_ENDIAN)){
System.out.println("Little Endian");
}
}

}

BFS prog for the Graph in the last blog

public void bfs() // breadth-first search
{ // begin at vertex 0
vertexList[0].wasVisited = true; // mark it
displayVertex(0); // display it
theQueue.insert(0); // insert at tail
int v2;
while( !theQueue.isEmpty() ) // until queue empty,
{
int v1 = theQueue.remove(); // remove vertex at head
// until it has no unvisited neighbors
while( (v2=getAdjUnvisitedVertex(v1)) != -1 )
{ // get one,
vertexList[v2].wasVisited = true; // mark it
displayVertex(v2); // display it
theQueue.insert(v2); // insert it
} // end while
} // end while(queue not empty)
// queue is empty, so we're done
for(int j=0; j< totalVertices; j++) // reset flags
vertexList[j].wasVisited = false;
} // end bfs()

The Complete Graph Class (including DFS prog)

import java.util.Stack;




public class Graph {

private final int MAX_VERTS = 20;
private Vertex[] vertexList;
private int totalVertices;
private int adjMat[][];

public Graph(){
vertexList = new Vertex[MAX_VERTS];
adjMat = new int[MAX_VERTS][MAX_VERTS];
totalVertices = 0;

for(int i = 0 ; i < MAX_VERTS ; i++){
for(int j = 0 ; j < MAX_VERTS ; j++){
adjMat[i][j] = 0;
}
}
}

public int getAdjUnvisitedVertex(int v){
if(v >= 0 && v< MAX_VERTS){
for(int i = 0 ; i < MAX_VERTS ; i++){
if(adjMat[v][i] == 1 && vertexList[i].visited == false){
return i;
}
}
}
return -1;
}
public void addVertex(char lab){
vertexList[totalVertices++] = new Vertex(lab);
}

public void dfs(){
vertexList[0].visited = true;
Stack dfsStack = new Stack();
dfsStack.push(0);
displayVertex(0);

while(!dfsStack.isEmpty()){
Integer currrent = dfsStack.peek();
int adjVe = this.getAdjUnvisitedVertex(currrent);
if(adjVe >= 0){
vertexList[adjVe].visited = true;
dfsStack.push(adjVe);
displayVertex(adjVe);
}else{
dfsStack.pop();
}

}
for(int j=0; j< totalVertices; j++) // reset flags
vertexList[j].visited = false;

}

public void addEdge(int start , int end){
adjMat[start][end] = 1;
adjMat[end][start] = 1;
}

public void displayVertex(int v){
if(v >= 0 && v < MAX_VERTS){
System.out.println(vertexList[v].label);
}
}
}
class Vertex{
public char label;
public boolean visited;

public Vertex(char lab){
label = lab;
visited = false;
}
}

Main Class :


public class GraphMain {

/**
* @param args
*/
public static void main(String[] args) {
Graph g = new Graph();
g.addVertex('A'); //0
g.addVertex('B'); //1
g.addVertex('C'); //2
g.addVertex('D'); //3
g.addVertex('E'); //4
g.addVertex('F'); //5
g.addVertex('G'); //6


g.addEdge(0, 1); // AB
g.addEdge(1, 2); // BC
g.addEdge(0, 3); // AD
g.addEdge(3, 4); // DE
g.addEdge(5, 6); // DE

System.out.print("Visits: ");
g.dfs(); // depth-first search
System.out.println();

}

}

HashMap vs Hashtable vs HashSet

Hashtable

Hashtable is basically a datastructure to retain values of key-value pair.

It didn’t allow null for both key and value. You will get NullPointerException if you add null value.
It is synchronized. So it comes with its cost. Only one thread can access in one time.

HashMap

Like Hashtable it also accepts key value pair.

It allows null for both key and value (It allows only one null key and multiple null values)
It is unsynchronized. So come up with better performance

HashSet

HashSet does not allow duplicate values. It provides add method rather put method. You also use its contain method to check whether the object is already available in HashSet. HashSet can be used where you want to maintain a unique list.

Complete + Easy + My MergeSort

public class MyMergeSort {

/**
* @param args
*/
public static void main(String[] args) {
int[] arr = { 14, 23, 76, 32, 76, 12, 11, 90 };
mergeSort(arr , 0 ,arr.length);
for(int i = 0 ; i < arr.length ; i ++){
System.out.println(arr[i]);
}
}

public static void mergeSort(int[] input , int firstIndex , int lastIndex){
int leftHalfSize;
int rightHalfSize;
if(lastIndex > 1){
leftHalfSize = lastIndex / 2;
rightHalfSize = lastIndex - leftHalfSize;

mergeSort(input, firstIndex, leftHalfSize);
mergeSort(input, firstIndex + leftHalfSize, rightHalfSize);

merge(input , firstIndex , leftHalfSize , rightHalfSize);
}

}
public static void merge(int[] input , int firstIndex , int leftHalfSize , int rightHalfSize){
int[] temp = new int[leftHalfSize + rightHalfSize];

int[] leftArray = new int[leftHalfSize];
int[] rightArray = new int[rightHalfSize];

for(int i = 0 ; i < leftHalfSize ; i++){
leftArray[i] = input[firstIndex + i];
}
for(int j = 0 ; j < rightHalfSize ; j++){
rightArray[j] = input[firstIndex + leftHalfSize + j ];
}
int i = 0 , j = 0 ,k = 0;
for(; i < leftHalfSize && j < rightHalfSize ;){
if(leftArray[i] < rightArray[j]){
temp[k] = leftArray[i];
i++;
k++;
}else{
temp[k] = rightArray[j];
j++;
k++;
}
}
if(i < leftHalfSize){
while (i < leftHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = leftArray[i];
k++;
i++;
}
}

if(j < rightHalfSize){
while (j < rightHalfSize || k < leftHalfSize + rightHalfSize){
temp[k] = rightArray[j];
k++;
j++;
}
}
for(int m = 0 ; m < leftHalfSize + rightHalfSize ; m++){
input[firstIndex+ m ] = temp[m] ;
}
}

}

Merge Sort -> Complete Prog

public class MergeSort
{
private int a[];

public MergeSort(int b[])
{
a = b;
}
public void sort()
{
if(a.length <= 1)
return;
int first[] = new int[a.length / 2];
int second[] = new int[a.length - first.length];
for(int x = 0; x < first.length; x++)
first[x] = a[x];
for(int x = first.length, y = 0; x < a.length; x++, y++)
first[y] = a[x];
//Split the array again
MergeSort sort1 = new MergeSort(first);
MergeSort sort2 = new MergeSort(second);
sort1.sort();
sort2.sort();

merge(first, second);
}
private void merge(int first[], int second[])
{
int x = 0;
int y = 0;
int z = 0;
while(x < first.length && y < second.length)
{
if(first[x] < second[y])
{
a[z] = first[x];
x++;
}
else
{
a[z] = second[y];
y++;
}
z++;
}
//copy remaining elements to the tail of a[];
for(int i = x; i < first.length; i++)
{
a[z] = first[i];
z++;
}
for(int i = y; i < second.length; i++)
{
a[z] = second[i];
z++;
}
}
}

Merge Sort -> Merge + MergeSort

public static int[] merge(int[] a, int[] b){
int len1 = a.length;
int len2 = b.length;
int[] c = new int[len1 + len2];
int len = len1 < len2 ? len1 : len2;
int i = 0 , j = 0 , k = 0;
for(; i < len1 && j < len2 && k < len1 + len2 ; ){
if(a[i] < b[j]){
c[k] = a[i];
k++;
i++;
}else{
c[k] = b[j];
k++;
j++;
}
}

if(i < len1){
while (i != len1 || k != len1 + len2){
c[k] = a[i];
k++;
i++;
}
}

if(j < len2){
while (j != len2 || k != len1 + len2){
c[k] = b[j];
k++;
i++;
}
}

return c;
}

Stable Sort

• A sort is stable if the order of elements with the same key is retained.

Insertion Sort

public static int[] insertionSort(int[] arr){
int len = arr.length;
for(int i = 0 ; i < len ; i++){
for(int j = 0 ; j < i ; j++){
if(arr[i] < arr[j]){
int temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;

}
}
}

return arr;
}

Selection Sort

public static int[] selectionSort(int[] arr){
int len = arr.length;

for (int i = 0 ; i < len ; i++){
int min = arr[i];
for(int j = i + 1 ; j < len ; j++){
if(min > arr[j]){
int temp = arr[j];
arr[j] = min;
min = temp;
arr[i] = min;
}
}

}
return arr;
}

Bubble Sort

public static int[] bubbleSort(int[] arr) {
int len = arr.length;

for (int i = len - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
}