Interval - Algorithm

When to use interval
- Sort by start or end first
- Kind of Greedy
- sort interval, then binary search (LeetCode 436 - Find Right Interval)
  -- Sort Interval
  -- Or sort start, end separately
  -- Or sort start, end at one array
- Use TreeMap or TreeMap> to store intervals and compare based on start
- Use Priorityqueue
- Sweep line algorithm
- Interval operation: insert, merge interval

X. Interval Binary Search Tree
- How to remove an interval
private class Node {
 Interval interval; // or directly store start, end; start is used as the key to build BST
 Node left, right;
 int maxValue; // the max value of all intervals rooted in this node

Unlimited switches
isToggled(long idx)
toggle(long start, long end)

Sort by start
Given n appointments, find all conflicting appointments

LeetCode 616 - Add Bold Tag in String

LettCode 452 - Minimum Number of Arrows to Burst Balloons

Given a collection of intervals, find the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.

LeetCode 436 - Find Right Interval
Sort by start then binary search

Google – Remove Alarm
Google – Find a Path Among Circles
- Only merge interval when two circles intersects

LeetCode 352 - Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
TreeMap intervals to merge interval based on start

LeetCode 436 - Find Right Interval
Use TreeMap to store intervals
- Use TreeMap> to handle duplicate start
Sort Intervals based on start + binary search

LeetCode 253 - Meeting Rooms II
find the minimum number of conference rooms required.
starts[i] = intervals[i].start;
ends[i] = intervals[i].end;
- Use PriorityQueue
Arrays.sort(intervals, (a, b) -> { return a.start - b.start;}});
PriorityQueue ends = new PriorityQueue();
pq.offer(new Event(interval.start, 1));
pq.offer(new Event(interval.end, 0));

LeetCode 252 - Meeting Rooms
determine if a person could attend all meetings.

LeetCode 56 - Merge Intervals
LeetCode 57 - Insert Interval

LeetCode 218 - The Skyline Problem
Using TreeMap
Sweepline is used in solving the problem. List height is used to save each of the line segments including both start and end point. The trick here is to set the start segment as negative height. This has a few good uses:
first, make sure the start segment comes before the end one after sorting.
second, when pushing into the queue, it is very each to distinguish either to add or remove a segment.
    public List<int[]> getSkyline(int[][] buildings) {
        List<int[]> heights = new ArrayList<>();
        for (int[] b: buildings) {
            heights.add(new int[]{b[0], - b[2]});
            heights.add(new int[]{b[1], b[2]});
        Collections.sort(heights, (a, b) -> (a[0] == b[0]) ? a[1] - b[1] : a[0] - b[0]);
        TreeMap heightMap = new TreeMap<>(Collections.reverseOrder());
        int prevHeight = 0;
        List<int[]> skyLine = new LinkedList<>();
        for (int[] h: heights) {
            if (h[1] < 0) {
                Integer cnt = heightMap.get(-h[1]);
                cnt = ( cnt == null ) ? 1 : cnt + 1;
                heightMap.put(-h[1], cnt);
            } else {
                Integer cnt = heightMap.get(h[1]);
                if (cnt == 1) {
                } else {
                    heightMap.put(h[1], cnt - 1);
            int currHeight = heightMap.firstKey();
            if (prevHeight != currHeight) {
                skyLine.add(new int[]{h[0], currHeight});
                prevHeight = currHeight;
        return skyLine;
X. Divide and Conquer
  if (buildings.length == 0)
   return new LinkedList<int[]>();
  return recurSkyline(buildings, 0, buildings.length - 1);

 private LinkedList<int[]> recurSkyline(int[][] buildings, int p, int q) {
  if (p < q) {
   int mid = p + (q - p) / 2;
   return merge(recurSkyline(buildings, p, mid),
     recurSkyline(buildings, mid + 1, q));
  } else {
   LinkedList<int[]> rs = new LinkedList<int[]>();
   rs.add(new int[] { buildings[p][0], buildings[p][2] });
   rs.add(new int[] { buildings[p][1], 0 });
   return rs;

 private LinkedList<int[]> merge(LinkedList<int[]> l1, LinkedList<int[]> l2) {
  int h1 = 0, h2 = 0;
  while (l1.size() > 0 && l2.size() > 0) {
   int x = 0, h = 0;
   if (l1.getFirst()[0] < l2.getFirst()[0]) {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h = Math.max(h1, h2);
   } else if (l1.getFirst()[0] > l2.getFirst()[0]) {
    x = l2.getFirst()[0];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
   } else {
    x = l1.getFirst()[0];
    h1 = l1.getFirst()[1];
    h2 = l2.getFirst()[1];
    h = Math.max(h1, h2);
   if (rs.size() == 0 || h != rs.getLast()[1]) {
    rs.add(new int[] { x, h });
  return rs;

X. Thought as different kinds of evet: start/end event
LeetCode 253 - Meeting Rooms II
    public int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for(int i=0; iint
rooms = 0int endsItr = 0for(int i=0; iif(starts[i]else endsItr++; } return rooms; }X. Using prority queue + sweep line
    public int minMeetingRooms(Interval[] intervals) {
            return 0;
        Arrays.sort(intervals, new Comparator() {
            public int compare(Interval t1, Interval t2) {
                if(t1.start != t2.start)
                    return t1.start - t2.start;
                    return t1.end - t2.end;
        int maxOverlappingMeetings = 0;
        PriorityQueue pq = new PriorityQueue<>();      // min oriented priority queue
        for(int i = 0; i < intervals.length; i++) {         // sweeping-line algorithms
            while(pq.size() > 0 && intervals[i].start >= pq.peek())
            maxOverlappingMeetings = Math.max(maxOverlappingMeetings, pq.size());
        return maxOverlappingMeetings;

LeetCode 252 - Meeting Rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
public boolean canAttendMeetings(Interval[] intervals) {
  if (intervals == null)
    return false;

  // Sort the intervals by start time
  Arrays.sort(intervals, new Comparator() {
    public int compare(Interval a, Interval b) { return a.start - b.start; }
    if (intervals[i].start < intervals[i - 1].end)
      return false;
  return true;

TCP/IP Miscs

TCP/IP Miscs

What is this flags(In packet): URG, ACK, PSH, RST, SYN, FIN?
# CWR - Congestion Window Reduced
# ECE - Explicit Congestion Notification echo
# URG - Urgent
# ACK - Acknowledgement
# PSH - Push
# RST - Reset
# SYN - Synchronize
# FIN - Finished
A TCP connection is managed by an operating system through a programming interface that represents the local end-point for communications, the Internet socket. During the lifetime of a TCP connection it undergoes a series of state changes:
1. LISTEN : In case of a server, waiting for a connection request from any remote client.
2. SYN-SENT : waiting for the remote peer to send back a TCP segment with the SYN and ACK flags set. (usually set by TCP clients)
3. SYN-RECEIVED : waiting for the remote peer to send back an acknowledgment after having sent back a connection acknowledgment to the remote peer. (usually set by TCP servers)
4. ESTABLISHED : the port is ready to receive/send data from/to the remote peer.
10. TIME-WAIT : represents waiting for enough time to pass to be sure the remote peer received the acknowledgment of its connection termination request. According to RFC 793 a connection can stay in TIME-WAIT for a maximum of four minutes.

Three-way Connection Establishment Handshake

A (virtual) connection is established via what is commonly known as a three-way handshake.
To establish a TCP connection:
1. (B) --> [SYN] --> (A)
The requesting end (normally called the client) sends a SYN segment specifying the port number of the server that
the client wants to connect to, and the client's initial sequence number.
Note: A SYN packet is a TCP packet with the SYN flag set only (see TCP header diagram in Resources). It's important to note that unless a SYN packet is received by A from B, there is no way to establish a TCP connection. Therefore, if your firewall drops all SYN packets to your internal network (and to itself), there is no way for anyone to establish a TCP connection to you.
2. (B) <-- [SYN/ACK] <--(A)
The server responds with its own SYN segment containing the server's initial sequence number. The
server also acknowledges the client's SYN by ACKing the client's ISN plus one. A SYN consumes one sequence
Note: A SYN/ACK packet is a TCP packet with the SYN and ACK flag set and no other TCP flags.
3. (B) --> [ACK] --> (A)
When the (B) receives the SYN/ACK packet from (A), The client completes the final part of the three-way handshake, returns acknowledge this SYN from the server by ACKing the server's ISN plus one.
Note: An ACK packet is a TCP packet with the ACK flag set only. The important thing to note here is that after the three-way handshake is completed, and the connection is complete, every packet that is part of this TCP connection will always have the ACK bit set.
This is also the reason why connection tracking is so important. Without connection tracking, there is no way for your firewall to know whether an arriving ACK packet is really a part of an established connection. When simple packet filters (and Ipchains) receives a packet with the ACK flag set, it simply allows the packet through (does this sound like a good idea?). When a stateful firewall received an ACK packet, it'll consult a connection table to see if the packet belongs to an established connection. If it does not, the packet is dropped.
Four-way Connection Termination Handshake
What goes up, must come down. A four-way handshake tears down a previously established TCP connection. Again, using the same scheme as above:
1. (B) --> ACK/FIN --> (A)
2. (B) <-- ACK <-- (A)
3. (B) <-- ACK/FIN <-- (A)
4. (B) --> ACK --> (A)
Note: Since a TCP connection is a two way connection, it needs to be torn down in both directions. An ACK/FIN packet (ACK and FIN flags set) is sometimes referred to as a FIN (Finish) packet . However, since the connection is not yet torn down, it is always accompanied by the ACK flag. A packet with only the FIN flag set is NOT legal and is likely maliciously generated.
Resetting a connection
The four-way handshake is not the only way to tear down an established TCP connection. Sometimes, if either hosts need to tear down the connection quickly (timeout, port or host unreachable, etc.), a RST (Reset) packet is sent. Note that since a RST packet is not necessarily always part of a TCP connection, it can be sent by itself. RST packets that are part of a TCP connection is usually accompanied by the ACK flag as well.
Note that RST packets are not acknowledged.
Normal TCP Flag combination
* SYN, SYN ACK, and ACK are used during the three-way handshake which establishes a TCP connection.
* Except for the initial SYN packet, every packet in a connection must have the ACK bit set.
* FIN ACK and ACK are used during the graceful teardown of an existing connection.
* RST ACK can be used to immediately terminate an existing connection.
* Packets during the "conversation" portion of the connection (after the three-way handshake but before the teardown or termination) contain just an ACK by default.
* Optionally, they may also contain PSH and/or URG.
Abnormal TCP Flag combination
* SYN FIN is probably the best known illegal combination. Remember that SYN is used to start a connection, while FIN is used to end an existing connection. It is nonsensical to perform both actions at the same time. Many scanning tools use SYN FIN packets, because many intrusion detection systems did not catch these in the past, although most do so now. You can safely assume that any SYN FIN packets you see are malicious.
* SYN FIN PSH, SYN FIN RST, SYN FIN RST PSH, and other variants on SYN FIN also exist. These packets may be used by attackers who are aware that intrusion detection systems may be looking for packets with just the SYN and FIN bits set, not additional bits set. Again, these are clearly malicious.
* Packets should never contain just a FIN flag. FIN packets are frequently used for port scans, network mapping and other stealth activities.
* Some packets have absolutely no flags set at all; these are referred to as "null" packets. It is illegal to have a packet with no flags set.
What is a FIN_WAIT_1, FIN_WAIT_2 state?
FIN_WAIT_2 seems to occur when the server has an active connection with a client and it wants to shut down the TCP connection (probably in response to a normal application layer "exit"). The server sends the client a packet with a "FIN" bit set. At this point, the server is in FIN_WAIT_1 state. The client gets the FIN packet and goes into CLOSE_WAIT state, and sends an acknowledgment packet back to the server. When the server gets that packet, it goes into FIN_WAIT_2 state. From the server's perspective, the connection is now closed, and the server can't send any more data. However, under the TCP protocol, the client needs to shut down also by sending a FIN packet, which the server TCP implementation should ACK. The server should close about two milliseconds later.

Interview Questions – Thread

Interview Questions – Thread
Java Synchronization
How synchronization is implemented?
Class lock vs Object lock
g() {synchronized(MyClass.class) {}}
How can threads communicate with each other in java? 
What is difference between notify() and notfiyAll()?
Is there a separate stack for each thread in Java?
What is synchronization?
What is synchronization advantage and disadvantage? 

Interview Questions - XML

                        Interview Questions - XML


There are three distinct approaches to parsing XML documents:

• DOM parsing

• Push parsing - SAX

• Pull parsing – StAX

DOM means Document Object Model, SAX stands for Simple API for XML.

DOM was developed by W3C, whereas SAX, StAX were developed by an informal group of participants of mailing list.

They have advantages and disadvantages and should be used depending on the situation.

DOM Parsing

The DOM approach has the following notable aspects:

1.        An in-memory DOM tree representation of the complete document is constructed before the document structure and content can be accessed or manipulated.

2.        Document nodes can be accessed randomly and do not have to be accessed strictly in document order.

3.        Random access to any tree node is fast and flexible, but parsing the complete document before accessing any node can reduce parsing efficiency.

4.        If an XML document needs to be navigated randomly or if the document content and structure needs to be manipulated, the DOM parsing approach is the most practical approach.

5.        DOM is convenient when applications need to traverse the document multiple times.

6.        DOM supports XPath.

7.        For large documents ranging from hundreds of megabytes to gigabytes in size, the in-memory  DOM tree structure can exhaust all available memory, making it impossible to parse such large documents under the DOM approach.

Push Approach -- SAX

1.        SAX was developed by an informal group of participants of the XML-DEV mailing list.

2.        Under the push parsing approach, a push parser generates synchronous events as a document is  parsed, and these events can be processed by an application using a callback handler model.

3.        No no random access, SAX can be used only for a sequential processing of an XML document, it can only traverse XML from top to bottom.

4.        SAX doesn't retain all the information of the underlying XML document such as comments whereas DOM retains almost all the info.

5.        SAX doesn't support XPath.


7.        Comparewd with DOM, SAX is efficient, and consumes lower memory.

Pull Approach -- StAX

1.        Under the pull approach, events are pulled from an XML document under the control of the application using the parser.

2.        StAX is similar to the SAX API in that both offer event-based APIs. However,

3.        StAX differs from the SAX API in the following respects:

4.        In SAX, data is pushed via events to application code handlers.

5.        In StAX, the application "pulls" the data from the XML data stream at its convenience. Application code can filter, skip tags, or stop parsing at any time. The application--not the parser--is in control, which enables a more intuitive way to process data.

5.StAX offers two event-based APIs: a cursor-based API and an iterator-based API.

6.        Unlike the SAX API, the StAX API can be used both for reading and for writing XML documents.

SAX, StAX are good choices for dealing with large documents.


XPath is a language for addressing node sets within an XML document.

The XPath data model treats an XML document as a tree of various node types, such as an element node, an attribute node, and a text node.


XSLT specifies a language for transforming XML documents into other XML documents.

XSLT language constructs are completely based on XML. Therefore, transformations written in  XSLT exist as well-formed XML documents. An XML document containing XSLT transformations is commonly referred to as a style sheet.

An XSLT style sheet merely specifies a set of transformations. Therefore, you need an XSLT processor to apply these transformations to a given XML document. An XSLT processor takes an XML document and an XSLT style sheet as inputs, and it transforms the given XML document to its target output, according to transformations specified in the style sheet. The target output of XSLT transformations is typically an XML document but could be an HTML document or any type of text document. Two commonly used XSLT processors are Xalan-Java and Saxon.

To use an XSLT processor, you need a set of Java APIs, and TrAX is precisely such an API set.

XML Libraries

Xerces, jdom, Sun’s XML parser

JAXP - Java API for XML Processing

Sun packages its XML APIs as the Java API for XML Processing (JAXP). JAXP is included in Jdk5.0 and later.

Its XSLT processor is actually Xalan from Apache.

Using factory classes, JAXP allows you to plug in any conforming XML or XSL parse.

JAXB - Object Binding

XML Schema Binding to Java Representation



Pro XML Development with Java Technology

Java Network Miscs

Java Network Miscs

About Too many open files

The number of open files allowed is an Operating System dependent setting. This is a limited resource that is shared by all processes on the machine. The standard programming practice is to make sure to close all files that the program opens. On Unix systems this applies to socket connections as well.

A very common mistake is to assume that the runtime garbage collector (GC) will look after resources in the same way that it looks after memory references. However, wshile the memory associated with the object itself is collected by the GC, the resources associated with that object may not be cleaned up.

There are at least two types of resource that are collected under the stream object:

* Memory associated with the stream object itself, and with managing state within the stream

* An operating system file descriptor or handle that relates to the underlying file within the file system

The GC will take care of the first aspect while leaving the underlying descriptor open, thus consuming valuable system resources over time and eventually resulting in a denial-of-service scenario.

when use Runtime.getProcess() method to get a process and then exec() an external script,

API automatically opens three streams (stdout, stderr, stdin) each time the getProcess() is called. It is the responsibility of the caller to close those streams when done.


see sample code for how to close. Scan for "close".

Avoid use nameless InputStream/OutputStream, instead explicitly close it.

Properties prop = new Properties(); prop.load(new FileInputStream(propertyFile));

The specified stream remains open after this method returns.

From Elliote Rusty Harold's Java IO:

Not all streams need to be closed -- byte array output streams do not need to be closed, for example. However, streams associated with files and network connections should always be closed when you're done with them.

For example, if you open a file for writing and neglect to close it when you're through, then other processes may be blocked from reading or writing to that file.

Does closing a BufferedOutputStream also close the underlying OutputStream?

Yes, it closes it.

The behaviour is actually inherited from FilterOutputStream. The Javadocs for for FilterOutputStream.close state:

Closes this output stream and releases any system resources associated with the stream.

The close method of FilterOutputStream calls its flush method, and then calls the close method of its underlying output stream.

BufferedOutputStream extends FilterOutputStream, Closing the BufferedOutputStream will also close the underlying OutputStream. You should close the BufferedOutputStream not underlying OutputStream so that it flushes its contents before closing the underlying stream.

Notes from Fundamental Networking in Java:

Closing a connected socket

In fact there are several ways to close a socket:

(a) close the socket itself with Socket.close();



Any one of these is sufficient, and exactly one of them is necessary, to close the socket and release all its resources. You can't use more than one of these techniques on any given socket. As a general rule you should close the output stream rather than the input stream or the socket, as the output stream may require flushing.

Object Stream Deadlock


ObjectInputStream in = new ObjectInputStream(socket.getInputStream());

ObjectOutputStream out = new ObjectOutputStream(socket.getOutputStream());

The ObjectInputStream constructor calls readStreamHeader to read and verifies the header and version written by the corresponding ObjectOutputStream.writeStreamHeader method. The ObjectInputStream constructor blocks until it completes reading the serialization stream header. Code which waits for an ObjectInputStream to be constructed before creating the corresponding ObjectOutputStream for that stream will deadlock, since the ObjectInputStream constructor will block until a header is written to the stream, and the header will not be written to the stream until the ObjectOutputStream constructor executes.

So Always create an ObjectOutputStream before an ObjectInputStream for the same socket.

Socket Output





Don't mix-use readObject/writeObject and readUnshared/writeUnshared.

os.writeObject("Hello World");


os.writeObject("Hello World");

what gets written to the file is something like this:


for the third entry, it just writes a special flag which says use the same Object as found at position 1

in this object stream. It's bascially doing a compression for you of the data being written.

Using writeUnshared, you get something like this:


All this means that you can't mix readObject/writeObject and readUnshared/writeUnshared.

If you want to readUnshared then you must writeUnshared.

If you write them without unshared (using the compression) and then readUnshared (as if it did not have the compression) you are going to have problems because it's going to hit that flag and not know what to do.

This would output error like: cannot read back reference as unshared






writeUnshared, then readObject is ok.

BufferedIutputStream/BufferedOutputStream just add a local buffer to improve network read/write performance, and would not affect remote side.
So one side can use buffered stream and remote side still can use un-buffered stream.
This can happen when you update existing code, thus cause different code version between two nodes.


Fundamental Networking in Java

Java Thread Miscs

Java Thread Miscs

Multi-thread considerations
1-     Synchronize access to shared mutable data and be ware of insufficient synchronization
When multiple threads share mutable data, each thread that reads or writes the data must perform synchronization.
The synchronized keyword ensures that only a single thread can execute a method or block at one time and prevent an object from being observed in an inconsistent state while it's being modified by another thread, also it ensures one thread's changes would be visible to other threads.
2-     Avoid excessive synchronization
Excessive synchronization can cause reduced performance, deadlock, or even nondeterministic behavior.
Avoid synchronization by other approaches.
1. Don't share mutable data, but share immutable data or a cloned one.
2. Use utilities in java.util.concurrent package, such as AtomicLong
3-     Limit the amount of work within synchronized regions.
Do as little work as possible inside synchronized, If we must perform some time-consuming activity, find a way to move the activity out of the synchronized block.
4-     Prefer executors and tasks to threads
5-     Never use suspend, resume and stop of thread.
6-     For interval timing, always use System.nanoTime
7-     Document thread safety
8-     Avoid multiple locking.
9-     Acquire lock in some consistent well-defined order
volatile keyword
Declaring a volatile Java variable means: it will not be stored in the thread's local cache. Whenever thread is updating the values, it is updated to the main memory. So, other threads can access the most recently written value.
Avoid busy-wait
busy-wait is the code repeatedly checks a shared object waiting for
something to happen.
API on thread
Other methods such as suspend, resume and stop are deprecated, and not recommended to use as they are deadlock-prone and not safe.
Thread.stop can result in data corruption.
public final void join() throws InterruptedException
Waits for this thread to die.
public final void join(long millis)
Waits at most millis milliseconds for this thread to die.
Difference between notify and notifyAll
notify wakes a single waiting thread, and notifyAll wakes all waiting threads.
It is safer to use notifyAll.
It will always yield correct results. You may wake some other threads, too, but this won't affect the correctness of your program. These threads will check the condition for which they're waiting and, finding it false, will continue waiting.
Using notifyAll in place of notify protects against accidental or malicious waits by an unrelated thread. Such waits could otherwise “swallow” a critical notification, leaving its intended recipient waiting indefinitely.
As an optimization, you can choose to invoke notify instead of notifyAll.
Timer and ScheduledThreadPoolExecutor
A timer uses only a single thread for task execution, which can hurt timing accuracy in the presence of long-running tasks. If a timer's sole thread throws an uncaught exception, the timer ceases to operate.
A scheduled thread pool executor supports multiple threads and recovers gracefully from tasks that throw unchecked exceptions.
For interval timing, always use System.nanoTime
System.nanoTime is used to time the activity rather than System.currentTimeMillis. For interval
timing, always use System.nanoTime  in preference to System.currentTime-
Millis. System.nanoTime is both more accurate and more precise, and it is not
affected by adjustments to the system's real-time clock.
Improve Performance for Lazy initialization
Under most circumstances, normal initialization is preferable to lazy initialization.
Use lazy initialization holder class idiom on a static field
// Lazy initialization holder class idiom for static fields
private static class FieldHolder {
static final FieldType field = computeFieldValue();
static FieldType getField() { return FieldHolder.field; }
When the getField method is invoked for the first time, it reads  Field-
Holder.field for the first time, causing the FieldHolder class to get initialized.

A modern VM will synchronize field access only to initialize the class.
Once the class is initialized, the VM will patch the code so that subsequent access to the field does not involve any testing or synchronization.
Use Double-check idiom on an instance field
This idiom avoids the cost of locking when access-
ing the field after it has been initialized.
It is critical that the field be declared volatile
private volatile FieldType field;
    FieldType getField() {
    FieldType result = field;
        synchronized(this) {
        result = field; // this is important
            field = result = computeFieldValue();
return result;
Prefer concurrency utilities to wait and notify
The higher-level utilities in java.util.concurrent fall into three categories: the Executor Framework, concurrent collections; and synchronizers.
The concurrent collections provide high-performance concurrent implementations of standard collection interfaces such as ConcurrentHashMap, ConcurrentSkipListMap, ConcurrentLinkedQueue, ConcurrentSkipListSet.
They combine several primitives into a single atomic operation.
For example, ConcurrentMap extends Map and adds several methods, including putIfAbsent(key, value).
Prefer executors and tasks to threads
It provide thread pool, various kinds of executors.
ExecutorService executor = Executors.newSingleThreadExecutor();
In a lightly loaded server, use Executors.newCachedThreadPool.
In a cached thread pool, submitted tasks are not queued but immediately handed off to a thread for execution. If no threads are available, a new one is created.
In a heavily loaded server, use Executors.newFixedThreadPool.
Use executor service provided in java.unit.concurrent package.
The key abstraction is the unit of work, which is called a task. There are two kinds of tasks: Runnable and Callable (which is like Runnable, except that it returns a value).
Deadlock is a situation where two or more threads are blocked forever, waiting for each other. When a thread holds a lock forever, other threads attempting to acquire that lock will block forever waiting. When thread A holds lock L and tries to acquire lock M, but at the same time thread B holds M and tries to acquire L, both threads will wait forever.
How to avoid deadlocks
Acquire lock in some consistent well-defined order
Deadlock usually occurs when multiple threads need the same locks but obtain them in different order.
Shrink synchronized blocks to avoid multiple locking
Do as little work as possible inside synchronized regions.
If you must perform some time-consuming activity, find a way to
move the activity out of the synchronized region.
Never leave control to the client within a synchronized method or block. 
Don't call an alien method from within a synchronized region.
Use Open Calls to Avoiding Deadlock Between Cooperating Objects
Inconsistent Lock-ordering Deadlocks
public class LeftRightDeadlock {
private final Object left = new Object();
private final Object right = new Object();
public void leftRight() {
synchronized (left) {
synchronized (right) {doSomething();}
public void rightLeft() {
synchronized (right) {
synchronized (left) {doSomethingElse();}
Dynamic Lock Order Deadlocks
The lock order depends on the order of arguments passed to transferMoney, and these in turn might depend on external inputs. Deadlock can occur if two threads call transferMoney at the same time, one transferring from X to Y, and the other doing the opposite.
public void transferMoney(Account fromAccount,Account toAccount,DollarAmount amountToTransfer) {
synchronized (fromAccount) {
synchronized (toAccount) {
if (fromAccount.hasSufficientBalance(amountToTransfer) {
Consider what happens when thread A executes:
transferMoney(accountOne, accountTwo, amount);
While at the same time, thread B executes:
transferMoney(accountTwo, accountOne, anotherAmount);
Again, the two threads try to acquire the same two locks, but in different orders.
Use an ordering to acquire locks in a fixed sequence
Account firstLock, secondLock;
if (fromAccount.accountNumber() == toAccount.accountNumber())
throw new Exception("Cannot transfer from account to itself");
else if (fromAccount.accountNumber() < toAccount.accountNumber()) {
firstLock = fromAccount; secondLock = toAccount;}
else {
firstLock = toAccount; secondLock = fromAccount;}
synchronized (firstLock) {
synchronized (secondLock) {
if (fromAccount.hasSufficientBalance(amountToTransfer) {
Another way to induce an ordering on objects is to use System.identityHashCode, which returns the value that would be returned by Object.hashCode.
Difference between Thread.sleep() and Object.wait()
1.       Thread.sleep is static method of Thread class and Thread.sleep would throw InterruptedException when it is awaken by other thread prematurely.
2.       Thread.sleep can be used anywhere in the code to halt the current thread execution for the specified time.
3.       Thread.sleep causes the current thread into Non-Runnable state, but, it doesn't release ownership of the acquired monitors. So, if the current thread is into a synchronized block/method, then no other thread will be able to enter that block/method.
4.       Thread.sleep(n) guarantees to sleep for at least n milliseconds. But it may sleep for considerably more if the system is busy.
5.       If somebody changes the system time, you may sleep for a very long time or no time at all. The behavior is OS and JDK-dependent.
1.     Object.wait is instance method of Object class.
2.     The wait method is used to put the thread aside for up to the specified time. It could wait for much lesser time if it receives a notify() or notifyAll() call.
3.     Object.wait have to be called inside synchronized block, otherwise it would throw IllegalMonitorStateException.
4.     Object.wait causes the current thread into Non-Runnable state, like Thread.sleep, but Object.wait releases the locks before going into Non-Runnable state. This causes the current thread to wait either another thread invokes the 'notify()' method or the 'notifyAll()' method for this object, or a specified amount of time has elapsed.
5.     Using sleep makes your codes non-scalable across hardwares, where a nicely written wait/notify code scales well.




Popular Posts