Abstract
Software design patterns have roots in the architectural patterns
of Christopher Alexander, and in the object movement. According
to Alexander, patterns repeat themselves, since they are a generic
solution to a given system of forces. The object movement looks
to the real world for insights into modeling software relationships.
With these dual roots, it seems reasonable that software design
patterns should be repeated in real world objects. This paper
presents a real world, non software instance of each design pattern
from the book, Design Patterns - Elements of Reusable Object-Oriented
Software [13]. The paper also discusses the implications
of non-software examples on the communicative power of a pattern
language, and on design pattern training.
1. Introduction
Within the software industry, a growing community of patterns
proponents exists. The roots of the patterns movement are found
in the writings of architect Christopher Alexander, who describes
a pattern as a generic solution to a given system of forces in
the world [1]. Alexander's patterns can be observed in everyday
structures. Each pattern in A Pattern Language[2] includes
a picture of an archetypal example of the pattern.
Since objects were the predominate world view at the time that
patterns were embraced by the software world, patterns also have
roots in the object movement [9]. Unfortunately examples of software
design patterns are not as abundant as Alexandrian patterns, since
they represent elegant designs, rather than the designs that people
generate initially [13]. Access to elegant designs is often limited
due to the proprietary nature of much of the software being developed
today.
According to Alexander, real world patterns always repeat themselves,
because under a given set of circumstances, there are always certain
fields of relationships which are most nearly well adapted to
the forces which exist [1]. In software, real world problems
are either modeled entirely, or real world objects are transformed
into hardware and software to produce real world results [5].
Since software design patterns have roots in both Alexandrian
patterns, and in the object movement, it seems logical that software
design patterns can be found in real world objects. This is not
to say that software design patterns are necessarily models of
the real world objects, but the relationships between objects
that have been adapted to deal with certain forces can be observed
both in the "real world" and in software objects. To
test this hypothesis, a real world example was sought for each
of the 23 Gang of Four Patterns [13]. The examples follow in
sections 2 through 4.
2. Creational Patterns
Five creational patterns have been documented by the Gang of Four.
Examples of these creational patterns can be found in manufacturing,
fast food, biology and political institutions.
2.1 Abstract Factory Example
The purpose of the Abstract Factory is to provide
an interface for creating families of related objects, without
specifying concrete classes. This pattern is found in the sheet
metal stamping equipment used in the manufacture of Japanese automobiles.
The stamping equipment is an Abstract Factory which creates
auto body parts. The same machinery is used to stamp right hand
doors, left hand doors, right front fenders, left front fenders,
hoods etc. for different models of cars. Through the use of rollers
to change the stamping dies, the concrete classes produced by
the machinery can be changed within three minutes [16].
2.2 Builder Example
The Builder pattern separates the construction of a complex
object from its representation, so that the same construction
process can create different representation. This pattern is
used by fast food restaurants to construct children's meals.
Children's meals typically consist of a main item, a side item,
a drink, and a toy (e.g., a hamburger, fries, coke, and toy car).
Note that there can be variation in the contents of the children's
meal, but the construction process is the same. Whether a customer
orders a hamburger, cheeseburger, or chicken, the process is the
same. The employee at the counter directs the crew to assemble
a main item, side item, and toy. These items are then placed
in a bag. The drink is placed in a cup and remains outside of
the bag. This same process is used at competing restaurants.
2.3 Factory Method Example
The Factory Method defines an interface for creating objects,
but lets subclasses decide which classes to instantiate. Injection
molding presses demonstrate this pattern. Manufacturers of plastic
toys process plastic molding powder, and inject the plastic into
molds of the desired shapes [15]. The class of toy (car, action
figure, etc.) is determined by the mold.
2.4 Prototype Example
The Prototype pattern specifies the kind of objects to
create using a prototypical instance. Prototypes of new products
are often built prior to full production, but in this example,
the prototype is passive, and does not participate in copying
itself. The mitotic division of a cell, resulting in two identical
cells, is an example of a prototype that plays an active role
in copying itself and thus, demonstrates the Prototype pattern.
When a cell splits, two cells of identical genotype result.
In other words, the cell clones itself.
2.5 Singleton Example
The Singleton pattern ensures that a class has only one
instance, and provides a global point of access to that instance.
The Singleton pattern is named after the singleton set,
which is defined to be a set containing one element. The office
of the President of the United States is a Singleton. The
United States Constitution specifies the means by which a president
is elected, limits the term of office, and defines the order of
succession. As a result, there can be at most one active president
at any given time. Regardless of the personal identity of the
active president, the title, "The President of the United
States" is a global point of access that identifies the person
in the office.
3. Structural Patterns
Seven structural patterns have been documented by the Gang of
Four. Examples of these patterns can be found in hand tools,
residential wiring, mathematics, holiday tradition, catalog retail,
and banking.
3.1 Adapter Example
The Adapter pattern allows otherwise incompatible classes
to work together by converting the interface of one class into
an interface expected by the clients. Socket wrenches provide
an example of the Adapter. A socket attaches to a ratchet,
provided that the size of the drive is the same. Typical drive
sizes in the United States are 1/2" and 1/4". Obviously
a 1/2" drive ratchet will not fit into a 1/4" drive
socket unless an adapter is used. A 1/2" to 1/4" adapter
has a 1/2" female connection to fit on the 1/2" drive
ratchet, and a 1/4" male connection to fit in the 1/4"
drive socket.
3.2 Bridge Example
The Bridge pattern decouples an abstraction from its implementation,
so that the two can vary independently. A household switch controlling
lights, ceiling fans, etc. is an example of the Bridge.
The purpose of the switch is to turn a device on or off. The
actual switch can be implemented as a pull chain, a simple two
position switch, or a variety of dimmer switches.
3.3 Composite Example
The Composite composes objects into tree structures, and
lets clients treat individual objects and compositions uniformly.
Although the example is abstract, arithmetic expressions are
Composites. An arithmetic expression consists of an operand,
an operator (+ - * /), and another operand. The operand can be
a number, or another arithmetic expression. Thus, 2 + 3 and (2
+ 3) + (4 * 6) are both valid expressions.
3.4 Decorator Example
The Decorator attaches additional responsibilities to an
object dynamically. Although paintings can be hung on a wall
with or without frames, frames are often added, and it is the
frame which is actually hung on the wall. Prior to hanging, the
paintings may be matted and framed, with the painting, matting,
and frame forming a single visual component.
3.5 Facade Example
The Facade defines a unified, higher level interface to
a subsystem, that makes it easier to use. Consumers encounter
a Facade when ordering from a catalog. The consumer calls
one number and speaks with a customer service representative.
The customer service representative acts as a Facade,
providing an interface to the order fulfillment department, the
billing department, and the shipping department.
3.6 Flyweight Example
The Flyweight uses sharing to support large numbers of
objects efficiently. The public switched telephone network is
an example of a Flyweight. There are several resources
such as dial tone generators, ringing generators, and digit receivers
that must be shared between all subscribers. A subscriber is
unaware of how many resources are in the pool when he or she lifts
the hand set to make a call. All that matters to subscribers
is that dial tone is provided, digits are received, and the call
is completed.
3.7 Proxy Example
The Proxy provides a surrogate or place holder to provide
access to an object. A check or bank draft is a proxy for funds
in an account. A check can be used in place of cash for making
purchases and ultimately controls access to cash in the issuer's
account.
4. Behavioral Patterns
Eleven behavioral patterns have been documented by the Gang of
Four. Examples of these patterns can be found in coin sorting
banks, restaurant orders, music, transportation, auto repair,
vending machines, and home construction.
4.1 Chain of Responsibility Example
The Chain of Responsibility pattern avoids coupling the
sender of a request to the receiver, by giving more than one object
a chance to handle the request. Mechanical coin sorting banks
use the Chain of Responsibility. Rather than having a
separate slot for each coin denomination coupled with receptacle
for the denomination, a single slot is used. When the coin is
dropped, the coin is routed to the appropriate receptacle by the
mechanical mechanisms within the bank.
4.2 Command Example
The Command pattern allows requests to be encapsulated
as objects, thereby allowing clients to be paramaterized with
different requests. The "check" at a diner is an example
of a Command pattern. The waiter or waitress takes an
order, or command from a customer, and encapsulates that order
by writing it on the check. The order is then queued for a short
order cook. Note that the pad of "checks" used by
different diners is not dependent on the menu, and therefore they
can support commands to cook many different items.
4.3 Interpreter Example
The Interpreter pattern defines a grammatical representation
for a language and an interpreter to interpret the grammar.
Musicians are examples of Interpreters. The pitch of a
sound and its duration can be represented in musical notation
on a staff. This notation provides the language of music [14].
Musicians playing the music from the score are able to reproduce
the original pitch and duration of each sound represented.
4.4 Iterator Example
The Iterator provides ways to access elements of an aggregate
object sequentially without exposing the underlying structure
of the object. On early television sets, a dial was used to
change channels. When channel surfing, the viewer was required
to move the dial through each channel position, regardless of
whether or not that channel had reception. On modern television
sets, a next and previous button are used. When the viewer selects
the "next" button, the next tuned channel will be displayed.
Consider watching television in a hotel room in a strange city.
When surfing through channels, the channel number is not important,
but the programming is. If the programming on one channel is
not of interest, the viewer can request the next channel, without
knowing its number.
4.5 Mediator Example
The Mediator defines an object that controls how a set
of objects interact. Loose coupling between colleague objects
is achieved by having colleagues communicate with the Mediator,
rather than with each other. The control tower at a controlled
airport demonstrates this pattern very well. The pilots of the
planes approaching or departing the terminal area communicate
with the tower, rather than explicitly communicating with one
another. The constraints on who can take off or land are enforced
by the tower. It is important to note that the tower does not
control the whole flight. It exists only to enforce constraints
in the terminal area.
4.6 Memento Example
The Memento captures and externalizes an object's internal
state, so the object can be restored to that state later. This
pattern is common among do-it-yourself mechanics repairing drum
brakes on their cars. The drums are removed from both sides,
exposing both the right and left brakes. Only one side is disassembled,
and the other side serves as a Memento of how the brake
parts fit together [8]. Only after the job has been completed
on one side is the other side disassembled. When the second side
is disassembled, the first side acts as the Memento.
4.7 Observer Example
The Observer defines a one to many relationship, so that
when one object changes state, the others are notified and updated
automatically. Some auctions demonstrate this pattern. Each
bidder possesses a numbered paddle that is used to indicate a
bid. The auctioneer starts the bidding, and "observes"
when a paddle is raised to accept the bid. The acceptance of
the bid changes the bid price, which is broadcast to all of the
bidders in the form of a new bid.
4.8 State Example
The State pattern allows an object to change its behavior
when its internal state changes. This pattern can be observed
in a vending machine. Vending machines have states based on the
inventory, amount of currency deposited, the ability to make change,
the item selected, etc. When currency is deposited and a selection
is made, a vending machine will either deliver a product and no
change, deliver a product and change, deliver no product due to
insufficient currency on deposit, or deliver no product due to
inventory depletion.
4.9 Strategy Example
A Strategy defines a set of algorithms that can be used
interchangeably. Modes of transportation to an airport is an
example of a Strategy. Several options exist, such as driving
one's own car, taking a taxi, an airport shuttle, a city bus,
or a limousine service. For some airports, subways and helicopters
are also available as a mode of transportation to the airport.
Any of these modes of transportation will get a traveler to the
airport, and they can be used interchangeably. The traveler must
chose the Strategy based on tradeoffs between cost, convenience,
and time.
4.10 Template Method Example
The Template Method defines a skeleton of an algorithm
in an operation, and defers some steps to subclasses. Home builders
use the Template Method when developing a new subdivision.
A typical subdivision consists of a limited number of floor plans,
with different variations available for each floor plan. Within
a floor plan, the foundation, framing, plumbing, and wiring will
be identical for each house. Variation is introduced in the latter
stages of construction to produce a wider variety of models.
4.11 Visitor Example
The Visitor pattern represents an operation to be performed
on the elements of an object structure, without changing the classes
on which it operates. This pattern can be observed in the operation
of a taxi company. When a person calls a taxi company he or
she becomes part of the company's list of customers. The company
then dispatches a cab to the customer (accepting a visitor).
Upon entering the taxi, or Visitor, the customer is no
longer in control of his or her own transportation, the taxi (driver)
is.
5. Implications
Non-software examples of each of the software design patterns
cataloged by the Gang of Four have been shown to exist. One might
now wonder about the practical implications of these examples.
These non-software examples are useful in increasing the communicative
power of the pattern language and as aids to learning the patterns.
5.1 Increasing the Communicative Power of the Pattern Language
Alexander had hoped that true patterns would enter a common language
that all could share [2]. Within the software design community,
patterns are seen as a way to develop a set of languages to streamline
communication between colleagues [4,17]. Patterns are expected
to provide a vocabulary for discussing structures larger than
modules, procedures, or objects [10].
One crucial element of a language is the mental imagery associated
with symbols of the language. In a language, a given configuration
of symbols has meaning only if one can grasp its content, which
involves mentally representing it [7]. The importance of mental
imagery to pattern languages was not lost on Alexander, who stated
that a language was not morphologically complete until the types
of buildings that it generates could be visualized concretely
[1]. In software design, Richle and Z¸llighoven recognized
the importance of concrete examples in guiding our perception
of the application domain [18].
If software design patterns are to become a common language among
programmers, shared meaning is essential. If design decisions
are communicated, but not understood, designers are forced to
make missing assumptions to complete the job [19]. Commonplace
examples facilitate understanding, because in order to understand
anything, people must find the closest item in memory to which
it relates [20]. The projects at AG Communication Systems that
make extensive use of patterns often use non-software examples
to illustrate the relationships at work in the patterns. The
examples help provide a common understanding between designers.
By establishing common understanding early in the design process,
communication between designers is facilitated throughout the
project life cycle.
5.2 Non-Software Examples as Aids to Learning Patterns
Students require examples whenever new concepts are presented.
This was evident in the evaluation of a course in patterns offered
at AG Communication Systems and has also been documented by others
[12]. When learning something new, the student naturally tends
to exploit prior knowledge in an effort to understand the new
concepts [6]. For this reason, many examples should be included
when students are first exposed to software design patterns [12].
Specific examples should be ones with which the student is acquainted,
but not expert [3]. Providing acquaintance examples does not
increase the new material that must be learned. At the same time,
choosing an example outside of a student's expertise keeps the
student from getting so involved in the example that the point
of the new material is missed. Since patterns must ultimately
reside in one's own mind [11], using examples that are common
to a large cross section of people, training material can build
on examples already committed to memory.
6. Conclusion
The repetition of software design patterns in non-software examples
is evidence that patterns are not limited to a specific domain.
Instances of these patterns in everyday objects can benefit software
designers, even though the examples are not expressed in a programming
language. The examples presented in this paper are intended to
be ones that are familiar to a large cross section of people (although
some may be culturally biased towards North Americans). By drawing
on common experience, such examples facilitate understanding of
specific design patterns, and thus improve communication and serve
as an aid to learning the patterns.
A Binary heap is a simple heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:
To traverse a non-empty binary tree in preorder, perform the following operations:
(This is also called Depth-first traversal.)
To traverse a non-empty binary tree in inorder, perform the following operations:
To traverse a non-empty binary tree in postorder, perform the following operations:
Finally, trees can also be traversed in level-order, where we visit every node on a level before going to a lower level. This is also called Breadth-first traversal.
 | In this binary search tree,
|
Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family.
Although somewhat slower in practice on most machines than a good
implementation of quicksort, it has the advantages of worst-case O(n
log n) runtime. The primary advantage of the heap sort is its
efficiency. The execution time efficiency of the heap sort is O(n log
n). The memory efficiency of the heap sort, unlike the other O(nlogn)
sorts, is constant, O(1), because the heap sort algorithm is not
recursive. Heapsort is an in-place algorithm and is not a stable sort.
Ref:
http://tide4javascript.com/?s=Quicksort
delete from employee
where (empid, empssn)
not in
( select min(empid), empssn
from employee group by empssn);
Database normalization is the process of organizing data into distinct and unique sets.
The purposes of normalization are to:
The process of normalization involves determining what data should be stored in each database table.
By tradition, the process of normalization involves working through well-defined steps, called normal forms.
In First Normal Form (1NF) you eliminate duplicate columns from the
same table, create separate tables for each group of related data, and
identify each row with a unique column or set of columns (the primary
keys).
In Second Normal Form (2NF) you remove subsets of data that
apply to multiple rows of a table, place them in separate tables, and
create relationships between these new tables and the original tables
through the use of foreign keys.
In Third Normal Form (3NF) you remove columns that are not dependent upon the primary key.
Additional normal forms have been defined, but are less commonly
utilized. These advanced normal forms include Fourth Normal Form (4NF),
Fifth Normal Form (5NF), Boyce Codd Normal Form (BCNF), and Domain-Key
Normal Form (DK/NF).
Classes and Objects
1. Describe OOPs concepts.
The four main concepts are involved in OOP:
1. Abstraction
2. Encapsulation
3. Inheritance
4. Polymorphism
Abstraction
Abstraction is hiding of information from others. In case of Java, its hiding implementation of a method/ object. For example if an interface is available to outer world, so end user won't know about implementing class details. This is just a kind of abstraction. Abstraction could be anywhere in java, wherever we hide some information, we call it abstraction.
Encapsulation
Encapsulation is combining data and method along with implementation hiding within the class. Implementation hiding is done with the help of access modifiers (public, protected, package, private).
Inheritance
Inheritance is the capability of a class to use the properties and methods of another class while adding its own functionality. Although inheritance may sometimes imply (especially in Java, where the keyword for inheritance is extends) that you are going to add new methods to the interface, that's not necessarily true. The second and more important way to differentiate your new class is to change the behavior of an existing base-class method. This is referred to as overriding that method.
Polymorphism
Polymorphism is something like one name many forms. Polymorphism is also known as dynamic binding or late binding or run-time binding.
2. What is an abstract class?
You create an abstract class when you want to manipulate a set of classes through this common interface. All derived-class methods that match the signature of the base-class declaration will be called using the dynamic binding mechanism.
A class containing abstract methods is called an abstract class. Class does not contain implementation for Abstract methods. If a class contains one or more abstract methods, the class itself must be qualified as abstract. (Otherwise, the compiler gives you an error message.)
3. What is an interface?
The interface keyword takes the abstract concept one step further. You could think of it as a "pure" abstract class. It allows the creator to establish the form for a class: method names, argument lists, and return types, but no method bodies. An interface can also contain fields, but these are implicitly static and final. An interface provides only a form, but no implementation. An interface says, "This is what all classes that implement this particular interface will look like."
4. What is Polymorphism in java?
The meaning of Polymorphism is something like one name many forms. Polymorphism is also known as dynamic binding or late binding or run-time binding. In java polymorphism exists in three distinct forms
1. Method overloading
Method overloading can be done on the basis of number of argument in a method , or order of arguments or class of the function. Overloading can't be done on the basis of return type. This is because sometime methods are called only for their side effect and their return value might be ignored. E.g.
public class Test {
// First method
public void display(){}
// Second method
public void display(String msg){}
// Third method: Not allowed
public String display(){}
}
In the above example first and second display methods are overloaded on the basis of number of arguments while we can't define third display method with same arguments and different return type as compiler won't be able to differentiate that which method is called.
2. Method overriding through inheritance
overriding methods in extended class which are defined in base class. E.g.
public class ExtendedTest extends Test {
// overriding Method
public void display(String msg){}
public static void main(String[] args) {
ExtendedTest eTest = new ExtendedTest();
eTest.display("ExtendedTest");
Test test = new Test();
test.display("Test");
}
}
That means the method "display" in the "ExtendedTest" class is given more preference than " display " in the "Test" class for any " ExtendedTest " object. This is what is called overriding the methods. If there is no "display" method defined in "ExtendedTest" class then object from "ExtendedTest" will use method defined in "Test" class. That means compiler doesn't have information at compile time that which method to call. This decision is takes at run time. That is why this is called late binding or runtime binding.
3. Method overriding through the Java interface
This could be the case when we have one interface implemented by more than one java class. Let's assume that there is an interface ITest and classes TestA & TestB both implement this interface. Any statement like E.g.
ITest test1 = new TestA();
//Or
ITest test2 = new TestB();
can't be resolved at compile time. This could be resolved at runtime.
5. What is a static in java?
A class is the blueprint from which individual objects are created. We won't get anything until we create an object of that class with new and at that point we get space of data storage and handle (method) for this data.
There are two cases which don't fit in above situation. One we want only one storage of data for every object or even if no object is created. The second situation is that if we want a method that is not associated with any object. Method is directly associated with the class and operate on class data (static) only.
We can achieve both by static keyword. When we say variable or method static that means it is related with class and every instance will access same copy.
If a method is declared static then we can use only static data member inside it. Static method in super class can be overridden by static method in sub-class only. However we can't override a static method with non-static method. Static method is implicitly final.
It is not recommended to use instance name for accessing static data or method since this gives a feeling that data or method is associated with object and not with the class. But that is not the case.
6. What are transient variables?
During serialization, there might be a particular variable that you don't want Java's serialization mechanism to automatically save and restore. This is commonly the case if that variable represents sensitive information that you don't want to serialize. Even if that information is private in the object, once it has been serialized, it's possible for someone to access it by reading a file or intercepting a network transmission.
To control this, you can turn off serialization on a field-by-field basis using the transient keyword. This keyword indicates that the value of this variable doesn't have to be serialized. When the object will be de-serialized, this variable will be initialized with a default value of its data type.
String
1. Describe String in Java?
Strings are immutable. A string can't be altered once created. Applying a method on string won't change string's value; rather it will create a new string. String is also final, and so can't be sub classed. When you assign one String variable to another, no copy is made. Even when you take a substring there is no new String created.
Creating String : String can be created by assigning string literals as shown below. The text between double quotes is a string literal. By assigning a string literal, you can avoid using the new keyword. In fact, this special shortcut syntax was designed to improve String performance. Each JVM only keeps one copy of each string literal. In the following code firstStr and secondStr points to same string reference. thirdStr creates a new String in String pool.
String firstStr = "I am a String Literal";
String secondStr = "I am a String Literal";
// Points to the same object as firstString
String thirdStr = new String("I am a String Literal");
// By using constructor, It will create a new Object in JVM
Note: You almost always want to initialize String references with literals to avoid creating unnecessary objects in the JVM. This can really add up if you are creating hundreds of identical Strings.
2. What are the differences between the == operator and the equals() method?
Equals method compare values of the receiver and sender object. It returns true if the values are same. While '==' operator is a fundamental operator, it compares reference of the sender and receiver object. E.g.
String s1 = "Hello";
String s2 = "Hello";
String s3 = new String("Hello");
System.out.println(s1 == s2); // true
System.out.println(s1 == s3);// false
System.out.println(s1.equals(s2));// true
System.out.println(s1.equals(s3));// true
From the example, we can see that reference and value for s1 & s2 are same. At the same time s3 is a newly created instance which has same value as of s1 and s2 but reference is different.
3. What is String.intern()?
String.intern returns a canonical representation for the string object. A pool of strings, initially empty, is maintained privately by the class String. All literal strings and string-valued constant expressions are stored in this pool.
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals(Object) method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
It follows that for any two strings s and t, s.intern() == t.intern() is true if and only if s.equals(t) is true. By using intern one can get better performance as compared to equals method in String class. equals does the character by character that you probably want.
There are some disadvantages of intern. If we start using intern with every string then pool size will increase and could lead to memory problem. Secondly in case of bigger pool, finding a string could be more costly that having character by character comparison.
4. Which one of the following is more efficient?
a. String str1 = "Hello " + "Guest";
b. String str2 = (new StringBuffer().append("Hello ")).append("Guest")
.toString();
str1 is resolved at compile time, while str2 is resolved at runtime time with an extra StringBuffer and String. The version that can be resolved at compile time is more efficient. It avoids the overhead of creating a String and an extra StringBuffer, as well as avoiding the runtime cost of several method calls.
5. What will be output of the following program?
public static void main(String[] args) {
String s1 = new String("Hello");
change(s1);
System.out.println(s1);
}
public static void change(String s1) {
s1 += " Guest";
}
The output of the program will be "Hello" only. " Guest" won't be appended to the original string.
This is due to immutable nature of string. In the change method, appending string to s1 won't change previous string, rather it will create a new string which will be "Hello Guest" and will be pointing to some other memory location and not to the String location which is passed to the 'change' method.
Containers
1. What do you know about Containers?
There are two types of container library available in java.
1. Collection: Collection category only holds one item in each location. This includes List and Set Interfaces.
a. List (ArrayList, Vector, LinkedList): A collection of elements, duplicates allowed.
b. Set (HashSet, LinkedHashSet, TreeSet): A collection of unique elements.
2. Map: The Map holds key-value pairs, rather like a mini database. We can look up on the basis of key. This includes Map interface.
a. Map (HashMap, HashTable, LinkedHashMap, TreeMap): A mapping of keys to values.
2. What are the differences between Vector and ArrayList?
The two classes are very similar, however there are few differences, which can give one a clear idea about their usages.Vector is synchronized. Content in vector is thread-safe. ArrayList is not synchronized hence its content is not thread-safe. Synchronization is not at free of cost. It affects vector's performance. So if we don't require thread-safe data, we should use ArrayList.
Internally, both the ArrayList and vector hold data in Array. When we add a new element into ArrayList or Vector, and the object will need to expand its internal array if it runs out of memory. Vector doubles the size of Array by default, while the ArrayList increases its size by 50 percent. Vector does have slight advantage since they allow to reset increment size.Addition and deletion operation in both classes takes same time.
Addition at the end of container can be performed in constant time O(1). Deletion and Addition are more expansive when the element is added/removed from middle, it takes O(n-i). Here n is number of elements in the container and i is index of the element.
3. What are the differences between ArrayList and LinkedList?
Both classes implement List interface. Order is the most important feature of a List; it promises to maintain elements in a particular sequence. Following are the main differences
1. An ArrayList implemented with Array, allowed fast random access to an element, while LinkedList are optimal for sequential access and are relatively slow for random access.
2. ArrayList is slow when inserting or removing element from middle of the List while LinkedList provide inexpensive insertion and deletion from the middle of the List.
4. Difference between HashTable and HashMap?
The HashTable is almost equal to HashMap except following points.
1. HashTable is synchronized, while HashMap is not.
2. HashTable doesn't permit null as key while in HashMap it is allowed.
3. HashTable guarantee that order of the table will remain constant over time while in HashMap it is not.
Garbage Collector
1. What is Garbage Collection ?
Memory for the new object created in java is allocated in heap at runtime. When an object is no longer referenced by the program, the heap space it occupies must be recycled so that the space is available for subsequent new objects.
Garbage collection is the process of automatically freeing objects that are no longer referenced by the program.
During object cleaning, free memory in the heap may not be continuous, free memory may be between live objects. It's job of GC to fragment heap memory.
There are many advantages of having garbage collector
1. It increases productivity. One need not worry about memory issues.
2. It ensures program integrity. Garbage collection is an important part of Java's security strategy. Java programmers are unable to accidentally (or purposely) crash the Java virtual machine by incorrectly freeing memory.
A potential disadvantage of a garbage-collected heap is that it adds an overhead that can affect program performance. The Java virtual machine has to keep track of which objects are being referenced by the executing program, and finalize and free unreferenced objects on the fly. This activity will likely require more CPU time than would have been required if the program explicitly freed unnecessary memory. In addition, programmers in a garbage-collected environment have less control over the scheduling of CPU time devoted to freeing objects that are no longer needed.
2. How you can force the garbage collection?
We can't have forced garbage collection. System.gc( ) does not necessarily force a synchronous garbage collection. Instead, the gc( ) call is really a hint to the runtime that now is a good time to run the garbage collector. The runtime decides whether to execute the garbage collection at that time and what type of garbage collection to run.
3. What are the advantages and disadvantages of reference counting in garbage collection over tracing algorithm?
??
Both classes implement List interface. Order is the most important feature of a List; it promises to maintain elements in a particular sequence. Following are the main differences
1. An ArrayList implemented with Array, allowed fast random access to an element, while LinkedList are optimal for sequential access and are relatively slow for random access.
2. ArrayList is slow when inserting or removing element from middle of the List while LinkedList provide inexpensive insertion and deletion from the middle of the List.
Thread
1. What is a thread?
A thread is an independent path of execution within a process. Many threads can run concurrently within a process. A process is a program having its own address space.
2. What is the difference between multithreading & multitasking?
In multithreaded program, more than one thread is running concurrently. It is not equivalent to starting a program twice at the same time. If we start two or more programs at a time, this will require separate address space for both data and code, making it more CPU intensive operation. This type of program execution is called multitasking.
In multithreaded environment, sharing of data is done across the threads, which makes it less CPU intensive but brings up some other issues which may even corrupt data if not handled carefully.
Multitasking is a heavyweight task that require own address space. Communication between different processes is very expensive. Also context switching from one process to another is costly since they are running in different address spaces.
Multithreading is lightweight. Communication between two threads is not that expensive as it is in case of processes. Context switching is also less expensive as both share same address space.
3. What is synchronization?
You can think of a single threaded program which is accessing some resource at a time. You are not worried by the fact that if some other thread is accessing same resource at the same time.
With multithreaded environment there will be possibility that two or more threads are trying to access same resource at the same time. This may lead to some error. Colliding over resource must be prevented to avoid any such error.
Consider the bathroom in your house; multiple people (threads) may each want to have exclusive use of the bathroom (the shared resource). To access the bathroom, a person knocks on the door to see if it's available. If so, they enter and lock the door. Any other thread that wants to use the bathroom is "blocked" from using it, so that thread waits at the door until the bathroom is available.
In Java, to solve this problem of thread collision, all the multithreaded program should synchronize access to shared resource. This is achieved by putting a locked clause around a piece of shared code so that one thread at a time may pass through that piece of code. Serializing access of shared resource is called synchronization. Synchronization is Java is achieved by "synchronized " keyword.
Patterns
1. What are the different types of Java patterns?
Let's first understand what a design pattern is.
When a problem occurs repetitively in all application across programmers, the solution to that problem is defined as a design pattern.
Most of design patterns are language independent strategies to common object oriented problems.
Typically java has three design patterns.
1. Creational Design Pattern
As the name suggests, this pattern is all about instantiated a class and how object is managed across the program to reduce duplicate objects and unnecessary coding which might be caused by using the basic form of object creation. This pattern is again subdivided in to class creational patterns and object creational patterns. Common examples of such patterns are -
a. Factory
Delegates the work of creating the object instance to derived classes of the interface.
b. Abstract Factory
Used for creating groups of dependant instances of classes without specifying their concrete classes. It's the centralize decision of what factory to instantiate.
c. Builder
It's used to separate the instantiation of a complex object from its representation so that same construction process can be used for different representations.
d. Singleton
Ensures at every point in the application, there is only and only one instance of that class and also provides a global access point to the same.
e. Prototype
When the typical way of instantiating an object (i.e. "new") is costly. In this pattern new instances are created by copying the prototype of that class.
f. Lazy initiation
Supply when demanded. Instead of already having a created object, create only when it's required.
g. Objects pool
Recycling the objects when they are not in used, rather than releasing them and created new ones when they are required.
2. Structural Design Patterns
These are the patterns used for realizing the relationship between different entities. It defines ways to compose an object to obtain new functionality. Common examples of such patterns are:
a. Adapter/Wrapper
Its used to convert an interface into the one that client expects to see. That is, it adapts the interface to an expected class. It makes incompatible interfaces work together by wrapping them with its own interface.
b. Composite
It's used for defining a whole hierarchy tree structure of objects where each object has the same interface. This allows client to treat a group of different objects in the same way.
c. Bridge
It separates an abstraction from its implementation so that two can vary differently. That is the implemented class can be launched independently and work as its own system.
d. Decorator
Used for adding functionality to the objects at runtime. It's an alternative for sub classing. Sub classing ads functionality to an object at compile time where as decorating adds functionality at the runtime.
e. Facade
Providing an additional layer to existing subsystems to hide complexities. It makes an entry system to the sub systems.
f. Flyweight
When data is shared between numbers of objects to prevent memory consumptions. It's not possible to share all the object state data; therefore it's commonly put in external data structures to populate object's property at runtime (On the Fly).
g. Proxy
Using a mirror substitute of original object if creation of original object is time taking or memory consuming (when that memory consuming operation is not needed for this object to perform). This is often used in as a placeholder typically used in conjunction which flyweight pattern where one instance and multiple proxy are created all pointing to same reference.
2. What is singleton pattern? Write an example singleton class?
A singleton class is a class which has only one instance per application. Rather per JVM. This design pattern is extensively used when user needs exactly one instance. For example facade objects, state objects or for global variables (as it permits lazy allocation and initialization which may not happen in all languages).
To make a class singleton, its constructor is made private or protected so that it can not be instantiated. Instead, a getInstance () method is written to return a new instance of that class if it doesn't exist or return the reference of that object if it already exists. If it's a multithreaded environment make sure to synchronize the getInstance() menthod.
Conventional way of writing a singleton class is :
public class Singleton {
private final static Singleton INSTANCE = null;
// to prohibit instantiation
private Singleton() {}
public static Singleton getInstance() {
if(instance==null) {
// lazy initialisation
INSTANCE = new Singleton();
}
return INSTANCE;
}
}
You can synchronise on getInstance() method for a multi threaded environment.
Another thread-safe Java programming language lazy-loaded solution is:
public class Singleton {
private Singleton() {}
// lazy initialisation
private static class SingletonHolder {
private final static Singleton INSTANCE = new Singleton();
}
public static Singleton getInstance() {
return SingletonHolder.INSTANCE;
}
}
Remember a singleton class is one instance per JVM. So if you have your application running in a cluster of servers. Every server will have its own JVM, therefore its own instance of singleton class. In this case, purpose of making a class singleton is not fulfilled. Hence this pattern should be used with care.
